Game Theory in Competitive Programming Part 10

Codeforces: Integer Game

Welcome to part 10 of this series, in case you have missed part 9, here is the link: Part 9

Problem Statement

Anton and Harris are playing a game to decide which of them is the king of problemsetting.

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.

Feeling confident in his skills, Anton decided to let Harris choose whether he wants to go first or second. Help Harris defeat Anton and become the king of problemsetting!

Input

The first line of input contains three distinct positive integers a, b, and c (1≤a,b,c≤10^9) — the initial number of stones in piles 1, 2, and 3 respectively.

Interaction

The interaction begins by reading the integers a, b and c.

After reading the integers, print a single line containing either “First” or “Second”, denoting who you want to play as (as first or second correspondently).

On each turn, the first player (either you or the judge) must print a positive integer y (1≤y≤10^12). Then, the second player must print 1, 2, or 3, indicating which pile should have y stones added to it. From the second turn onwards, the pile that the second player chooses must be different from the pile that they chose on the previous turn. If you are playing as Second and complete 1000 turns without losing, or if you are playing as First and the judge has determined that it cannot make a move without losing, the interactor will print 0 and will finish interaction. This means that your program is correct for this test case, and you should exit immediately.

If you are playing as First and complete 1000 turns without winning, or if you are playing as Second and print a move that makes two piles have the same number of stones, or if you output an invalid move as either player, the interactor will print −1 and will finish interaction. You will receive a Wrong Answer verdict. Make sure to exit immediately to avoid getting other verdicts.

Problem Link

Problem - F - Codeforces

Explanation

Example —

Input 
5 2 6
3
0
Output 
First
2
3

In the given example, the three piles are initially given stones as 5,2, and 6. The first player is then selected and 2 stones are provided. If the user puts the stones on the 3rd pile, the status of the three piles is 5,2 and 8. Now, 3 stones are given. As in the question, the second player can’t put stones on the same pile for two consecutive moves, putting 3 stones on both first and second will make 2 piles with the same number of stones and hence the First player wins.

Intuition

It can be observed that the first player can win in at most 3 moves. How? If the piles are forced to be in an arithmetic sequence, with the pile with maximum stones not accessible, the game will be over.

Approach

The first player will give stones to the second player, and the second player has to put the stones on any of the three piles. If the second player puts the stones on a pile such that two piles result in having the same number of stones, he/she loses.

If the first player fails to let the second player lose in 1000 moves, the first player loses. The intuition is of an arithmetic sequence, with the pile having maximum stones not accessible by giving stones that the pile in which the stones are added, that pile becomes the one with the maximum number in the series. The first player then can give the number of stones equal to the common difference in the series. The simple approach explains the winning of the first player every time with at most 3 moves and thus becoming the king of problemsetting.

Solution

Let us try to make the piles in an arithmetic sequence. Firstly, we need to identify the position of maximum, minimum, and middle length of stones. We know that in an arithmetic series, the average of the largest and the minimum value is always equal to the middle value. The first value given by the first player will be y= 2 * a[max] — a[min] — a[mid] and the pile it will be added to will be having the maximum stones after the move.

So, if the second player adds the stones to the pile having a minimum number of stones, the total stones in that pile will be 2* a[max] — a[mid] being the maximum value. And other piles still as a[max] and a[mid]. Now the piles are in arithmetic series.

(2*a[max] — a[mid] + a[mid])/2 = Middle pile, that is, a[max].

Now the first player will give y=a[max]-a[mid] stones which when added to any of the two piles will result in the termination of the game.

In the other scenario, if the stones 2*a[max] — a[min] — a[mid] is added to the pile with the middle number of stones initially, it will then have total stones to be 2*a[max] — a[min] with having the maximum number of stones. The piles will again become an arithmetic sequence with the pile having maximum stones not accessible.

(2*a[max] — a[min] + a[min])/2 = Middle pile, that is, a[max].

In the third case, when the second player adds the stones on the pile already having the maximum number of stones, the total stones on that pile will be 3*a[max]-a[min]-a[mid]. In this, the first player needs to give an extra set of stones to win the game. As the pile with the maximum number of stones is not accessible in the next move by the second player, the first player can give stones as y= 2 * a[max] — a[min] — a[mid] which when placed on any of the two other piles will make it an arithmetic sequence, resulting in the win of the first player.

Code