【アルゴリズム問題】yukicoder no.10 +か×か (level ☆☆☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.10 +か×か (level ☆☆☆☆)

2014-08-04 00:00
  • 1
あなたは、Isaacから借りたノートをコピーしようとしてOCRにかけようとしている。
ある計算式をOCRしようとしたら、演算子を正しく認識されてなく、文字化けしていることに気づいた。
ここに出てくる演算子は+と*のみで、すべて?と表示されてしまっている。
元の数式の正しい数式を求めてください。
複数回答がある場合は、{+,*} の順の辞書列順の最初のものを求めてください。
例えば辞書順は
++ -> +* -> *+ -> ** の順番である。

重要:この問題では優先順位は同じとし、左結合とする。
簡単に言うと左から順に処理するだけである。
例えば1 ? 2 ? 10 ? 1=31の場合 1+2*10+1が答えで
実際の世界では((1+2)*10)+1=31 となるので注意。

入力
N
Total

A1 A2 ... AN (空白区切り)

A1 ? A2 ? A3 ?....? AN = Total
となっていることを表す。

制約
1<=N<=50
1<=Total<=100,000
1<=Ai<=10
少なくともひとつは、
A1 ? A2 ? A3 ?....? AN = Totalを満たす解があるものとする。

出力
それぞれの演算子を順番に並べたものを出力してください。
(空白などの区切り文字はつけない)



sample1
4
31
1 2 10 1

ans1
+*+

sample2
3
6
2 3 1

ans2
++

**でも成り立つが、{+*}の辞書列順の最初なので++となる。


sample3
3
2
1 1 2


ans3
**



q
https://gist.githubusercontent.com/yuki2006/6d23980cb17b6693a7f9/raw/127f39dc251c99bdaa59352b32af49f324897c9a/yukicoder10.txt


想定解法 Python
http://ideone.com/XQUR0C

1st . なおさん C++
http://ideone.com/3kUOn1
(あるテストケースでTLEがあるのが指摘されました)

広告
×
scache

自分の回答 : http://ideone.com/gPNWPM
なおさんのTLEの入力 : http://ideone.com/HjoUg5
64ヶ月前
コメントを書く
コメントをするには、
ログインして下さい。