No.332 数列をプレゼントに
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 256 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 56
作問者 :
紙ぺーぱー
タグ : / 解いたユーザー数 56
作問者 :
紙ぺーぱー
問題文最終更新日: 2015-12-24 23:55:32
問題文
今日はクリスマスなので、$i$番目の要素が$A_i$であるような$N$個の自然数からなる数列である$\text{kamipeipaa}$くんに総和が$X$であるような部分列が存在するか教えてあげましょう。
入力
入力は以下の形式で標準入力から与えられる。
$N \ X$ $A_1 \ A_2 \dots A_N$
- $1 \leq N \leq 100$
- $1 \leq A_i \leq 10^{9}$
- $A_1 \times A_2 \times \dots \times A_N \leq 10^{100}$
- $1 \leq X \leq 10^{12}$
出力
$\text{kamipeipaa}$くんに総和が$X$であるような部分列が存在しないならばNoを$1$行に出力してください。
存在するならば$1$行に$N$文字からなる文字列$S$を$1$行に出力してください。
$S$の$i$文字目は答えとなるような部分列に数列の$i$番目が使用されるならばoを、使用されないならばxを出力してください。
答えとなるような部分列が複数存在した場合どれを出力しても構いません。
詳しくはサンプルを確認してください。
サンプル
サンプル1
入力
4 8 1 2 2 5
出力
oxoo
$\text{kamipeipaa}$くんに総和が$8$であるような部分列はoxooとooxoで表されるようなものの$2$種類が存在しますが、どちらを出力しても構いません。
サンプル2
入力
3 7 8 9 3
出力
No
$\text{kamipeipaa}$くんに総和が$7$であるような部分列が存在しません。Noを出力してください。
サンプル3
入力
1 1 1
出力
o
$\text{kamipeipaa}$くんの総和自身が$X$であることもあります。
サンプル4
入力
1 2 1
出力
No
$\text{kamipeipaa}$くんの総和より総和が大きい部分列は存在しません。
サンプル5
入力
10 10000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力
oooooooooo
$\text{kamipeipaa}$くんの総和はとても大きいこともあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。