Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %lld & %llu

Description

Gordon is recently reading about an interesting game. At the beginning of the game, there are three positive numbers written on a blackboard. In each round, you are asked to delete one of these three numbers. And you should write the sum of the remaining two numbers minus one back to the blackboard. For example, there are three numbers, 2, 3 and 10 on the blackboard. If you decide to change the number 3 in this round, you will delete the number 3 first and put the number 11=2+10-1 back to the blackboard. So it would be 2, 10 and 11 on the blackboard then. The target of this game is to reach a given number in the minimal steps.

One day, when Gordon was playing the game, his best friend Mike came in. Mike saw that the numbers on the blackboard were 17, 1967 and 1983, and asked Gordon if he had played this game from the beginning numbers 3, 3 and 3. Since Gordon didn’t leave a trace on the game, he asked you, a young brilliant programmer, to help them check out if Mike made the right guess.

Input

The first line of the input contains an integer T (T < 200), indicating the number of cases. Each test case consists of a line with six positive integers. The first three are the numbers currently on Gordon’s blackboard and the last three are the numbers that Mike guessed. It is guaranteed that every number in a game is positive and is less than 1,000,000.

Output

For each test case, you should write a single word in a line. If it is possible to get Gordon’s numbers from Mike’s guess, you would give the word “Yes”. Otherwise you need to output the word “No”.

Sample Input

2
6 10 15 7 13 26
17 1967 1983 3 3 3

Sample Output

No
Yes

Source

The 9th Zhejiang University Programming Contest
思路:如果从正向走,设初始数对为{a, b, c},则可拓展出{a, b, a + b – 1}, {a, c, a + c – 1}, {b, c, b + c – 1}三种状态。每种父亲有3个儿子,解答树太大,会超时。
从后往前走,因为每组数肯定都满足其中最大的数等于另两个数求和减一,所以较小的两个数上次肯定也在数对中,并且当前数对第二大的数就是上次最大的数。设终止数对为{a, b, c}(a < b < c),则可且仅可拓展出{a, b – a + 1, b}一个儿子,例如数对{6, 10, 15}只可能是由{5, 6, 10}拓展过来的。每种状态有且仅有一个父亲,可行。
代码实现方面,每产生一种状态就按升序排一次,这样最后面的就是最大的,第二个就是上次最大的。把初始数对的三个儿子都计算出来并保存到数组中,方便判断。
AC代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int goal[5], start[5], dir[5][5];
void input()
{
	for (int i = 0; i < 3; i++)
		scanf("%d", &goal[i]);
	for (int i = 0; i < 3; i++)
		scanf("%d", &start[i]);
}
bool check()
{
	for (int i = 0; i < 3; i++)
		if (!memcmp(dir[i], goal, sizeof(goal)))
			return 1;
	return 0;
}
void solve()
{
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			dir[i][j] = start[j];
	dir[0][0] = dir[0][1] + dir[0][2] - 1;
	dir[1][1] = dir[1][0] + dir[1][2] - 1;
	dir[2][2] = dir[2][0] + dir[2][1] - 1;
	for (int i = 0; i < 3; i++)
		sort(dir[i], dir[i] + 3);
	sort(start, start + 3);
	while (1)
	{
		sort(goal, goal + 3);
		if (goal[0] < start[0])
		{
			printf("No\n");
			return;
		}
		if (check())
		{
			printf("Yes\n");
			return;
		}
		goal[2] = goal[1] - goal[0] + 1;
	}
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		input();
		solve();
	}
	return 0;
}

 

分类: ACM/ICPC

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注