No.332 A Sequence as a Present
タグ : / 解いたユーザー数 60
作問者 :
紙ぺーぱー
Problem Statement
Today is Christmas, so let us tell $\text{kamipeipaa}$-kun, who is a sequence of $N$ natural numbers whose $i$-th element is $A_i$, whether he has a subsequence whose sum is $X$.
Input
The input is given from standard input in the following format.
$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}$
Output
If $\text{kamipeipaa}$-kun has no subsequence whose sum is $X$, print No on $1$ line.
If such a subsequence exists, print on $1$ line a string $S$ of $N$ characters, on $1$ line.
The $i$-th character of $S$ should be o if the $i$-th element of the sequence is used in the subsequence forming the answer, and x if it is not used.
If there are multiple subsequences that form an answer, you may print any of them.
See the samples for details.
Sample
Sample 1
Input
4 8 1 2 2 5
Output
oxoo
$\text{kamipeipaa}$-kun has $2$ kinds of subsequences whose sum is $8$, represented by oxoo and ooxo, and you may print either of them.
Sample 2
Input
3 7 8 9 3
Output
No
$\text{kamipeipaa}$-kun has no subsequence whose sum is $7$. Print No.
Sample 3
Input
1 1 1
Output
o
The sum of $\text{kamipeipaa}$-kun himself may be $X$.
Sample 4
Input
1 2 1
Output
No
There is no subsequence whose sum is greater than the sum of $\text{kamipeipaa}$-kun.
Sample 5
Input
10 10000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Output
oooooooooo
The sum of $\text{kamipeipaa}$-kun may be very large.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。