cppAcademy
FROM LEARNING TO COMPETING

Expert.
Put your skills to the test.

Bulgarian Informatics Group A · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group A also includes challenging national-level problems. The 109 National-round tasks shared by Groups A and B retain their existing permanent URLs and explanations. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP A2015 · MediumGame theory

Triple Game

National Olympiad — Regional round (2015 season)

Submission name: x3game.cpp

Solve in Editor →

Problem summary

Two players alternately remove a positive number of balls from one of two piles. If either pile is exactly three times the other, the player to move loses immediately, even if moves would otherwise be possible. For each of three positions, report no winning strategy or a guaranteed winning move.

Input

Three lines, each containing nonnegative P Q.

Output

For each position: 0 if losing, otherwise pile number (1 or 2) and positive number removed.

Constraints

P and Q have at most 18 decimal digits.

Worked example

Official sample; other valid outputs may exist.

Input

11 9
6 2
5 5

Output

1 8
0
0

Solution analysis

  1. The immediate losing positions are the two 3:1 rays, including (0,0). Another losing family consists of (a,a) with a not divisible by 3.
  2. For any nonterminal position let a be the smaller pile and b the larger. If a is divisible by 3, reduce b to a/3 and end the game. Otherwise, when b>a reduce b to a, leaving the second losing family. Equality with a not divisible by 3 is the only remaining case.
  3. For (11,9), a=9 is divisible by 3, so reduce the first pile to 3, removing 8. For (5,5), any reduction creates an unequal position and allows the opponent one of the replies above.

Why it works

Every terminal position is losing by definition. From (a,a) with 3∤a, any move creates unequal piles and cannot create a terminal ratio, since the unchanged pile a is not a multiple of 3. The described rule moves every other nonterminal position to a terminal ratio or such an equal position. Induction on the total number of balls therefore establishes the classification and winning moves.

Complexity: O(1) time and space per position.

Watch out. A terminal ratio ends the game before a move. Use 64-bit integers: multiplying an at-most-18-digit pile by 3 remains safe.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Every terminal position is losing by definition. From (a,a) with 3∤a, any move creates
// unequal piles and cannot create a terminal ratio, since the unchanged pile a is not a multiple of 3.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int test=0;test<3;++test){
        long long p,q;
        cin>>p>>q;
        if(p==3*q||q==3*p){
            cout<<0<<'\n';
            continue;
        }
        long long a=min(p,q),b=max(p,q);
        if(a==b&&a%3!=0){
            cout<<0<<'\n';
            continue;
        }
        long long target=(a%3==0?a/3:a);
        int pile=(p>=q?1:2);
        cout<<pile<<' '<<b-target<<'\n';
    }
}

Source: Arena Olimpiici ↗