D - 壊れた電卓
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君の電卓は壊れてしまっています。 K 種類より多くの種類の数字を打つと、電卓が壊れてしまいます。
整数 A が与えられます。高橋君は、この整数を入力したいです。 ですが、普通にその整数を打とうとすると、電卓が壊れてしまうことがあるため、 電卓が壊れない範囲で、出来るだけ整数 A との差の大きさが小さい整数を入力します。
この時、高橋君が入力する整数と、整数 A の差の大きさがいくつになるかを出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。
A K
- 1 行目には、入力したい整数 A (1 ≦ A ≦ 10^{15}) と、入力可能な数字の種類数 K (1 ≦ K ≦ 10) が、スペース区切りで与えられる。
部分点
- 1 ≦ A ≦ 100,000 の全てのケースに正解すると、 30 点が与えられる。
- 残りの全てのケースに正解すると、さらに 70 点が与えられる。
出力
高橋君が入力する整数と、整数 A の差の大きさの最小値を 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
1234 2
出力例1
12
高橋君は、 2 種類のキーまでしか入力することが出来ません。
今回の場合は、 1222 と入力することで、1234 と最も近くなり、その差は 12 となります。
入力例2
800000 1
出力例2
22223
数字は 1 種類しか使えないので、777777 が最も近い整数となります。
入力例3
7328495 10
出力例3
0
このケースでは、高橋君の電卓は本当は壊れていません。
よって、与えられた整数をそのまま入力することが出来ます。
入力例4
262004 2
出力例4
218
262222 が、最も近い整数となります。