---
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

#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

#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 ?