#P13028. [GCJ 2021 #1A] Hacked Exam

    ID: 12817 Type: RemoteJudge 30000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>动态规划 DP2021Special Judge组合数学期望Google Code Jam

[GCJ 2021 #1A] Hacked Exam

题目描述

There is an exam with Q\mathbf{Q} true or false questions. The correct answer to each question is either T\mathsf{T} or F\mathsf{F}. Each student taking the exam selects either T\mathsf{T} or F\mathsf{F} for each question, and the student's score is the number of questions they answer correctly.

There are N\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, T\mathbf{T}. T\mathbf{T} test cases follow. The first line of each test case contains two integers N\mathbf{N} and Q\mathbf{Q}: the number of students and the number of questions, respectively. Each of the next N\mathbf{N} lines contains a string Ai\mathbf{A}_i and an integer Si\mathbf{S}_i: the ii-th student's answers and their score, respectively. The jj-th character of Ai\mathbf{A}_i is either T\mathsf{T} or F\mathsf{F}, representing the answer the ii-th student gave to the jj-th question.

输出格式

For each test case, output one line containing Case #x: y z/w, where xx is the test case number (starting from 1), yy is a string representing a sequence of answers that yields the maximum expected score (in the same format as the input), and zw\frac{z}{w} is the maximum expected score as an irreducible fraction (that is, ww 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 FFT\mathsf{FFT} is 3, the sequence of correct answers must be FFT\mathsf{FFT}.

In Sample Case #2, given that the score for FFT\mathsf{FFT} is 2, the sequence of correct answers is FFF\mathsf{FFF}, FTT\mathsf{FTT}, or TFT\mathsf{TFT}, each with probability 13\frac{1}{3}. Your best strategy is to answer FFT\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 FTFTFT\mathsf{FTFTFT}.

In Sample Case #4, one of the questions' answer is T\mathsf{T} and the other one is F\mathsf{F}, but you do not know which is which. Answering TF\mathsf{TF} or FT\mathsf{FT} scores you 2 with probability 12\frac{1}{2} and 0 with probability 12\frac{1}{2}, yielding an expected score of 1. Answering FF\mathsf{FF} or TT\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 2642^{64} (the numerator in this case actually exceeds 2972^{97}).

Limits

  • 1T20211 \leq \mathbf{T} \leq 2021.
  • The length of Ai=Q\mathbf{A}_{\mathbf{i}}=\mathbf{Q}, for all ii.
  • Each character of Ai\mathbf{A}_{\mathbf{i}} is an uppercase T\mathsf{T} or an uppercase F\mathsf{F}, for all ii.
  • 0SiQ0 \leq \mathbf{S}_{\mathbf{i}} \leq \mathbf{Q}, for all ii.
  • There exists at least one sequence of correct answers consistent with the input.

Test Set 1 (8 Pts, Visible Verdict)

  • 1N21 \leq \mathbf{N} \leq 2.
  • 1Q101 \leq \mathbf{Q} \leq 10.

Test Set 2 (6 Pts, Hidden Verdict)

  • 1N21 \leq \mathbf{N} \leq 2.
  • 1Q401 \leq \mathbf{Q} \leq 40.

Test Set 3 (25 Pts, Hidden Verdict)

  • 1N31 \leq \mathbf{N} \leq 3.
  • 1Q1201 \leq \mathbf{Q} \leq 120.