홀드할까, 계속할까?
시간 제한2초메모리 제한512 MB
각 질의에서 캐틀린의 점수, 호스터의 점수, 현재 턴 합계가 주어질 때, 두 사람이 최적으로 플레이한다고 가정하고 캐틀린의 승률을 최대화하는 선택이 홀드인지 계속인지 판정한다.
문제
Pig는 두 명 이상이 즐기는 간단한 주사위 게임이다. 각 턴에서 플레이어는 1이 나오거나 스스로 "홀드"를 선언할 때까지 주사위를 계속 굴린다.
- 주사위에서 1이 나오면 그 턴에는 아무 점수도 얻지 못하고 다음 플레이어의 턴이 된다.
- 1이 아닌 다른 숫자가 나오면 그 숫자를 턴 합계에 더하고, 플레이어는 "홀드"와 "계속" 중 하나를 선택할 수 있다.
- "홀드"를 선택하면 턴 합계를 자신의 점수에 더하고 다음 플레이어의 턴으로 넘어간다. 그렇지 않으면 주사위를 계속 굴린다.
점수가 정확히 75가 되는 첫 번째 플레이어가 승리한다. 플레이어의 점수와 턴 합계를 더한 값이 75를 초과하면 그 턴에는 아무 점수도 얻지 못하고 다음 플레이어의 턴이 된다.
Catelyn Tully는 아버지 Hoster와 Pig를 하고 있다. Catelyn이 턴을 시작해 5를 굴렸다면 홀드해서 그 턴에 5점을 얻을 수 있다. 계속하기를 선택해 2를 굴렸다면 홀드해서 7점을 얻을 수 있다. 다시 계속하기를 선택해 1을 굴렸다면 점수 없이 턴을 끝내야 한다. Hoster가 자신의 턴에서 4-5-3-5-5를 연속으로 굴린 뒤 홀드를 선택하면, 턴 합계 22를 현재 점수에 더한다(단, 합이 75를 초과하는 경우는 제외). 그다음 Catelyn이 다시 주사위를 굴리고, 둘 중 하나가 정확히 75점을 얻을 때까지 이어진다.
Hoster는 이 게임이 교육적이라고 생각하며 꽤 능숙한 플레이어가 되었다. Catelyn과 여러 번 겨루면서 그녀가 매우 충동적이어서 필요 이상으로 주사위를 굴린다는 사실을 깨달았다. Catelyn은 자신의 플레이를 개선하고 싶지만 Hoster는 그녀를 가르칠 만큼 인내심이 많지 않아 여러분의 도움이 필요하다. 아버지와 게임을 하면서 Catelyn은 홀드할지 계속할지 여러 번 결정해야 하고, 때로는 무엇을 해야 할지 확신하지 못한다. 각 결정이 승리 확률을 최대로 만들도록 그녀에게 조언해 줄 수 있는가?
입력
첫 번째 줄에는 정수 Q (1 ≤ Q ≤ 1000)가 주어지며, 이는 Catelyn이 조언을 구하는 질문의 수이다. 다음 Q개 줄은 각각 세 정수 C, H, X (0 ≤ C, H ≤ 73, X ≥ 2, C + X ≤ 75)로 하나의 질문을 나타내며, 각각 Catelyn의 현재 점수, Hoster의 현재 점수, Catelyn의 턴 합계(그녀의 턴 동안 나온 주사위 눈의 합)이다.
출력
Q개 줄을 출력하며, 각 줄에는 Catelyn과 Hoster가 모두 최적으로 플레이할 때 승리 확률을 최대로 만들기 위해 해당 질문에서 Catelyn이 내려야 할 결정을 나타내는 문자를 출력한다. 각 질문에 대해 최적의 결정이 홀드라면 대문자 "H"를, 계속이라면 대문자 "C"를 출력한다. 최적의 결정은 명확히 구분됨이 보장된다. 즉, |ph − pc| > 10−5이며, 여기서 ph는 Catelyn이 홀드할 때의 승리 확률, pc는 계속할 때의 승리 확률이다 (0 ≤ ph, pc ≤ 1).