E - Examination, Estimation Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 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;
}