Left-Right-Win
시간 제한2초메모리 제한512 MB
원탁에 둘러앉은 참가자들이 왼쪽 이동, 오른쪽 이동, 승리 확률이 주어진 스피너를 돌릴 때 각자가 차지할 상금 $100의 기여금을 계산한다.
문제
Left-Right-Win 게임은 n명의 플레이어가 둘러앉아 진행하며, 돌림판*은 확률 P_left로 Left, 확률 P_right로 Right, 확률 1 – P_left – P_right로 Win을 반환한다.
게임은 시작 플레이어(그림에서 0번, 나머지 플레이어는 시계 방향으로 1 .. (n-1)번)가 돌림판을 돌리면서 시작한다. 결과가 Win이면 그 플레이어가 상금(예: $100)을 가져간다. 결과가 Left이면 돌림판은 왼쪽 플레이어(1번)에게 넘어간다. 결과가 Right이면 돌림판은 오른쪽 플레이어((n-1)번)에게 넘어간다. 돌림판을 받은 플레이어는 같은 과정을 반복한다. 즉 이기거나 돌림판을 왼쪽 또는 오른쪽으로 넘긴다. 누군가 이길 때까지 게임은 계속된다. (이론적으로 게임이 영원히 계속될 수 있으므로, 2n턴이 지나면 하우스가 상금을 가져가는 식의 중단 규칙이 있다.)
왼쪽 그림은 P_left = 0.5, P_right = 0.4일 때 6명의 플레이어 각자가 이길 확률을 보여준다. 오른쪽 그림은 P_left = 0.1, P_right = 0.8일 때 6명의 플레이어 각자가 이길 확률을 보여준다.
3번 플레이어가 0번 플레이어만큼 많은 돈을 내고 게임에 참여하려 하지 않는다는 것은 분명하다. 각 플레이어는 자신이 상금을 가져갈 확률에 비례하는 금액을 상금에 보태기를 원한다(잠재적으로 무한한 게임). P_left와 P_right가 주어졌을 때 각 플레이어가 $100 상금에 얼마를 보태야 하는지 계산하는 프로그램을 작성하라.
계산은 배정밀도 부동 소수점으로 수행해야 한다.
* 돌림판은 여러 값 중 하나를 각 값에 지정된 확률로 반환하는 장치다. 원래 돌림판은 카드 위의 균형 잡힌 포인터와, 중심 둘레에 여러 결과가 적힌 호로 이루어져 있었다. 포인터를 돌려 멈춘 곳이 선택된 값이다. 호의 길이는 값의 확률에 비례한다. 돌림판은 어떤 난수 장치로도 대신할 수 있다. 예를 들어 P_left = 1/3, P_right = 1/3은 주사위 하나를 굴려 1이나 2가 나오면 Left, 3이나 4가 나오면 Right, 5나 6이 나오면 Win으로 정해 시뮬레이션할 수 있다.
입력
입력의 첫 줄에는 뒤따르는 데이터 세트의 수 P(1 ≤ P ≤ 100)가 십진 정수로 주어진다. 각 데이터 세트는 서로 독립적으로, 같은 방식으로 처리해야 한다.
각 데이터 세트는 공백으로 구분된 5개의 값이 있는 한 줄로 이루어진다. 데이터 세트 번호 K, 플레이어 수 n(십진 정수, 3 ≤ n ≤ 15), 기여 금액을 구할 플레이어의 번호 k(십진 정수, 0 ≤ k ≤ n-1), 그리고 두 부동 소수점 값 P_left와 P_right가 주어진다. (P_left+P_right ≥ 0.8)
모든 데이터 세트에서 상금은 $100이라고 가정한다.
출력
각 데이터 세트마다 출력은 한 줄이다. 출력 줄은 데이터 세트 번호 K, 공백 하나, 그리고 $100 상금에 대한 플레이어 k의 기여 금액을 달러 단위로 소수점 이하 두 자리까지(즉 달러와 센트) 나타낸 값으로 이루어진다.