P13028 [GCJ 2021 #1A] Hacked Exam

There is an exam with $\mathbf{Q}$ true or false questions. The correct answer to each question is either $\mathsf{T}$ or $\mathsf{F}$. Each student taking the exam selects either $\mathsf{T}$ or $\mathsf{F}$ for each question, and the student's score is the number of questions they answer correctly.  There are $\mathbf{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, $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains two integers $\mathbf{N}$ and $\mathbf{Q}$: the number of students and the number of questions, respectively. Each of the next $\mathbf{N}$ lines contains a string $\mathbf{A}_i$ and an integer $\mathbf{S}_i$: the $i$-th student's answers and their score, respectively. The $j$-th character of $\mathbf{A}_i$ is either $\mathsf{T}$ or $\mathsf{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 $\frac{z}{w}$ is the maximum expected score as an irreducible fraction (that is, $w$ must be positive and of minimum possible value).

**Sample Explanation** In Sample Case #1, given that the score for $\mathsf{FFT}$ is 3, the sequence of correct answers must be $\mathsf{FFT}$. In Sample Case #2, given that the score for $\mathsf{FFT}$ is 2, the sequence of correct answers is $\mathsf{FFF}$, $\mathsf{FTT}$, or $\mathsf{TFT}$, each with probability $\frac{1}{3}$. Your best strategy is to answer $\mathsf{FFT}$, 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 $\mathsf{FTFTFT}$. In Sample Case #4, one of the questions' answer is $\mathsf{T}$ and the other one is $\mathsf{F}$, but you do not know which is which. Answering $\mathsf{TF}$ or $\mathsf{FT}$ scores you 2 with probability $\frac{1}{2}$ and 0 with probability $\frac{1}{2}$, yielding an expected score of 1. Answering $\mathsf{FF}$ or $\mathsf{TT}$ 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 $2^{64}$ (the numerator in this case actually exceeds $2^{97}$). **Limits** - $1 \leq \mathbf{T} \leq 2021$. - The length of $\mathbf{A}_{\mathbf{i}}=\mathbf{Q}$, for all $i$. - Each character of $\mathbf{A}_{\mathbf{i}}$ is an uppercase $\mathsf{T}$ or an uppercase $\mathsf{F}$, for all $i$. - $0 \leq \mathbf{S}_{\mathbf{i}} \leq \mathbf{Q}$, for all $i$. - There exists at least one sequence of correct answers consistent with the input. **Test Set 1 (8 Pts, Visible Verdict)** - $1 \leq \mathbf{N} \leq 2$. - $1 \leq \mathbf{Q} \leq 10$. **Test Set 2 (6 Pts, Hidden Verdict)** - $1 \leq \mathbf{N} \leq 2$. - $1 \leq \mathbf{Q} \leq 40$. **Test Set 3 (25 Pts, Hidden Verdict)** - $1 \leq \mathbf{N} \leq 3$. - $1 \leq \mathbf{Q} \leq 120$.