Submission #1574343
Source Code Expand
First consider an easier version of problem: we don’t divide the integers by their GCD. In this case, obviously the answer only depends on the parity of the total number of stones. The original problem also has something to do with parities.Suppose that in your turn all integers are odd. If all integers are one, you can’t perform any operations and you lose. If not, you can perform an operation, and after the operation exactly one integer is even and the others are odd (here the GCD doesn’t matter - since GCD is odd in this case, it doesn’t change the parities). However, if your opponent perform an operation on the only even number, you will again face the situation where all numbers are odd, and you will lose eventually.If exactly one integer in your turn is even, you can always win. By performing an operation in the only even number, you can force the opponent to lose (as described above).By similar observations, we get the following:1. In case there are odd number of even integers, you win. Your strategy is as follows. In your turn you choose one of even numbers and perform an operation on it. After the operation there will be two or more odd integers, so the GCD operation doesn’t change the parities. Thus, in the opponent’s turn there will be even number of even integers,and in your next turn you will again have odd number of even integers. By repeating this strategy, you always win.2. In case there are even number of even integers and two or more odd integers, you lose.No matter what you do, after your operation the opponent will be given a winning state,as described above.3. In case there are even number of even integers and exactly one odd integer. In this case, it’s clear that if you perform an operation on one of even integers, you lose (your opponent will face a winning state). Thus, you must perform an operation on the odd integer, and after that divide all integers by their GCD. It’s not clear what happens in this case - just simulate the game and solve the problem recursivelyWhen the simulation happens, all the integers are divided by at least two. Thus, the number of simulations is O(log(max Ai)). The time complexity of the algorithm above is O(N log(max Ai)
Submission Info
Submission Time | |
---|---|
Task | D - Decrementing |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2226 Byte |
Status | CE |
Compile Error
./Main.cpp:1:1: error: stray ‘\342’ in program First consider an easier version of problem: we don’t divide the integers by their GCD. In ^ ./Main.cpp:1:1: error: stray ‘\200’ in program ./Main.cpp:1:1: error: stray ‘\231’ in program ./Main.cpp:3:1: error: stray ‘\342’ in program original problem also has something to do with parities.Suppose that in your turn all integers are odd. If all integers are one, you can’t perform any ^ ./Main.cpp:3:1: error: stray ‘\200’ in program ./Main.cpp:3:1: error: stray ‘\231’ in program ./Main.cpp:5:1: error: stray ‘\342’ in program one integer is even and the others are odd (here the GCD doesn’t matter - since GCD is odd ^ ./Main.cpp:5:1: error: stray ‘\200’ in program ./Main.cpp:5:1: error: stray ‘\231’ in program ./Main.cpp:6:1: error: stray ‘\342’ in program in this case, it doesn’t change the parities). However, if your opponent perform an operation ^ ./Main.cpp:6:1: error: stray ‘\200’ in program ./Main.cpp:6:1: error: stray ‘\231’ in program ./Main.cpp:11:1: ...