Guess Them All(数当て) - joi2011-day2

出典: 第10回日本情報オリンピック 日本代表選手選考会

時間制限: 2秒

メモリ制限: 64MB

あなたは JOI ちゃんと数当てゲームをしている．まず，JOI ちゃんは 1 以上 N 以下の整数 1 つずつをある順番に並べ替えた数列を用意する．この数列を「正解」と呼ぶことにしよう．あなたは「予想」という行動を L 回まで行うことができ，L 回以内に正解を当てることができればあなたの勝ちである．

1 回の「予想」では，あなたは 1 以上 N 以下の整数 N 個を並べた数列を JOI ちゃんに伝える．予想の数列には，同じ整数が複数個含まれていてもかまわない．1 回の予想ごとに，予想の数列と正解とが何か所で一致したかを知ることができる．

あなたはこのゲームに勝つため，プログラムを書くことにした．

課題

正解の数列を指定された回数以下の予想で当てるプログラムを作れ．

制限

数列の長さ N と予想回数の上限 L は「採点基準」の項目で述べる．

入力

標準入力から以下の入力を読み込め．

やりとり

入力データを読み込んだ後，あなたのプログラムは，標準出力への予想の書き出しと，標準入力からの回答の読み込みを交互に行わなければならない．各予想は，予想した数列の i 番目の整数を i 行目とした N 行を標準出力に書き出さなければならない．予想には 1 より小さい整数や N より大きい整数が含まれていてはならない．各回答は，予想の数列と正解の数列が何か所で一致したかを表す 1 個の整数からなる 1 行として，標準入力から与えられる．回答として N が返ってきた際は，数列を当てることに成功したということなので，その時点でプログラムを終了し，その後一切の出力を行ってはならない．

注意

全ての採点用データについて，適切なアルゴリズムを用いれば，正解の数列が 1 以上 N 以下の整数のどのような並べ替えであっても，L 回以下の予想で当てることができる．

重要な注意

標準入力を読み込むときに，読み込みが誤ってブロックされてしまうことを防ぐ必要がある．そのため，読み込みを行う前に fflush(stdout); などを記述しておくことを勧める．以下が採点システムとのやりとりを行うサンプルプログラムである．

#include <stdio.h>
int main(void) {
    int i, N, ret;
    scanf("%d", &N);
    for (;;) {
        for (i = 1; i <= N; i++) {
            printf("%d\n", i); // 予想
        }
        fflush(stdout); // 回答を読む前に標準出力をフラッシュする
        scanf("%d", &ret); // 採点システムからの回答を読む
        if (ret == N) break;
    }
    return 0;
}

採点基準

入出力の例

入力例 1 出力例 1
3
3
2
1
1
1
2
3
0
2
3
1
3

この例では3 回の予想で正解に達している．