|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
The Avengers are still bored on their way to the Collector’s hiding place, and are continuing to play Shut the Box. Unfortunately for Dr. Banner, the strategy that he was using with your help is not turning out to be a very good one, and he is losing most of the games. He is halfway to transforming into the Hulk, and you need to calm him down by finding the best move at any given point, defined to be the one that maximizes the probability of eventually shutting the box.
Assume that the dice are fair (i.e., with two dice, all of the 36 possibilities are equally likely). Keep in mind the twist mentioned earlier: when the total of the open cards is ≤ 6, only one die is used.
For example, say the current open cards are: 1, 2, and 3, and the rolled total = 3. There are 2 moves:
The first line in the test data file contains the number of test cases (< 100). After that, each line contains one test case: the first entry on each line is the rolled total (called target), and the next entry is the number of open cards n. The following n entries denote the open cards in the ascending order.
For each test case, you are to output the move that maximizes the probability of eventually shutting the box, or output that there is no legal move. If there is a move, you also need to list out the probability of shutting the box moving forward. The exact form is shown below.
4 3 3 1 2 4 3 3 1 2 3 6 3 1 2 3 8 4 1 2 3 9
The best move is: 1 2, and probability of shutting = 0.1667 The best move is: 3, and probability of shutting = 0.2222 The best move is: 1 2 3, and probability of shutting = 1 No move found.