本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn

1357. Hold or Continue?


Description

Pig is a simple dice game for two or more players. Each turn, a player repeatedly rolls a dice until either a 1 is rolled or the player decides to "hold":

  • If the player rolls a 1, they score nothing in their turn and it becomes the next player's turn.
  • If the player rolls any other number, it is added to their turn total and the player can decide between "hold" or "continue".
  • If the player chooses to "hold", their turn total is added to their score and it becomes the next player's turn. Otherwise the player continues rolling the dice.

The  first player to score exactly 75 wins the game. If a player's score plus their turn total exceeds 75, they score nothing in their turn and it becomes the next player's turn.

Catelyn Tully is playing Pig with her father Hoster. If Catelyn begins her turn rolling a 5, she could hold and score 5 during her turn. If she chooses to continue and rolls a 2, she could hold and score 7. If she chooses again to continue and rolls a 1, she must end her turn without scoring. If at his turn Hoster rolls the sequence 4-5-3-5-5 and then he chooses to hold, he adds his turn total of 22 to his current score (unless the sum exceeds 75). Then Catelyn rolls the dice again, and so on, until one of them scores exactly 75.

Hoster  finds the game very didactic and he became a pretty good player. After playing several times with Catelyn, he realized that she is very impulsive and continues rolling the dice more times than she should. Catelyn would like to improve the way she plays, but unfortunately Hoster doesn't have too much patience to teach her, so she needs your help. While playing with her father, Catelyn has to decide several times whether to hold or continue, and sometimes she is not sure about what to do. Can you advise her so that each decision maximizes her winning probability?

Input

The  first line contains an integer \$Q (1 \leq Q \leq 1000)\$ indicating the number of questions on which Catelyn wants your advice. Each of the next \$Q\$ lines describes a question with three integers \$C, H\$ and \$X (0 \leq C,H \leq 73, X \geq 2, C +X \leq 75)\$, representing respectively Catelyn's current score, Hoster's current score, and Catelyn's turn total (sum of the rolls of the dice during her turn).

Output

Output \$Q\$ lines, each line with a character indicating the decision Catelyn must make for the corresponding question of the input, so as to maximize her winning probability if both Catelyn and Hoster play optimally. For each question, the character must be the uppercase letter "H" if the optimal decision is to hold, or the uppercase letter "C" if the optimal decision is to continue. It is guaranteed that the optimal decision can be clearly differentiated; this means that \$| ph - pc| > 10^{-5}\$, where \$p_h\$ is the winning probability if Catelyn decides to holdd,and \$pc\$ is the winning probability if she decides to continue (\$0 \leq p_h, p_c \leq 1\$).

Samples

Input Copy
3
15 0 3
35 50 40
15 0 30
Output
C
H
H

Source

ICPC Latin American Regional 2019
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 64MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1039. ICPC Latin American Regional 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register