GCJ Qualification Round 2016 A. Counting Sheep
問題概要
すべての数字が出揃うまで N,2N,3N,... と数を並べていったとき、最後に並べた数はなんだろうか。いくら並べても揃わないなら INSOMNIA と出力せよ。
解法
N,2N,3N, ... と順に並べていけば直感的にはすぐに揃うし、実験してみると N ≦ 106 では確実に揃うことが分かる。N=0 のときだけが例外。
ここからは余談だけど、下 4 桁だけを見ると任意の整数 N で揃うことが証明できる。
N mod 10000, 2N mod 10000, 3N mod 10000, ... を並べていく問題を解いてみると、N が以下の値のとき揃わないことが分かる。
- 0
- 1250
- 2000
- 2500
- 3750
- 4000
- 5000
- 6000
- 6250
- 7500
- 8000
- 8750
元の問題に戻ってみよう。
もし N の下 4 桁がこれらの値でなければ揃う。
もし N の下 4 桁がこれらの値になってたら、 N を出来るだけ 10 で割れば 1 の位が 0 ではなくなるので、やはり揃う。
GCJ Qualification Round 2016 A. Counting Sheep
ゴリ押し証明です。