[problem:2125B]↵
[Problem Link](https://mirror.codeforces.com/problemset/problem/2125/B)↵
Editorial for Codeforces 2125B — Left and Down↵
↵
Problem Restatement↵
You are given a robot at position (a, b) on a grid. The robot can move left and down using any pair (dx, dy) where 0 ≤ dx, dy ≤ k. Each distinct pair costs 1 the first time it's used; reusing it is free. The goal is to reach (0, 0) with minimum cost.↵
↵
Observations↵
- You want to minimize the number of distinct move pairs.↵
- If you can reach (0, 0) using just one pair repeatedly, the cost is 1.↵
- Otherwise, you need at least two pairs → cost is 2.↵
↵
Solution Logic↵
Let g = gcd(a, b). Then:↵
- You can reduce both a and b by g steps of (a/g, b/g).↵
- If both a/g and b/g are ≤ k, then one pair is enough → cost = 1↵
- Else, you need at least two different pairs → cost = 2↵
↵
Code↵
```cpp↵
↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
↵
long long a, b, k;↵
↵
cin >> a >> b >> k;↵
↵
long long gd = __gcd(a, b);↵
↵
if (a / gd <= k && b / gd <= k)↵
↵
cout << 1 << '\n';↵
↵
else↵
↵
cout << 2 << '\n';↵
↵
}↵
↵
int main() {↵
↵
int t;↵
↵
cin >> t;↵
↵
while (t--) solve();↵
↵
return 0;↵
↵
}
[Problem Link](https://mirror.codeforces.com/problemset/problem/2125/B)↵
Editorial for Codeforces 2125B — Left and Down↵
↵
Problem Restatement↵
You are given a robot at position (a, b) on a grid. The robot can move left and down using any pair (dx, dy) where 0 ≤ dx, dy ≤ k. Each distinct pair costs 1 the first time it's used; reusing it is free. The goal is to reach (0, 0) with minimum cost.↵
↵
Observations↵
- You want to minimize the number of distinct move pairs.↵
- If you can reach (0, 0) using just one pair repeatedly, the cost is 1.↵
- Otherwise, you need at least two pairs → cost is 2.↵
↵
Solution Logic↵
Let g = gcd(a, b). Then:↵
- You can reduce both a and b by g steps of (a/g, b/g).↵
- If both a/g and b/g are ≤ k, then one pair is enough → cost = 1↵
- Else, you need at least two different pairs → cost = 2↵
↵
Code↵
```cpp↵
↵
#include<bits/stdc++.h>↵
↵
long long a, b, k;↵
↵
cin >> a >> b >> k;↵
↵
long long gd = __gcd(a, b);↵
↵
if (a / gd <= k && b / gd <= k)↵
↵
cout << 1 << '\n';↵
↵
else↵
↵
cout << 2 << '\n';↵
↵
}↵
↵
int main() {↵
↵
int t;↵
↵
cin >> t;↵
↵
while (t--) solve();↵
↵
return 0;↵
↵
}
