A few words first, since last Friday, I have been dizzy, and I feel my feet off the ground when I move a little.
Went to the hospital for a check-up. Fortunately, it was just excessive fatigue. After a week at home, some medicine, I feel like I can roll again. But still you mention, the body is the capital of revolution, old iron people must take good care of the body ~
Continue the fight
Start 1740 “A New Stone Game”.
Topic link
Poj.org/problem?id=…
Topic describes
Alice and Bob decide to play a new stone game.At the beginning of the game they pick n(1<=n<=10) piles of stones in a line. Alice and Bob move the stones in turn.
At each step of the game,the player choose a pile,remove at least one stones,then freely move stones from this pile to any other pile that still has stones.
For example: n=4 and the piles have (3,1,4,2) stones.
If the player chose the first pile and remove one.Then it can reach the follow states.
- 1 4 2 2
- 1. What do you think of the Pile? 2.
- 1 1 1 2 2 (Pile 3)
- 1 1 1 2 3 3 4
- 0 2 5 2 (move one stone to Pile 2 and another one to Pile 3)
- 0 2 4 3 (Move one stone to Pile 2 and another one to Pile 4)
- 3. Move one stone to Pile 3 and another one to Pile 4.
- 0 3 4 2 (Move two stones to Pile 2)
- 0 1 6 2 (Move two stones to Pile 3)
- 0 1 4 4 (Move two stones to Pile 4)
Alice always moves first. Suppose that both Alice and Bob do their best in the game.
You are to write a program to determine who will finally win the game.
The input
The input contains several test cases.
The first line of each test case contains an integer number n, denoting the number of piles.
The following n integers describe the number of stones in each pile at the beginning of the game, you may assume the number of stones in each pile will not exceed 100.
The last test case is followed by one zero.
The output
For each test case, if Alice win the game,output 1,otherwise output 0.
The sample input
3, 2, 1, 3, 2, 1, 1, 0
Sample output
1 0
Answer key
First, let’s analyze the operations that players can do, which can be roughly divided into three steps:
- So let’s pick one of n pebbles, let’s call it PiP_iPi.
- 1≤x≤Pi1 \le x \le P_i1≤x≤Pi.
- Take yyy from the remaining Pi− Xp_i-xpi − X and put them into any heap or piles that have not yet been taken, 0≤y≤Pi−x0 \le y \le P_i-x0≤ Y ≤Pi−x.
It is not difficult to find that when there is only a pile of stones left, the player can remove all the stones, so n=1n =1n =1 is a winning situation.
Then, if n=2n=2n=2, when the number of two heaps is the same, the first step can only reduce one heap and increase or keep the other heap.
Let’s assume that P0P_0P0 reduces x+ YX + YX + Y, and P1P_1P1 increases YYy. Then a subsequent party must be in P1 + yP_1 + yP1 + y take (P1 + y) – (P0 – x – y) (P_1 + y) – (P_0 – x – y) (P1 + y) – (P0 – x – y), and let the two piles into the same situation again.
Until the first hand enters the situation P0=1P_0 = 1P0=1, P1=1P_1 = 1P1=1, the first hand can only take one of them, let the second hand into n=1n=1n=1 must win the situation.
So n=2n=2n=2 with the same number of pebbles is a losing situation.
When the two piles of pebbles are not equal, set P0>P1P_0 gt P_1P0>P1, and the first hand can always remove P0− P1p_0-P_1P0 −P1 from P0P_0P0, so that the second hand enters the situation of losing.
So n=2n=2n=2 and not the same number of pebbles is a winning situation.
If you keep diverging, if you take into account that NNN is even, if any of these piles have another heap with the same number. For example:
In this case, the NNN heap can be divided into two identical parts, such as:
At this point, the latter hand can enter the rogue state, constantly imitate the actions of the first hand, so that the first hand is always facing this symmetrical situation. So the symmetric situation where NNN is even is a loser.
Then, if NNN is even, how can the first player construct a symmetric situation so that the opponent will lose?
Let the number of pebbles in NNN be P1P_1P1, P2P_2P2… PPP is a monotone increasing sequence because players can manipulate any pile of stones.
In order to construct a symmetric situation, it is better to operate PnP_nPn and make Pn=P1P_n = P_1Pn=P1, because this can take out the most free stones, namely Pn−P1− 1P_n-p_1 -1Pn−P1−1 stones, put P2,P4… , Pn – 1 p_2, P_4,… ,P_{n-1}P2,P4,… ,Pn−1, such that P2=P3P_2 = P_3P2=P3, P4=P5P_4 = P_5P4=P5,… Pn−2=Pn−1P_{n-2} = P_{n-1}Pn−2=Pn−1.
To meet the preceding requirements, ensure that Pn−P1>P3−P2+… +Pn−1−Pn− 2P_n-p_1 \gt P3-P_2 +… + P_ {}, n – 1 – P_ {2} n – Pn – P1 > P3 – P2 +… + Pn – Pn – 2-1
Pn+Pn−2+… + Pn + P2 > Pn – 1-3 + P1P_n + P_ {2} n – +… + P_2 > P_ {}, n – 1 + P_ {n – 3} + P_1Pn + Pn – 2 +… + Pn + P2 > Pn – 1-3 + P1
To sum up, when NNN is even, if the above requirements are met, it is a sure win situation; otherwise, it is a sure lose situation.
To explain the above formula: since PPP is monotonically increasing, the left-hand side of the inequality will only be greater than or equal to the right-hand side, and only in symmetric situations will both sides be equal. Therefore, when NNN is even, the symmetric situation is a losing situation, and the asymmetric situation is a winning situation.
If NNN is odd, PPP is still a monotone increasing sequence, as long as:
By manipulating PnP_nPn, the first hand allows the second hand to enter a symmetrical situation.
By transposing the above equation:
Since PPP is a monotone increasing sequence, the above formula is always true. So if NNN is odd, first hand wins.
The thought process is a bit cumbersome and the code is very simple
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(a) {
int n;
int seq[10];
while(scanf("%d", &n) ! = EOF && n) {for (int i = 0; i < n; i++) {
scanf("%d", seq + i);
}
if (n & 1) {
puts("1");
} else {
sort(seq, seq+n);
bool flag = true;
for (int i = 0; i < n && flag; i += 2) {
if(seq[i] ! = seq[i+1]) {
flag = false; }}if (flag) {
puts("0");
} else {
puts("1"); }}}return 0;
}
Copy the code