TopCoder

$\huge 南ことり$
$ε=ε=ε=(~ ̄▽ ̄)~烙跑囉$

User's AC Ratio

97.3% (107/110)

Submission's AC Ratio

50.9% (118/232)

Tags

Description

  這學期工藝課期中作業是作一把有雕刻裝飾的竹尺。在半個學期的工藝課中,小批陸續完成了切割,磨邊以及裝飾的工作,最後一個步驟是將刻度給刻在尺上。才刻了幾個刻度在尺上,小批很意外地發現一件事:

  假設本題中所討論的尺,單位都是公分。如上圖,雖然還沒刻完所有刻度,這把全長為 $1+1+4+4+3=13$ 公分的尺已經可以量出所有 $1\sim 13$ 公分的長度了。尺中分別有長為 $1,3,4$ 公分的片段,而前兩段長度合起來是 $2$ 公分長,第 $2$ 和第 $3$ 段合起來是 $5$ 公分,前 $3$ 段合起來則是 $6$ 公分,後 $2$ 段合起來 $7$ 公分,第 $3$ 和第 $4$ 段合起來 $8$ 公分,第 $2$ 到第 $4$ 段合起來是 $9$ 公分$\dots$。你可以試看看,這把 $13$ 公分長的尺已經可以量測 $1\sim 13$ 公分長的長度了。

  上述的尺有個小名叫做節約尺。一把總長度為 $K$ 的節約尺一定要符合兩個條件:
  (1). 必需可以量出 $1$ 到 $K$ 之間所有整數公分長。
  (2). 總刻度數不等於 $K$,這裡的刻度數定義為尺上刻痕所分隔的片段個數,例如上圖的尺一共有 $1, 1, 4, 4, 3$ 共 $5$ 個刻度。一把 $10$ 公分的尺,如果有 $10$ 個刻度,每個刻度長度都是 $1$,那就不算是「節約」刻度的尺了。

  小批還想知道的是,還有沒有其他不同刻度組合的節約尺。你可以幫忙寫一個程式來判斷一把還沒刻完刻度的尺是不是節約尺嗎?

Input Format

  你的程式必須讀入一個輸入檔,檔案可能有數筆測試資料。每筆完整的測試資料共有兩行,定義一把尺的刻度數目和長度。測試資料的第一行為 $1$ 個整數 $N (1 ≤ N ≤ 20)$,表示一個尺已刻上的刻度將這把尺分成幾個片段。第二行則有 $N$ 個整數,這些整數會介於 $1$ 到 $N$ 之間,表示這些片段的長度。
  當程式讀到測試資料的 $N=0$ 時,請不要再輸出任何訊息並結束執行此程式。

Output Format

  對每一把尺,若其符合節約尺定義,請輸出「YES」。若否請輸出「NO」。

Sample Input 1

5
2 2 2 2 2
5
1 1 4 4 3
10
1 2 3 4 5 6 7 8 9 10
10
1 2 4 4 5 6 5 1 1 1
0

Sample Output 1

NO
YES
NO
YES

Hints

Problem Source

原TIOJ1074 / NPSC2005決賽(prob C)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1