시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
30 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 0 | 0 | 0 | 0.000% |
There is an exam with Q true or false questions. The correct answer to each question is either T
or F
. Each student taking the exam selects either T
or F
for each question, and the student's score is the number of questions they answer correctly.
There are N students who have already taken this exam. For each of those students, you know the answers they gave to each question and their final score. Assuming that any sequence of answers that is consistent with all of those students' scores has the same probability of being the correct sequence of answers, you want to maximize your own expected score. Determine what that expected score is and how to answer the questions so that you achieve it.
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains two integers N and Q: the number of students and the number of questions, respectively. Each of the next N lines contains a string Ai and an integer Si: the i-th student's answers and their score, respectively. The j-th character of Ai is either T
or F
, representing the answer the i-th student gave to the j-th question.
For each test case, output one line containing Case #x: y z/w
, where x is the test case number (starting from 1), y is a string representing a sequence of answers that yields the maximum expected score (in the same format as the input), and z/w is the maximum expected score as an irreducible fraction (that is, w must be positive and of minimum possible value).
T
or an uppercase F
, for all i.4 1 3 FFT 3 1 3 FFT 2 2 6 FFTTTF 2 FTFTFT 4 2 2 FF 1 TT 1
Case #1: FFT 3/1 Case #2: FFT 2/1 Case #3: FTFFFT 4/1 Case #4: TF 1/1
In Sample Case #1, given that the score for FFT
is 3, the sequence of correct answers must be FFT
.
In Sample Case #2, given that the score for FFT
is 2, the sequence of correct answers is FFF
, FTT
, or TFT
, each with probability 1/3. Your best strategy is to answer FFT
, to achieve the expected score of 1/3×2+1/3×2+1/3×2=2.
In Sample Case #3, there are other answers that also achieve an expected score of 4, like FTFTFT
.
In Sample Case #4, one of the questions' answer is T
and the other one is F
, but you do not know which is which. Answering TF
or FT
scores you 2 with probability 1/2 and 0 with probability 1/2, yielding an expected score of 1. Answering FF
or TT
guarantees a score of 1. Since any sequence of answers gives the same expected score, you can output any of them.
1 3 120 FFTFFFTFFFTTTTTTTFTFFFFFFTTTFTFFFTFTFFTTFTFFTFFTTTFTFTFFTFTFTTFFFFTFTFFFFTTTFTTFTTTTFFFTTFFFFFTTFFTFFTFFTTTFFFFTTFFTFTTF 55 FFFTFFTTFFFFTFTFFTFFFTTTTTTFFFTTTFTTTTFFTFTTTFTTFFTTTFTFFFFTFFTTFFTTFTTFFTFTFFTFTTFTFTFFTTTFFTFTFTTFFTFTFTFTTFFTFFFTFTFT 62 FFFTFTTFFFFFTFTFTTTTTTFFTTFTFFFTFFTTTTTTFFFTTTFFFTTFTFFFFFFTFTTFFTFTTTFTTTTFTTFFFFTFFTTFTFFTTTTTTFTFFFFFTTFFTFTFTFFTTTTT 64
Case #1: FFFTFTTTFFFFTFTFFTFTTTTTTTFFFFTTTFTTTTFFTFTTTTTFFFTFTFTFFFFTFFTTFTFTFTTTTTFFTFFFFFFFFTTFTTTTTTFTTTTFFFFTFTFTTFTFFFFTTTFT 189154508532118369075350624633/2901503505434414233388602018
In the Sample Case for Test Set 3, you can get an expected score over 65, which is higher than the actual score of any of the other students. Notice that both the numerator and denominator of the expected score can be significantly larger than 264 (the numerator in this case actually exceeds 297).
Contest > Google > Code Jam > Google Code Jam 2021 > Round 1A C번