[ホームゲーム]A number game
Description
You've designed a computer and implemented all the common arithmetic operators: addition, subtraction, multiplication and integer division. However, your budget was very limited, so you could only afford to place a single register in the computer. The register can store any non-negative integer value. Since there is only one register, there is no need to identify the store location or the operands of each operation or its result. The programming language has four instructions: '+', '-', '*' and '/'. Each instruction performs the corresponding operation using the value in the register as both its parameters. It then stores the result in the same register, overwriting the previous content. A program for your computer is a sequential list of zero or more instructions. You want to show that, even with its limitations, your newly constructed computer is powerful. You will be given two ints s and t. Return the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-("(quotes for clarity) instead.
Input
There are at most 100 cases,each case one line contain 2 space seperated integers S and T. (1 <= S,T <= 10^9)
Output
Output the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-("(quotes for clarity) instead.
Sample Input
Sample Output
//--------------------------------------------------------------------------------------
简単で広く问题を探して、しかし私にしたのはとても悲剧で、无限WA.今日は恥ずかしくてテストデータを見に行って、どこが間違っているのかを発見しました.
//----------------------------------------
最初の考えは次のとおりです.
1もし目標数が開始数と2の積に分解できるならば*、+で広く探します
2できないが目標数因数が2しかない場合は、まず1を除いてから上へ広く検索する
3以上が該当しない、または見つからない場合は出力:-(
エラー:直接上へ検索できると思ったら、直接上へ検索するのは1を除いて上へ検索するより速いに違いないが、実はそうではない.
例えば、開始数は2^n、目標数は2^(2 n-1)であり、開始数は絶えず加算されなければならないが、1を除いては乗算が可能であり、nが大きい場合、後者は目標に早く到達する.
//----------------------------------------
そこで変えて、状況を分けないで、直接広く探します.
除算は最初にしか使えないので、先頭数をキューに差し込んだ後、1と除算番号もキューに差し込み(頭が果敢に水に入る)、依然としてWAです.
エラー:2つの方法が同じステップでターゲットに達すると仮定し、1つ/先頭、1つ*先頭で、辞書順に後者を出力すべきですが、/が先に挿入されているため、逆に前者を出力します.
//----------------------------------------
最后にやはり最も年を取って正直な広捜に帰って、初めの数を列に挿入して、先に挿し込んで更に挿し込んで最后に挿して挿して挿して挿して挿していないで除いて、ああ~~~
//----------------------------------------
間違いに陥るたびに混乱し、頭から頭を整理する習慣がなく、元の基礎の上で直すだけだ.このエラーはコードに従って一度行けば発見できるので、今度は落ち着いて、ああ~~~
You've designed a computer and implemented all the common arithmetic operators: addition, subtraction, multiplication and integer division. However, your budget was very limited, so you could only afford to place a single register in the computer. The register can store any non-negative integer value. Since there is only one register, there is no need to identify the store location or the operands of each operation or its result. The programming language has four instructions: '+', '-', '*' and '/'. Each instruction performs the corresponding operation using the value in the register as both its parameters. It then stores the result in the same register, overwriting the previous content. A program for your computer is a sequential list of zero or more instructions. You want to show that, even with its limitations, your newly constructed computer is powerful. You will be given two ints s and t. Return the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-("(quotes for clarity) instead.
Input
There are at most 100 cases,each case one line contain 2 space seperated integers S and T. (1 <= S,T <= 10^9)
Output
Output the shortest program that finishes with a value of t in the register if it contained s before executing. If there is more than one possible answer, return the one that comes earliest lexicographically. If there is no program that can do the job, return ":-("(quotes for clarity) instead.
Sample Input
7 392
7 256
4 256
7 9
Sample Output
+*+
/+***
**
:-(
//--------------------------------------------------------------------------------------
简単で広く问题を探して、しかし私にしたのはとても悲剧で、无限WA.今日は恥ずかしくてテストデータを見に行って、どこが間違っているのかを発見しました.
//----------------------------------------
最初の考えは次のとおりです.
1もし目標数が開始数と2の積に分解できるならば*、+で広く探します
2できないが目標数因数が2しかない場合は、まず1を除いてから上へ広く検索する
3以上が該当しない、または見つからない場合は出力:-(
エラー:直接上へ検索できると思ったら、直接上へ検索するのは1を除いて上へ検索するより速いに違いないが、実はそうではない.
例えば、開始数は2^n、目標数は2^(2 n-1)であり、開始数は絶えず加算されなければならないが、1を除いては乗算が可能であり、nが大きい場合、後者は目標に早く到達する.
//----------------------------------------
そこで変えて、状況を分けないで、直接広く探します.
除算は最初にしか使えないので、先頭数をキューに差し込んだ後、1と除算番号もキューに差し込み(頭が果敢に水に入る)、依然としてWAです.
エラー:2つの方法が同じステップでターゲットに達すると仮定し、1つ/先頭、1つ*先頭で、辞書順に後者を出力すべきですが、/が先に挿入されているため、逆に前者を出力します.
//----------------------------------------
最后にやはり最も年を取って正直な広捜に帰って、初めの数を列に挿入して、先に挿し込んで更に挿し込んで最后に挿して挿して挿して挿して挿していないで除いて、ああ~~~
//----------------------------------------
間違いに陥るたびに混乱し、頭から頭を整理する習慣がなく、元の基礎の上で直すだけだ.このエラーはコードに従って一度行けば発見できるので、今度は落ち着いて、ああ~~~