시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
20 초 (추가 시간 없음) | 1024 MB | 0 | 0 | 0 | 0.000% |
The game of Tricky Trios is played using a deck of 3N cards consisting of three identical cards labeled 1, three identical cards labeled 2, and so on, up to three identical cards labeled N. The cards are shuffled (such that all possible card orderings have an equal probability of appearing), and then dealt out onto a table, face down, so that all the numbers are hidden.
Each round of the game proceeds as follows:
Note that you may choose to flip a card even if you already know its number. Also, even if you know the locations of all of the cards in a trio, you must actually flip all three cards in the trio on the same round in order to remove it.
You would like to win as quickly as possible, so you will use a strategy that minimizes the expected number of rounds needed to end the game. What is that expected number of rounds?
The first line of the input gives the number of test cases, T; T test cases follow. Each consists of one line with an integer N, as described above.
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is a rational: the minimal expected number of rounds needed to end the game, as described above. y
will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer.
3 1 2 5
Case #1: 1.000000 Case #2: 3.400000 Case #3: 9.842024
In Sample Case #1, all three cards have the same number, so flipping them over in any order will end the game in one round.
In Sample Case #2:
The answer is 3 × 1/5 + 4 × 2/5 + ... = 17/5.
Contest > Google > Code Jam to I/O for Women > Code Jam to I/O for Women 2018 > Code Jam to I/O for Women 2018 D번