D - 連射王高橋君
Editorial
/
ようやく魚屋に到着した高橋君は、あまりお金を持ってきていなかったことに気づきました。これでは定価でうなぎを買うことができません。そこで、店主に値引きしてくれないか交渉することにしました。ところが、魚屋の店主はお年寄りで耳が遠く、値段を言う高橋君の声がうまく聞こえていないようです。仕方がないので高橋君は近くにあった電卓を使って、値段を伝えることにしました。
しかし困ったことに、高橋君はうっかり電卓を落としていくつかのボタンを壊してしまいました。電卓には 数字(
例えば
電卓に表示させたい数字が与えられた時、壊れていないボタンのみを用いて数字を表示させるために、押したボタンの回数が最小となる場合に押したボタンを順に答えなさい。なお、加算の形で表す場合は、項の順番は問いません(
入力は以下の形式で標準入力から与えられる。
壊れていないボタンのみを用いて指定された数字を表示させるために、押したボタンの回数が最小値となる場合に押したボタンを順に答えなさい。
なお、最後には改行を出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
しかし困ったことに、高橋君はうっかり電卓を落としていくつかのボタンを壊してしまいました。電卓には 数字(
0
-9
), 加算記号(+
), イコール(=
) の 12 個のボタンがあります。0
、1
、+
、=
が壊れていないことは確かですが、それ以外のボタンは壊れている可能性があります。例えば
0
、1
、2
、+
、=
が壊れていない場合は、店主に 11 を伝える方法の例の一部としては以下のようなものがあります。
- 1+1+1+1+1+1+1+1+1+1+1=
- 2+2+2+2+2+1=
- 11
- 1+2+1+2+1+1+1+2=
- 10+1=
+
と =
は以下のように用いる。
+
: 数字と数字の間でのみ押すことができます。=
:+
を使用する場合は一番最後に必要です。+
を使っていない場合に押しても何も起きません。
電卓に表示させたい数字が与えられた時、壊れていないボタンのみを用いて数字を表示させるために、押したボタンの回数が最小となる場合に押したボタンを順に答えなさい。なお、加算の形で表す場合は、項の順番は問いません(
1+2=
が正解ならば、2+1=
も正解です)。
入力
b_1b_2...b_N price
- 入力は 2 行のみである。
- 1 行目には N(2≦N≦10) 文字の整数の文字列が与えられる。
- b_i(1≦i≦N)は、
0
-9
のいずれかであり、壊れていないボタンを表す。 - b_1からb_Nまでに、
0
、1
の 2 つは必ず含まれる。 - 1 行目の中で、b_i は小さい順に並んでおり、重複はしない。
- この行に表示された数字のボタンと
+
と=
を用いることができる。
- b_i(1≦i≦N)は、
- 2 行目には表示させたい整数 price(1≦price<10^{18}) が与えられる。
- 注:64bit型整数型を使うことを推奨します。
出力
なお、最後には改行を出力せよ。
入力例 1
01257 2380
出力例 1
2270+110=
- 使用できるボタンは
0
,1
,2
,5
,7
,+
,=
の7 つです。 - 3 と 8 が壊れてしまっているので、加算の形で表す必要があります。
入力例 2
0123456789 17564523527628452
出力例 2
17564523527628452
- 全てのボタンが使えるので、入力したい数字を直接入力できます。
入力例 3
01 9
出力例 3
1+1+1+1+1+1+1+1+1=
- 0 と 1 しか使えないので、1 つずつ足すしかありません。
入力例 4
019 2727
出力例 4
909+909+909=
入力例 5
01457 245723852196245230
出力例 5
175711751155145110+70011701041100110+400000000010=