#P13028. [GCJ 2021 #1A] Hacked Exam
[GCJ 2021 #1A] Hacked Exam
题目描述
There is an exam with true or false questions. The correct answer to each question is either or . Each student taking the exam selects either or for each question, and the student's score is the number of questions they answer correctly.
There are 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, . test cases follow. The first line of each test case contains two integers and : the number of students and the number of questions, respectively. Each of the next lines contains a string and an integer : the -th student's answers and their score, respectively. The -th character of is either or , representing the answer the -th student gave to the -th question.
输出格式
For each test case, output one line containing Case #x: y z/w
, where is the test case number (starting from 1), is a string representing a sequence of answers that yields the maximum expected score (in the same format as the input), and is the maximum expected score as an irreducible fraction (that is, must be positive and of minimum possible value).
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
1
3 120
FFTFFFTFFFTTTTTTTFTFFFFFFTTTFTFFFTFTFFTTFTFFTFFTTTFTFTFFTFTFTTFFFFTFTFFFFTTTFTTFTTTTFFFTTFFFFFTTFFTFFTFFTTTFFFFTTFFTFTTF 55
FFFTFFTTFFFFTFTFFTFFFTTTTTTFFFTTTFTTTTFFTFTTTFTTFFTTTFTFFFFTFFTTFFTTFTTFFTFTFFTFTTFTFTFFTTTFFTFTFTTFFTFTFTFTTFFTFFFTFTFT 62
FFFTFTTFFFFFTFTFTTTTTTFFTTFTFFFTFFTTTTTTFFFTTTFFFTTFTFFFFFFTFTTFFTFTTTFTTTTFTTFFFFTFFTTFTFFTTTTTTFTFFFFFTTFFTFTFTFFTTTTT 64
Case #1: FFFTFTTTFFFFTFTFFTFTTTTTTTFFFFTTTFTTTTFFTFTTTTTFFFTFTFTFFFFTFFTTFTFTFTTTTTFFTFFFFFFFFTTFTTTTTTFTTTTFFFFTFTFTTFTFFFFTTTFT 189154508532118369075350624633/2901503505434414233388602018
提示
Sample Explanation
In Sample Case #1, given that the score for is 3, the sequence of correct answers must be .
In Sample Case #2, given that the score for is 2, the sequence of correct answers is , , or , each with probability . Your best strategy is to answer , to achieve the expected score of $\frac{1}{3} \times 2 + \frac{1}{3} \times 2 + \frac{1}{3} \times 2 = 2$.
In Sample Case #3, there are other answers that also achieve an expected score of 4, like .
In Sample Case #4, one of the questions' answer is and the other one is , but you do not know which is which. Answering or scores you 2 with probability and 0 with probability , yielding an expected score of 1. Answering or guarantees a score of 1. Since any sequence of answers gives the same expected score, you can output any of them.
Sample 2 fits the limits of Test Set 3. It will not be run against your submitted solutions.
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 (the numerator in this case actually exceeds ).
Limits
- .
- The length of , for all .
- Each character of is an uppercase or an uppercase , for all .
- , for all .
- There exists at least one sequence of correct answers consistent with the input.
Test Set 1 (8 Pts, Visible Verdict)
- .
- .
Test Set 2 (6 Pts, Hidden Verdict)
- .
- .
Test Set 3 (25 Pts, Hidden Verdict)
- .
- .