18036번 - Hold or Continue? 다국어

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?

The first line contains an integer Q (1 ≤ Q ≤ 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 ≤ C, H ≤ 73, X ≥ 2, C + X ≤ 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 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 |p_h − p_c| > 10⁻⁵ , where ph is the winning probability if Catelyn decides to hold, and pc is the winning probability if she decides to continue (0 ≤ p_h, p_c ≤ 1).