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 が、最も近い整数となります。