Coin Game

시간 제한90초메모리 제한2048 MB

요약
매 턴 네 가지 회전 중 하나를 골라 500번 움직인 뒤 x좌표를 음수로 만드는 게임이다.
난이도

어려움10점 중 9점

유형
게임 이론, 수학, 시뮬레이션, 그리디
정답자
아직 제출이 없습니다

문제

Now it's time to play a real game! But, I don't have anything but just one little coin. So, let's do something fun with it!

This isn't just any ordinary coin; it bears a unique image allowing me to interpret its rotational angle with remarkable ease. By selecting a specific point on this coin's face, I can draw an arrow from the center to that point. Intrigued? I thought you would be! Let's set the stage for our game.

Imagine this: I place the coin right at the origin on a two-dimensional coordinate plane, poised to face along the positive OyOy axis. The game is turn-based. On each turn, the active player will rotate the coin by one of the four predetermined angles, then advance it by 1 unit in the direction defined by the arrow.

The game lasts for 500500 full moves (500500 turns for one player and 500500 for the other). After all moves, you win if the xx coordinate of the coin is negative, and I win otherwise.

The rotation options available depend on the current coordinates of the coin (x,y)(x, y) and are computed with the following formulas:

  1. α_1=x2+y2+x2+A⋅∣x∣\alpha\_1 = \sqrt{x^2 + y^2} + x^2 + A \cdot |x|
  2. α_2=x2+y2−x2−B⋅∣x∣\alpha\_2 = \sqrt{x^2 + y^2} - x^2 - B \cdot |x|
  3. α_3=x2+y2+y2+C⋅∣y∣\alpha\_3 = \sqrt{x^2 + y^2} + y^2 + C \cdot |y|
  4. α_4=x2+y2−y2−D⋅∣y∣\alpha\_4 = \sqrt{x^2 + y^2} - y^2 - D \cdot |y|

Here, AA, BB, CC, and DD are some constants established before the game begins.

Excited yet? What's that? You're unsure about how to conquer this challenge? You think just because I conceived this game, I have all the strategies figured out? Fear not! I'll grant you a small advantage: I'll make my moves in the blink of an eye.

힌트

The example is provided to demonstrate the format of input and output. In the actual validation of the solution, players will make 500500 moves and the jury's program will output all numbers with a precision of 1818 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);
}

예제1

  1. 예제 1

    입력
    1
    1 1 1 1
    0.00 0.00 1.57
    1
    0.00 1.00 1.57
    
    -0.84 1.54 2.57
    1
    0.08 1.14 5.88
    
    0.76 1.88 0.82
    2
    0.82 2.88 1.51
    
    -0.18 3.00 3.02
    1
    0.82 2.94 6.22
    
    0.37 3.84 2.04
    4
    1.37 3.74 -0.10
    
    
    예상 출력
    
    
    
    1
    
    
    
    1
    
    
    
    2
    
    
    
    3
    
    
    
    3