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=
　この時、+ と = は以下のように用いる。
  • + : 数字と数字の間でのみ押すことができます。
  • = : + を使用する場合は一番最後に必要です。+ を使っていない場合に押しても何も起きません。
　さて、この魚屋の店主は気難しいので、早く伝えないと怒ってしまいます。そこでボタンを押す回数はなるべく少なくしたいです。 先ほどの例の場合は 11 と押すと、2 回ボタンを押すだけで 11 を表すことができ、この場合が押す回数は最小になります。

　電卓に表示させたい数字が与えられた時、壊れていないボタンのみを用いて数字を表示させるために、押したボタンの回数が最小となる場合に押したボタンを順に答えなさい。なお、加算の形で表す場合は、項の順番は問いません（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 は小さい順に並んでおり、重複はしない。
    • この行に表示された数字のボタンと+と=を用いることができる。
  • 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=

Source Name

ARC 005