#P9755. 考试

    ID: 6385 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-固定一个变量消去另一维暴力枚举乘法原理Pascal 递推对称性分析期望线性性欧几里得算法

考试

题目描述

一份考试有 qq 道判断题,答案用 T 或 F 表示,答对一题得 11 分,答错得 00 分。已有 nn 人交卷,你知道每个人的答案串和总分。数据保证至少存在一份与所有已知总分一致的标准答案。假定标准答案在所有这样的答案串中等概率选取。

请输出一份期望得分最高的答案,并以最简分数表示该期望得分。存在多个最优答案时,可以输出其中任意一个。

输入格式

第一行一个正整数 TT,表示数据组数。

每组数据的第一行是两个正整数 n,qn,q。接下来 nn 行,每行包含一个长度为 qq、只含 T 和 F 的字符串,以及该答案的总分 ss。

输出格式

每组数据输出一行。先输出一个长度为 qq 的答案串,再输出一个最简分数,两者以空格隔开。

样例

4
1 3
FFT 3
1 3
FFT 2
2 6
FFTTTF 2
FTFTFT 4
2 2
FF 1
TT 1
FFT 3/1
FFT 2/1
FTFFFT 4/1
TF 1/1

样例 2

输入 · 输出

数据范围与计分

对于全部数据,1≤T≤20211\le T\le2021,0≤s≤q0\le s\le q。

测试点 nn qq 分值
1 1≤q≤1201\le q\le120 10
2 1≤n≤21\le n\le2 1≤q≤101\le q\le10 20
3 1≤q≤401\le q\le40
4 1≤n≤31\le n\le3 1≤q≤1201\le q\le120 50

若一个测试点内每组数据都至少答对构造和期望两项中的一项,可以获得该测试点的 20% 分值。保持所有行的输出格式正确。

原题 PDF