ZZZ's Site

狗蛋儿

26 July 2020

[Codeforces 1375F] Integer Game

by zzz

Problem Description

Problem Link

There are three piles of stones, initially containing a, b, and c stones, where a, b, and c are distinct positive integers. On each turn of the game, the following sequence of events takes place:

The first player chooses a positive integer y and provides it to the second player.
The second player adds y stones to one of the piles, with the condition that he cannot choose the same pile in two consecutive turns.
The second player loses if, at any point, two of the piles contain the same number of stones. The first player loses if 1000 turns have passed without the second player losing.

Solution

Solution from the tutorial is as follows,

Assume that the initial numbers of stones are p<q<r. On the first turn, choose y=2r−p−q. We then have three cases:

Case 1. y is added to p.
The piles now have 2r−q, q and r stones. Now choose y=r−q. Since the pile with 2r−q stones cannot be chosen on this turn, this results in a win.
Case 2. y is added to q.
The piles now have p, 2r−p and r stones. Choose y=r−p. Similarly to the previous case this results in a win since the pile with 2r−p stones cannot be chosen on this turn.
Case 3. y is added to r.
The piles have p<q<3r−p−q stones. We now have a situation similar to the initial one, with the difference that the pile with the largest number of stones cannot be chosen on the next turn. Thus we may repeat the strategy and obtain a guaranteed win this time.

How to approch the solution?

Step 1, try some examples and find “Singularity”. (I had tried a lot and found for 1, 2, 4x, the player can give 5.)

Step 2, try to generalize the “Singularity” to cover all the cases. (I failed to figure out the 5 is 2 *4 - 1 - 2).

tags: Codeforces - Constructive - Inductive

Posts

subscribe via RSS