owned this note changed 4 years ago
Published Linked with GitHub

\(\Huge \text{🌱 Free Contest 131 - HURRYBIRD}\)


📌 Tags: Math, Implementation
👤 Writer: @SPyofgame
👥 Contributor: @mạnh, @kazamahoang
📋 Content:


Hướng dẫn

Nhận thấy rằng:

  • Khi chỉ đi qua phải hoặc trái, ta tạo ra thời điểm sớm nhất đến các ô trong lưới
  • Những bước đi qua trái hoặc xuống dưới thì sẽ luôn tồn tại cách đi khác đến sớm hơn, nên sẽ chỉ làm tăng thêm thời gian di chuyển

Gọi \(a\) là chi phí để di chuyển \(1\) bước sang ngang hoặc sang dọc

Gọi \(b\) là chi phí để di chuyển \(1\) bước sang đường chéo kề góc

Gọi \(d_x\) là số bước tối thiểu cần di chuyển để đi theo hàng \(1 \rightarrow n\), ta có \(d_x = |n - 1|\)

Gọi \(d_y\) là số bước tối thiểu cần di chuyển để đi theo cột \(1 \rightarrow m\), ta có \(d_y = |m - 1|\)

Gọi \(d_z\) là số bước ngang, dọc tối thiểu cần di chuyển thêm nếu chỉ đi theo đường chéo từ ô \((1, 1)\), ta có \(d_z = \begin{cases} 1 & d_x \equiv d_y \pmod 2 \\ 0 & d_x \not\equiv d_y \pmod 2 \end{cases}\)

Không mất tính tổng quát, ta xét \(0 \leq d_x \leq d_y\)

Khi \(d_x = 0\) thì ta không thể đi được đường chéo vì chim không được đi ra khỏi lưới, nên chỉ có thể đi đường ngang

  • Kết quả bài toán lúc này là \(a \times (d_x + d_y)\)

Ngược lại, ta xét \(3\) trường hợp:

  • [A] Ưu tiên đi đường ngang hoặc dọc
  • [B] Ưu tiên đi đường chéo, nhưng chỉ đi ngang dọc khi \(d_z = 1\)
  • [C] Đi luôn một đường chéo tới khi không đi được nữa thì đi ngang dọc về đích
  • Chi phí cách [A]\(a \times (d_x + d_y)\)
  • Chi phí cách [B]\(b \times (d_y - d_z) + a \times d_z\)
  • Chi phí cách [C]\(a \times (d_y - d_x) + b \times d_x\)
  • Kết quả bài toán là chi phí nhỏ nhất trong \(3\) cách đi

Code

Query Time: \(O(1)\)
Total Time: \(O(q)\)
Space: \(O(1)\)
Algo: Math, Implementation

Mạnh's Code
#include<bits/stdc++.h> #define LL long long using namespace std; int main() { int t; cin >> t; while(t--) { LL n, m, x, y; scanf("%lli%lli%lli%lli", &n, &m, &x, &y); LL cm = ((n&1) != (m&1)); if (n > m) swap(n, m); --n; --m; LL res = min(n*x + m*x, n*y + (m - n)*x); if (n >= 1) res = min(res, (m - cm)*y + cm*x); printf("%lli\n", res); } }
SPyofgame Code
#include <iostream> using namespace std; template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; } template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; } typedef long long ll; ll solve(ll x, ll y, ll u, ll v, ll a, ll b) { if (x > u || y > v) return 0; ll dx = u - x; ll dy = v - y; ll dz = (dx & 1) != (dy & 1); if (dx > dy) swap(dx, dy); ll res = a * (dx + dy); if (dx == 0) return res; minimize(res, a * (dy - dx) + b * dx); minimize(res, b * (dy - dz) + a * dz); return res; } int main() { ios::sync_with_stdio(NULL); cin.tie(NULL); int q; cin >> q; while (q-->0) { ll n, m, x, y; cin >> n >> m >> x >> y; cout << solve(1, 1, n, m, x, y) << "\n"; } return 0; }

Bonus

  • Bạn có thể giải với trường hợp tổng quát đi từ \((x, y)\) đến \((u, v)\) với chi phí \(a\) cho đường ngang, \(b\) cho đường dọc, \(c\) cho đường chéo chính, \(d\) theo đường chéo phụ không ?
  • Bạn có thể giải khi chi phí các đuờng ngang dọc và các đường chéo là khác nhau không ? Nếu không thì khi giảm \(n, m\) nhỏ đi bạn có giải được không ?
Select a repo