Johnny and the Beanstalk
All submissions for this problem are available.
One evening Johnny found some funny looking beens in his grandfather's garden shed, and decided to plant one of them. Next morning, to his surprise he found an enormous beanstalk growing in his back yard. Undaunted by its size, he decided to count its leaves.
You must know that beanstalks in Byteland grow in a very special way. At the lowest (1st) level, there is exactly one stem. At any level(including the 1st), a stem can end (forming exactly one leaf), or branch into exactly two stems which grow into the next level, following the same rules.
Johnny believes he has managed to count the number of leaves at each of the levels of the beanstalk. However, you must know that before he began to count, Johnny ate one or two of the other beans he found in his grandfather's shed, and that's why he is not quite sure of his results. Please verify whether Johnny's results may possibly be correct, at least in theory.
The input starts with a line containing integer t, the number of test cases (1<= t <= 20). The descriptions of exactly t test cases follow.
Each test case starts with an integer k, representing the number of levels of the beanstalk (1<= k<=106). The next k non-negative space-separated integers (not greater than 106) represent the number of leaves of the beanstalk at successive levels, starting from level 1.
For each test case, output a line containing exactly one of the words 'Yes' or 'No', depending on whether a beanstalk having the stated leaf counts can grow in accordance with the Bytelandian rules.
Input: 2 3 0 1 2 3 0 0 3 Output: Yes No
|Time Limit:||0.4 - 1.4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, D, PERL, FORT, ADA, ASM, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile|
Fetching successful submissions
If you are still having problems, see a sample solution here.