싸이버거와 대회 참가자간의 매칭을 계산하는 것은 꽤나 복잡한 작업이다. 관련하여, 제비뽑기라 불리우는 heuristic decision processing이 앞선 상황 등에서 효율적일 때가 많으며 일례로 '사다리타기 게임'을 떠올릴 수 있겠다.
가장 일반적인 형태의 '사다리타기 게임' 규칙은 이렇다: 평면 위에 참가자의 수만큼 세로줄을 평행하게 긋고, 인접한 세로줄 사이에 가로줄들을 무작위로 긋는다. 이후 각 참가자들은 배정된 세로줄의 위에서부터 아래로 이동하되 가로줄을 만날 때마다 그 인접 세로줄로 넘어간다. 최종 결과는 각 세로줄의 바닥에 위치한다.
우리는 정말로 위의 규칙으로부터 각 참가자들에 대해 확률적으로 균일한 결과를 기대할 수 있을까? 참가자와 세로줄의 배열 순서에 따른 분포 편향은 없는가? 또 만일 참가자들이 세로줄을 직접 선택할 수 있다면? 혹은 완벽히 제삼자가 되어야할 가로줄을 긋는 인물이 누군가의 부정한 청탁을 받아들인다면?
이에 rootenter는 보다 공정하면서도 그 결과의 예측 가능성을 배제할 아래와 같은 '공평한 사다리타기 게임'을 제안한다.
하지만 rootenter는 자신이 고안한 게임의 정당성을 증명해야한다. 그의 주장에 따르면 '공평한 사다리타기 게임'의 정당성을 보이는 과정에서 다음의 값을 계산해보는 것이 도움이 될 것이라 한다:
대충 임의의 참가자가 사다리를 타고 내려왔을 때 여전히 출발했을 때의 세로줄에 있을 확률을 알면 좋을것같은뎅슝
그러고는 그 작업을 당신에게 떠넘긴다.
입력은 다음과 같은 형식으로 주어진다.
개의 정수를 한 줄에 공백으로 구분하여 출력한다.
번째 정수는 일 때 출발 세로줄과 도착 세로줄이 같은 참가자 수의 기댓값을 으로 나눈 나머지에 해당한다.
기댓값이 유리수 이고 라면, 그 값을 으로 출력한다.
| 3 | 20 | 은 의 거듭제곱이다. |
| 4 | 22 | . |
| 5 | 33 | 추가적인 제약조건이 없다. |
