以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 2 – Guess Them All
数当て(Guess Them All)
あなたはJOI ちゃんと数当てゲームをしている.まず,JOI ちゃんは1 以上N 以下の整数1 つずつをあ
る順番に並べ替えた数列を用意する.この数列を「正解」と呼ぶことにしよう.あなたは「予想」という
行動をL 回まで行うことができ,L 回以内に正解を当てることができればあなたの勝ちである.
1 回の「予想」では,あなたは1 以上N 以下の整数N 個を並べた数列をJOI ちゃんに伝える.予想の数
列には,同じ整数が複数個含まれていてもかまわない.1 回の予想ごとに,予想の数列と正解とが何か所
で一致したかを知ることができる.
あなたはこのゲームに勝つため,プログラムを書くことにした.
課題
正解の数列を指定された回数以下の予想で当てるプログラムを作れ.
制限
数列の長さN と予想回数の上限L は「採点基準」の項目で述べる.
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれている.
やりとり
入力データを読み込んだ後,あなたのプログラムは,標準出力への予想の書き出しと,標準入力からの
回答の読み込みを交互に行わなければならない.各予想は,予想した数列のi 番目の整数をi 行目とした
N 行を標準出力に書き出さなければならない.予想には1 より小さい整数やN より大きい整数が含まれて
いてはならない.各回答は,予想の数列と正解の数列が何か所で一致したかを表す1 個の整数からなる1
行として,標準入力から与えられる.回答としてN が返ってきた際は,数列を当てることに成功したとい
うことなので,その時点でプログラムを終了し,その後一切の出力を行ってはならない.
注意
全ての採点用データについて,適切なアルゴリズムを用いれば,正解の数列が1 以上N 以下の整数のど
のような並べ替えであっても,L 回以下の予想で当てることができる.
数当て– 1 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 2 – Guess Them All
重要な注意
標準入力を読み込むときに,読み込みが誤ってブロックされてしまうことを防ぐ必要がある.そのため,
読み込みを行う前に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;
}
採点基準
採点用データのうち,配点の10%分については,1 ≦N ≦7, L = 6 000 をみたす.
採点用データのうち,配点の40%分については,1 ≦N ≦50, L = 3 000 をみたす.
採点用データのうち,配点の30%分については,1 ≦N ≦100, L = 1 000 をみたす.
採点用データのうち,配点の20%分については,1 ≦N ≦100, L = 700 をみたす.
数当て– 2 / 3
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 2 – Guess Them All
入出力の例
入力例 出力例
3
3
2
1
1
1
2
3
0
2
3
1
3
この例では3 回の予想で正解に達している.
数当て– 3 / 3