← 返回题目列表

AtCoder · xmascon16_e

E. 检查、估计

中文机器翻译题面 查看原题

配点 : 100 点

問題文

兔子是 它有一个矩形网格 50 正打算参加由若干题目组成的考试。每道题都是四选一题,0, 1, 2, 3 四个选项中有一个是正确答案,其余都是错误答案。

在兔子参加考试之前,30 若干条鳗鱼已经参加了完全相同的考试。每条鳗鱼答题的方法如下 3 中的某一种类型,并且已知每种类型的鳗鱼数量相同,为 10 条。

  1. 对每道题都独立地,2/3 的概率选择正确答案,1/3 的概率选择一个错误答案。在选择错误答案时,每个错误答案被选中的概率相同。
  2. 对每道题都独立地,1/3 的概率选择正确答案,2/3 的概率选择一个错误答案。在选择错误答案时,每个错误答案被选中的概率相同。
  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;
}