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