owned this note
owned this note
Published
Linked with GitHub
---
tags: VNOJ, Free Contest, Math, Implementation, SPyofgame
title: 🌱 Free Contest 131 - HURRYBIRD
author: Editorial-Slayers Team
license: Public domain
---
<style>
.markdown-body { max-width: 2048px; }
</style>
$\Huge \text{🌱 Free Contest 131 - HURRYBIRD}$
-----
###### 🔗 Link: [https://oj.vnoi.info/problem/fc131_hurrybird](https://oj.vnoi.info/problem/fc131_hurrybird)
###### 📌 Tags: `Math`, `Implementation`
###### 👤 Writer: @SPyofgame
###### 👥 Contributor: [@mạnh](https://codeforces.com/profile/Hoa_Dau_Biec), [@kazamahoang](https://codeforces.com/profile/PhaiCoGiaiQuocGia)
###### 📋 Content:
[TOC]
-----
## 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]** là $a \times (d_x + d_y)$
- Chi phí cách **[B]** là $b \times (d_y - d_z) + a \times d_z$
- Chi phí cách **[C]** là $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
> [color=lightgreen]
:::success
:::spoiler Mạnh's Code
```cpp=
#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);
}
}
```
:::
:::success
:::spoiler SPyofgame Code
```cpp=
#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 ?