Free Lunch
Time Limit: 3 Seconds Memory Limit: 65536 KB
Bahman is participating in a very popular cooking game show. The prize of the winner is a free lunch at the
ACM ICPC.
The goal of the game is to make the best cake out of some raw cooking ingredients. The judges are very picky, so
Bahman needs to follow the instructions of making the cake better very precise. The host provided the
participants all the N raw ingredients they can use. All these N ingredients are in separated containers,
ordered C1 to Cn. The only rule of the game is that you can not take ingredients freely. This rule is as
follows.
- You choose any container Ci and any positive integer d.
- You take exactly d grams of ingredient from container Ci.
- You choose K > 0 containers from the set {Cj | j < i}, and get some ingredients (in grams, integer) from them, in a way that the total weight of those ingredients from these K containers becomes equal to d.
You can repeat this procedure as many times as needed, but you can not throw away any grams of ingredients you
take.
Bahman has several cooking recipes, but he does not know if it is possible to take the required ingredients by the
rule of the game or not. Assume that the capacity of each container is infinite.
Write a program that given the required ingredients for a recipe, determines the possibility of taking that
ingredients by the rule.
Input
The input contains several test cases.
In the first line of input comes T (0 < T < 64), the number of test cases.
For each case, the first line contains an integer N(1 ≤ N ≤ 106) indicating the number of containers. Then
followed by N lines, the ith line contains an integer D
i(0 ≤ Di ≤ 109) which shows we need D
i grams of the ithcontainer’s ingredient.
Caution! Use fast IO functions as the input file is very big.
Output
For each test case, output a line with the string “YAAAYYYY” if Bahman can win the game and “NOOOO”
otherwise.
Sample Input
2 3 2 4 2 3 1 2 2
Sample Output
YAAAYYYY NOOOOSubmit
Source: 12th Iran Nationwide Internet Contest - Final