2125B - Left and Down Problem Link 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;

}