配点 : 100 点
問題文
兔子是 它有一个矩形网格 50 正打算参加由若干题目组成的考试。每道题都是四选一题,0, 1, 2, 3 四个选项中有一个是正确答案,其余都是错误答案。
在兔子参加考试之前,30 若干条鳗鱼已经参加了完全相同的考试。每条鳗鱼答题的方法如下 3 中的某一种类型,并且已知每种类型的鳗鱼数量相同,为 10 条。
- 对每道题都独立地,2/3 的概率选择正确答案,1/3 的概率选择一个错误答案。在选择错误答案时,每个错误答案被选中的概率相同。
- 对每道题都独立地,1/3 的概率选择正确答案,2/3 的概率选择一个错误答案。在选择错误答案时,每个错误答案被选中的概率相同。
- 对每道题都独立地,4 从选项中以相等的概率选择一个。
问题是用鳗鱼语写的,兔子无法靠自己解答问题。因此,兔子通过超能力作弊,获得了所有鳗鱼的答案。不过,不清楚哪些鳗鱼属于上述 3 类型中的哪一种。请仅根据获得的信息,尽可能多地猜出正确答案。
採点
1 每组输入数据正好给出 200 个测试用例。1 每个测试用例对应一次考试。
对于每次考试,输出的答案中如果错误答案是 3 個以下则视为合格,否则视为不合格。
在此基础上,1 在输入数据中包含的 200 个考试中 90% 以上合格 (即 180 如果通过了超过该数量的测试,该数据将被视为正确。
输入数据有 10 个,如果能对所有输入数据做出正确回答 100 点。 如果所有满足
每次测试的输入数据是在随机均匀选择正确答案之后,再随机均匀选择鳗鱼类型生成的。更具体的生成方法请参见页面下方。不过,由于可以通过不依赖具体生成方法的解法获得 100 分数,因此不一定需要阅读页面下方的信息,而且即使阅读,也不一定能获得解决这个问题的有用信息。
入力
输入是按以下格式从标准输入给出的。
A_{1,1} A_{1,2} ... A_{1,50}
A_{2,1} A_{2,2} ... A_{2,50}
:
A_{30,1} A_{30,2} ... A_{30,50}
(ここまでが 1 個の試験に対応しており,以下同様の形式の入力がさらに 199 個与えられる)
这里 A_{i,j} 是 您也可以写 i 对应第几条鳗鱼的 j 问题的回答,0, 1, 2, 3 的其中之一.
出力
200 行输出。i (1 \leq i \leq 200) 行 i 输出第几个考试的答案。
每个考试的答案用空格分隔 50 个整数(0, 1, 2, 3 之一)输出。j (1 \leq j \leq 50个整数对应于 j 题问题的回答。
入力例 1
0 2 2 0 0 0 2 1 1 3 1 1 3 3 1 2 2 1 3 0 1 0 1 2 1 3 3 0 0 1 1 1 3 2 1 2 0 2 2 1 2 3 2 0 2 2 2 0 3 3 0 3 3 1 2 3 0 0 2 0 0 2 3 1 2 0 3 2 0 2 2 1 1 2 3 0 1 2 2 0 3 3 0 2 0 3 1 2 2 1 0 3 1 1 1 0 2 1 3 1 3 2 1 0 1 1 2 0 1 1 0 3 0 2 0 0 2 3 2 2 3 1 2 1 0 2 3 0 1 0 1 0 2 3 2 1 1 0 0 0 3 3 3 0 2 2 2 2 2 3 2 0 2 2 0 1 1 1 0 3 1 0 1 1 3 3 0 0 3 1 0 3 0 2 2 0 1 3 3 1 3 3 3 0 2 2 3 2 0 3 0 3 1 1 0 2 3 0 3 1 1 3 0 1 1 1 1 3 2 2 0 2 0 1 0 3 2 3 3 0 1 3 2 1 1 3 1 0 1 2 0 0 3 2 0 3 0 2 1 1 0 1 0 1 2 0 0 3 0 0 2 1 0 1 3 2 1 1 2 3 0 2 3 2 2 1 1 2 1 2 1 3 3 2 1 1 2 3 0 0 3 0 2 3 3 3 1 3 1 1 2 0 3 3 3 2 1 1 3 0 3 0 2 0 0 0 2 0 3 3 0 3 0 1 2 2 1 1 2 0 2 0 2 3 2 2 0 3 2 2 2 3 0 2 0 3 1 0 2 0 3 3 0 2 2 0 2 3 2 3 3 0 1 0 0 0 2 3 2 3 3 3 1 1 3 1 2 2 1 0 0 0 0 1 1 1 0 0 3 3 2 2 3 2 0 3 2 3 1 0 1 0 3 3 2 0 2 3 2 3 1 1 2 0 0 0 2 0 2 3 0 2 0 1 2 2 1 2 3 0 2 0 0 0 0 3 2 1 2 0 0 3 3 3 1 3 0 0 1 0 2 2 3 0 2 0 2 0 2 3 2 0 2 0 0 0 2 0 0 3 0 2 0 1 0 3 1 2 2 0 2 1 0 3 2 2 2 2 2 0 2 3 3 3 1 3 0 0 1 0 3 3 3 0 2 3 0 3 3 3 0 2 3 2 3 2 2 0 1 1 1 3 0 1 2 1 1 1 1 0 2 2 2 2 2 1 2 2 2 0 1 0 2 2 0 0 1 0 2 3 3 2 3 0 2 0 1 0 1 3 1 1 0 0 0 3 2 0 2 0 1 0 3 1 2 3 1 2 2 2 3 1 2 0 3 2 1 1 3 0 3 3 2 1 0 2 1 1 3 0 3 2 2 2 3 3 0 2 2 1 3 1 1 0 1 2 3 2 1 2 3 0 2 1 0 2 0 1 2 0 2 0 3 2 2 1 0 2 0 3 1 2 3 0 1 0 2 2 1 0 2 1 1 1 3 0 3 3 0 2 0 0 2 1 1 3 3 0 3 3 3 2 1 2 1 3 3 2 2 2 3 0 2 3 2 3 0 0 0 0 3 3 2 0 3 0 2 3 1 1 1 0 3 1 1 2 2 1 2 0 3 1 2 3 1 0 0 2 2 2 0 3 0 1 1 2 1 2 3 0 2 0 0 1 1 2 2 1 2 1 2 1 3 0 1 3 0 0 0 3 3 0 3 0 2 0 2 3 0 3 3 3 2 0 2 0 2 0 1 3 0 2 0 0 0 1 3 1 2 1 2 2 0 1 3 2 2 1 2 0 3 3 3 1 1 3 2 2 1 0 3 3 3 0 2 3 2 3 2 3 2 1 1 3 3 0 3 3 0 1 1 0 0 1 3 0 2 2 1 3 2 3 2 3 3 0 3 0 1 1 0 1 0 2 1 1 2 3 2 2 0 1 1 0 3 2 0 0 0 3 3 1 2 3 0 3 2 2 3 1 1 1 1 1 3 1 0 3 0 1 2 2 3 0 3 2 0 1 3 0 2 1 3 2 1 3 0 3 1 3 3 3 1 2 2 2 1 2 1 0 3 2 1 2 0 3 2 0 2 0 2 3 0 1 2 3 2 1 0 0 2 1 1 2 1 2 3 1 0 3 2 3 0 2 2 2 3 2 1 1 2 0 2 1 1 3 0 0 1 3 3 2 2 2 0 2 2 3 2 3 0 2 0 2 0 2 3 2 0 2 0 3 0 1 0 1 2 3 2 0 0 3 3 3 3 3 2 0 3 0 1 3 3 2 2 0 2 3 2 3 3 2 2 2 1 1 2 3 2 3 0 1 0 1 0 2 1 0 2 0 2 0 0 1 1 2 2 3 1 2 3 3 3 3 1 3 2 0 1 3 3 1 3 0 2 2 0 3 2 3 2 0 3 1 0 0 0 1 1 0 0 2 3 1 1 0 0 1 2 0 3 0 0 2 0 0 2 2 1 0 1 3 3 2 2 1 0 2 1 1 1 2 2 2 1 1 1 0 1 2 2 1 3 0 2 0 3 2 2 3 1 2 0 0 0 2 0 2 2 0 2 0 0 1 1 0 3 1 3 1 2 3 3 3 2 3 3 2 2 3 3 0 1 0 3 0 0 3 1 2 3 1 2 3 0 0 2 1 2 3 0 2 2 1 0 2 1 2 2 0 2 2 1 1 1 2 0 1 2 3 2 3 3 1 1 3 2 0 1 0 0 0 1 1 2 0 2 3 2 3 1 1 0 0 1 2 0 2 2 3 0 2 1 1 3 1 0 2 3 0 3 0 1 2 1 1 0 0 2 3 2 2 2 2 1 0 0 0 1 0 0 2 2 0 2 0 1 0 2 3 2 1 0 3 1 2 2 0 3 2 0 0 0 1 2 2 0 1 3 2 1 0 3 3 1 2 3 2 2 1 2 3 1 0 1 2 0 3 3 3 0 0 3 1 0 3 3 3 2 0 1 2 1 2 0 2 2 0 1 1 3 2 3 2 1 1 3 2 3 1 3 2 0 0 3 2 1 0 2 2 2 1 3 0 0 2 2 0 1 3 3 0 0 0 1 3 0 0 3 0 2 2 3 0 0 0 3 1 2 3 0 1 1 1 3 2 3 2 2 3 2 0 1 1 3 2 1 1 1 0 3 3 1 1 0 2 1 0 3 2 2 3 0 2 0 3 1 0 2 0 2 3 0 0 0 3 2 0 2 1 1 2 0 1 3 0 1 1 2 0 1 2 2 2 1 1 1 3 3 1 2 1 1 2 2 3 2 2 3 0 0 1 1 0 3 2 0 3 3 1 1 1 2 2 1 0 3 2 0 2 3 2 1 0 3 1 1 0 1 0 1 3 0 3 1 2 1 2 2 0 2 0 0 3 1 2 1 3 0 2 3 0 3 2 2 1 0 2 3 3
原本的输入数据在此之后还有更多考试 199 份数据,但在此例中省略了,仅展示了对应于最初 1 次考试的数据,请注意。
出力例 1
3 2 2 0 0 0 2 0 2 3 0 2 0 1 0 2 1 2 2 0 2 0 0 1 1 2 2 1 2 0 2 3 3 3 1 3 2 0 1 0 3 0 3 0 2 0 2 3 2 3
关于输出,本来应注意在此之后还必须输出进一步的试验 199 个数据。
此外,这个输入例是在以本来的数据相同的方法生成之后的最初 1 仅提取了该数量的测试,输出示例的答案不包含错误答案(也可在本地测试自己的程序时使用)。
关于输入数据
本题的输入数据是由以下 C++ 程序生成的。
该程序从标准输入中输入作为随机数种子的整数 w ,并输出本题的输入数据。输入示例 1 的数据是 w = 0 在这种情况下的最初 1 次测试。
在裁判使用的输入数据中 w ,将 1 以上 10^9 从以下整数中 10 选择生成。
此外,作为存在不依赖于具体生成方法的解法的依据之一,在不依赖以下生成程序的本题解答程序中,0≦w≦1,000 可以得到第 1,001 可以对所有输入数据正确回答。
生成程序:
#include <iostream>
#include <cstdint>
using namespace std;
uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint32_t xor128() {
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int lo, int hi) {
uint64_t v = ((uint64_t)xor128() << 32) | xor128();
return v % (hi - lo + 1) + lo;
}
void generate() {
const int N = 30, Q = 50;
int correct_answer[Q];
for (int i = 0; i < Q; ++i) {
correct_answer[i] = randint(0, 3);
}
int eel_type[N];
for (int i = 0; i < N; ++i) {
eel_type[i] = i / (N / 3);
}
for (int i = N - 1; i >= 1; --i) {
swap(eel_type[i], eel_type[randint(0, i)]);
}
for (int i = 0; i < N; ++i) {
int eel_answer[Q];
for (int j = 0; j < Q; ++j) {
bool correct = false;
if (eel_type[i] == 0) correct = randint(0, 2) != 0;
if (eel_type[i] == 1) correct = randint(0, 2) == 0;
if (eel_type[i] == 2) correct = randint(0, 3) == 0;
if (correct) {
eel_answer[j] = correct_answer[j];
} else {
eel_answer[j] = (correct_answer[j] + randint(1, 3)) % 4;
}
}
for (int j = 0; j < Q; ++j) {
printf("%d%c", eel_answer[j], j+1 == Q ? '\n' : ' ');
}
}
}
int main() {
cin >> w;
for (int i = 0; i < 10000; ++i) {
xor128();
}
for (int t = 0; t < 200; ++t) {
generate();
}
return 0;
}