802 . 鐵棒問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dbGIs
＼(・ω・＼)SAN値!(／・ω・)／ピンチ!

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

100.0% (6/6)

Tags

apcsc apcsc-dp

Description

現在地上有 N 條鐵棒，第 i 條的長度為 li。你的目標是要利用這些鐵棒，焊出一條長度為 L 的長鐵棒，請問有辦法嗎？兩條鐵棒如果長度分別為 a 和 b，那它們兩個焊起來之後就會變成一條長度為 a+b 的鐵棒，而且這些鐵棒可以任意焊接。

此外，你必須要回答出 T 種這個問題。

Input Format

輸入的第一行有一個數字 T(1≤T≤50)，代表有幾個問題。對於每一個問題，都會有兩行的輸入：第一行有兩個數字 L(1≤L≤1000) 和 N(1≤N≤30)，代表目標長度的鐵棒與現在有幾根鐵棒。下一行有 N 個數字 li(1≤li≤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

Subtasks

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
Submit
Back to Top