読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

ゴリ押し証明です。