cho.sh

Token and Dice

무한 격자 위의 토큰을 (0, 0)으로 옮기는 상호작용 문제로, 매 단계마다 새로 주어지는 주사위를 받을지 버릴지 정하고 주사위 합에 맞는 거리만큼 이동한다.

보통4시뮬레이션구현확률수학아직 제출이 없습니다시간 제한8초메모리 제한256 MB

문제

This is an interactive problem.

There is an infinite grid. A token is placed in the square (x,y)(x, y). You are to put it in the square (0,0)(0, 0) following certain rules.

The possible moves are determined by a dice roll. Initially, you have one die which has the number 11 on each of its six sides.

Each move consists of the following steps:

  1. At the beginning, you are offered a completely new six-sided die, and each side contains an integer from 11 to 10,00010\\,000. Each integer is chosen randomly, equiprobably from the range given above, and independently from others.
  2. After that, you have to decide whether to take the new die or throw it away. If you take the die, you have it for all the subsequent steps.
  3. The jury rolls all the dice you have. On each die, one of the six sides is selected equiprobably and independently from other dice. The sum of all numbers on the dice is denoted by ss.
  4. You must move the token from its current square (x_1,y_1)(x\_1, y\_1) to another square (x_2,y_2)(x\_2, y\_2) which should satisfy one of the following conditions: ⌊(x_1−x_2)2+(y_1−y_2)2⌋=sor⌈(x_1−x_2)2+(y_1−y_2)2⌉=s\left\lfloor \sqrt{(x\_1 - x\_2)^2 + (y\_1 - y\_2)^2} \right\rfloor = s \hspace{0.3cm}\mathbf{or}\hspace{0.3cm} \left\lceil \sqrt{(x\_1 - x\_2)^2 + (y\_1 - y\_2)^2} \right\rceil = s