Coin Game
Time limit90sMemory limit2048 MB
Players alternately turn a coin by one of four angles and step it 1 unit forward for 500 moves; you win if the final x is negative.
- Level
Hard8 of 10
- Topics
- Game theory, Geometry, Simulation
- Solved
- No attempts yet
Statement
Now it is time to play a real game! But I have nothing except one small coin. So let's do something fun with it.
This is no ordinary coin. It has a special picture that lets me read its rotation angle easily. Pick a point on the coin's face, and you can draw an arrow from the center to that point. Intrigued? I thought you would be. Let's set up the game.
Place the coin at the origin of a two-dimensional coordinate plane, facing the positive axis. The game is turn-based. On each turn, the active player rotates the coin by one of four predetermined angles, then advances it by 1 unit in the direction of the arrow.
The game lasts for 500 full moves, meaning 500 turns for one player and 500 for the other. After all moves, you win if the x coordinate of the coin is negative. Otherwise, I win.
The rotation options depend on the current coordinates and are computed as follows.
Here , , , and are constants set before the game begins.
Not sure how to beat this? You think that because I invented the game, I have every strategy worked out? Don't worry. I'll grant you a small advantage: I'll make my moves in the blink of an eye.
Hint
The example shows the input and output format. In the actual judging, players make 500 moves, and the jury's program prints every number with 18 decimal places.
To avoid precision issues, you may use the coin-moving function from the jury's program:
double pi = acos(-1.);
void rotate_and_move(double &x, double &y, double &a, int type) {
double diff = 0;
double s = sqrt(x * x + y * y);
if (type == 1) diff = s + x * x + A * fabs(x);
if (type == 2) diff = s - x * x - B * fabs(x);
if (type == 3) diff = s + y * y + C * fabs(y);
if (type == 4) diff = s - y * y - D * fabs(y);
a += diff;
a = fmod(a, 2 * pi);
x += cos(a);
y += sin(a);
}