codechef Johnny and the Beanstalk 题解

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.

Input

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<=10⁶). The next k non-negative space-separated integers (not greater than 10⁶) represent the number of leaves of the beanstalk at successive levels, starting from level 1.

Output

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.

Example

Input:
2
3
0 1 2
3
0 0 3

Output:
Yes
No

注意：

1 上百万的数据，小心输入输出。

2 有时候并不需要处理完所有的数组中的数据，但是必须要清除读入stdin的数据。

3 清除的时候要小心了，也许之前的‘\n‘字符已经读出了，如果继续使用‘\n‘判断，那么就会出错。我这里干脆不处理跳过行了。直接读完所有数据，使用getchar速度也很快的。

水题要注意的东西也挺多的，不知道什么时候才能轻松避开这些陷阱。

#pragma once
#include <cstdio>

class JohnnyandtheBeanstalk
{
public:
	int scanInt()
	{
		char c = getchar();
		while (c < ‘0‘ || ‘9‘ < c)
		{
			c = getchar();
		}
		int num = 0;
		while (‘0‘ <= c && c <= ‘9‘)
		{
			num = (num<<3) + (num<<1) + (c - ‘0‘);
			c = getchar();
		}
		return num;
	}

	void run()
	{
		int T = 0, k = 0, leaves = 0;
		T = scanInt();
		while (T--)
		{
			k = scanInt();
			int steam = 1;
			bool flag = true;
			for (int i = 1; i <= k; i++)
			{
				leaves = scanInt();
				if (leaves > steam)
				{
					flag = false;
					
				}
				steam = (steam - leaves) << 1;
			}
			if (!flag || steam != 0) puts("No");
			else puts("Yes");
		}
	}
};

int johnnyandtheBeanstalk()
{
	JohnnyandtheBeanstalk jobean;
	jobean.run();
	return 0;
}

codechef Johnny and the Beanstalk 题解,布布扣,bubuko.com

codechef Johnny and the Beanstalk 题解

原文：http://blog.csdn.net/kenden23/article/details/25047091