TopCoder

dbGIs

這題出的好!唐可可給你一個讚

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

100.0% (5/5)

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

Sample Output 1

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

Sample Output 2

TAK
TAK
TAK
NO

Hints

Problem Source

UVa 12455 - Bars

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~11	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2

802 . 鐵棒問題