cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2026 · MediumReaching an Ordered Pair

Reaching an Ordered Pair

Национална олимпиада - Национален кръг 2026

Submission name: pairs.cpp

Solve in Editor →

Problem summary

Starting at (a,b), repeatedly replace the pair by (a+b,b) or (a,a+b). Find the minimum moves to reach the ordered target (c,d), or −1 if it is unreachable.

Input

T followed by T quadruples a b c d.

Output

Minimum moves or −1 for each query.

Constraints

1 ≤ T ≤ 100000; all coordinates are positive and at most 10^18.

Worked example

The worked example illustrates the rule described in the analysis.

Input

3
1 1 3 2
2 3 2 3
1 1 1 5

Output

2
0
4

Solution analysis

  1. Reverse the process. If the target coordinates differ, the larger coordinate must have been increased last; subtract the smaller one. This predecessor is unique.
  2. Batch repeated subtractions using integer division. While both coordinates exceed their required starting values, subtract q times without letting the changed coordinate drop below its start. For c>d, q=(c−a)/d; use the symmetric rule otherwise.
  3. When one coordinate equals its start, only repeated additions of that fixed coordinate can remain. Check nonnegative difference and divisibility to finish in one step. Reject if neither finishing rule works.
  4. For (1,1) to (3,2), reverse (3,2) to (1,2), then to (1,1), giving two moves. Equal starting and target pairs require zero moves.

Why it works

Every positive noninitial reachable pair has a unique inverse: subtract its smaller coordinate from the larger. Thus reverse steps cannot skip another shorter route. Batching exactly repeats this forced operation until a coordinate boundary or direction change, and the terminal divisibility test handles precisely the remaining forced steps.

Complexity: O(log max(c,d)) time per query and O(1) auxiliary space, by the batched Euclidean reduction.

Watch out. Pairs are ordered; do not sort their coordinates. GCD equality alone is insufficient. Avoid one subtraction per move, since the answer can approach 10^18. All arithmetic uses long long.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Every positive noninitial reachable pair has a unique inverse: subtract its smaller
// coordinate from the larger. Thus reverse steps cannot skip another shorter route.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
long long minimumMoves(long long a,long long b,long long c,long long d){
    long long moves=0;
    while(c>a&&d>b){
        if(c>d){
            long long count=(c-a)/d;
            if(count==0){
                break;
            }
            c-=count*d;
            moves+=count;
        }
        else{
            long long count=(d-b)/c;
            if(count==0){
                break;
            }
            d-=count*c;
            moves+=count;
        }
    }
    if(c==a&&d>=b&&(d-b)%a==0){
        return moves+(d-b)/a;
    }
    if(d==b&&c>=a&&(c-a)%b==0){
        return moves+(c-a)/b;
    }
    return -1;
}
int main(){
    int tests;
    cin>>tests;
    while(tests--){
        long long a,b,c,d;
        cin>>a>>b>>c>>d;
        cout<<minimumMoves(a,b,c,d)<<'\n';
    }
}

Source: Arena Olimpiici ↗