GCJ 2019 Round 1A - Golf Gophers
codingcompetitions.withgoogle.com
問題文
去年、たくさんの厄介なホリネズミたちが私たちの果樹園に住んでいました。
私たちは果樹園をやめてミニチュアゴルフコースを開業しました。
しかし、ホリネズミたちもついて来てしまったようです！
そこで、何匹のホリネズミがいるか調査する必要がありますが、ホリネズミは普段隠れていて夜行性なので、直接数えることができません。
ただ、全部で 1 匹以上 M 匹以下であることは分かっています。
私たちのミニチュアゴルフコースは、18ホール全てに小さな扇風機があることで有名です。
i 番目の扇風機には 2 ≤ B_i ≤ 18 枚の羽根があり、それらは時計回りに 0 番から B_i - 1 番まで番号が付けられています。
毎晩、寝る前に扇風機の電源を切り、それぞれの扇風機の羽根 0 が下を向くようにします。
これは扇風機が次の日にちゃんと充電されているようにするために重要です。
しかし、次の日には扇風機の羽根の位置が変わっていることに気がつきました。
ミニチュアゴルフコースは風のない地域にあるので、いたずら好きのホリネズミの仕業に違いありません！
全てのホリネズミは毎晩1回だけやってきて、扇風機を1つランダムに選んで羽根を反時計回りに1つ分回転させます。
例えば、羽根が3枚の扇風機の場合、最初のホリネズミが羽根を回すと羽根 1 が下を向き、次のホリネズミが羽根を回すと羽根 2 が下を向き、さらにホリネズミが羽根を回すと羽根 0 が下を向きます。
私たちはホリネズミの数を調べる計画を立てました。
ゴルフコースの難易度を変えるために、扇風機の羽根の数は簡単に変えられるようになっています。そこで、これを利用するのです！
毎晩、寝る前にそれぞれの扇風機の羽根の枚数を 2 〜 18 枚で選んで変えます。
全ての羽根の枚数を同じにしたり、毎晩同じ枚数にする必要はありません。
そして、朝にそれぞれの扇風機の羽根の向きを確認します。
私たちはホリネズミの数 G を調査するために N 晩使うことができます。
G を特定してください。
入出力
この問題はインタラクティブ問題です。出力の後にフラッシュする必要があります。
まず、テストケースの数 T、使える日数 N、ホリネズミの最大数 M が与えられます。その後、 T 回テストケースを繰り返します。
各テストケースでは N + 1 回までジャッジとやり取りをすることができます。
そのうちの N 回は以下の通りです。
あなたのプログラムは 2 以上 18 以下の18個の整数を1行に出力します。これらの i 番目は、その夜に i 番目の扇風機に取り付ける羽根の数を表します。
ジャッジは18個の整数を1行で返します。これらの i 番目は、ホリネズミがいたずらをした後、i 番目の扇風機の下を向いている羽根の番号を表しています。
無効なデータ（範囲外の数字、不正な行など）を送信した場合は、代わりに -1 が返されます。
どのホリネズミがどの扇風機を回すかはランダムで一様であり、他のホリネズミの行動によって変わることもありません。
このように 0 回以上 N 回以下やり取りをした後、あなたのプログラムはホリネズミの数 G を出力します。
ジャッジは1つの整数を返します。あなたの答えが正しい場合は 1、正しくない場合（または不正な形式の行を出力した場合）は -1 です。
ジャッジが -1 を返した場合、それ以降ジャッジは入出力を行いません。あなたのプログラムは終了しなければ Time Limit Exceeded になります。
制約
1 ≤ T ≤ 20
実行制限時間 : 20秒
メモリ制限 : 1GB
小課題
小課題1 (11点)
N = 365
M = 100
小課題2 (21点)
N = 7
M = 106
考察
羽根の枚数をバラバラにするとあまり情報が得られなさそう
羽根の枚数を同じにすると羽根の枚数で割ったあまりがわかる
→ 中国剰余定理
互いに素になるように上から選ぶと、
17 * 16 * 13 * 11 * 9 * 7 = 2.450448 * 106
だから N = 6 で十分
ACコード :
