TopCoder

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

User's AC Ratio

97.0% (98/101)

Submission's AC Ratio

49.8% (107/215)

Tags

Description

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

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