767 . 找錢問題
TopCoder
Tags
Description
在 TOI 國有 $N$ 種幣值，都是正整數且依照嚴格遞增的順序為 $c_1, c_2, c_3, \dots, c_N$，而每一種幣值都有無限多個。現在，你有 $M$ 個物品，價值分別為 $p_1, p_2, p_3, \dots, p_M$。請問你有沒有辦法用 TOI 國有的錢幣湊出每一個物品的價值呢？
一個價錢 $x$ 能夠被湊得出來若且唯若存在 $N$ 個數字 $w_i$ 滿足 $w_i \geq 0$ 且 $\sum c_i w_i = x$。
Input Format
輸入有三行。第一行有兩個數字 $N,M(1\leq N \leq 60,1\leq M \leq 10^ 5)$。第二行有 $N$ 個數字 $c_i(0 < c_1 < c_2 < \dots < c_N \leq 10^ 5)$ 代表有的幣值。第三行有 $M$ 個數字 $p_i(0 \leq p_i \leq 10^ 9)$，代表有的物品的價值。
Output Format
請輸出一個長度為 $M$ 的字串 $S$，滿足：$S$ 的第 $i$ 個字元為 Y 若且唯若 $p_i$ 能夠被湊出來；否則就是 N。
Sample Input 1
7 7
4 6 8 10 71 80 92
70 9 69 8199 460 14 98
4 6 8 10 71 80 92
70 9 69 8199 460 14 98
Sample Output 1
YNNYYYY
Sample Input 2
3 2
3 5 9
13 7
3 5 9
13 7
Sample Output 2
YN
Hints
Problem Source
NPSC 2015
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~14 | 無額外限制 | 100 |