802 . 鐵棒問題
TopCoder
Description
現在地上有 $N$ 條鐵棒，第 $i$ 條的長度為 $l_i$。你的目標是要利用這些鐵棒，焊出一條長度為 $L$ 的長鐵棒，請問有辦法嗎？兩條鐵棒如果長度分別為 $a$ 和 $b$，那它們兩個焊起來之後就會變成一條長度為 $a + b$ 的鐵棒，而且這些鐵棒可以任意焊接。
此外，你必須要回答出 $T$ 種這個問題。
Input Format
輸入的第一行有一個數字 $T(1 \leq T \leq 50)$，代表有幾個問題。對於每一個問題，都會有兩行的輸入：第一行有兩個數字 $L(1 \leq L \leq 1000)$ 和 $N(1 \leq N \leq 30)$，代表目標長度的鐵棒與現在有幾根鐵棒。下一行有 $N$ 個數字 $l_i(1 \leq l_i \leq 1000)$，代表目前有的鐵棒的長度。保證所有輸出的數字都是正整數。
Output Format
對於每一筆測資，請輸出一行：倘若能夠達到目標的話，請輸出 TAK；否則，請輸出 NO。
Sample Input 1
4
8 12
61 47 2 75 66 49 33 2 6 18 61 17
7 8
1 1 1 1 1 1 1 2
8 7
1 1 1 1 1 1 1
19 6
18 36 2 8 9 12
8 12
61 47 2 75 66 49 33 2 6 18 61 17
7 8
1 1 1 1 1 1 1 2
8 7
1 1 1 1 1 1 1
19 6
18 36 2 8 9 12
Sample Output 1
TAK
TAK
NO
TAK
TAK
NO
TAK
Sample Input 2
4
10 4
2 3 4 5
9 4
2 3 4 5
63 6
1 2 4 8 16 32
64 6
1 2 4 8 16 32
10 4
2 3 4 5
9 4
2 3 4 5
63 6
1 2 4 8 16 32
64 6
1 2 4 8 16 32
Sample Output 2
TAK
TAK
TAK
NO
TAK
TAK
NO
Hints
Problem Source
UVa 12455 - Bars
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~11 | 無額外限制 | 100 |