比赛 20121108 评测结果 AAAAAWAAAA
题目名称 造房子的学问 最终得分 90
用户昵称 Truth.Cirno 运行时间 0.018 s
代码语言 C++ 内存使用 3.31 MiB
提交时间 2012-11-08 09:57:25
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;

struct quetype
{
	int len,tim;
};

bool got[40000];
queue<quetype> que;

int main(void)
{
	freopen("wood.in","r",stdin);
	freopen("wood.out","w",stdout);
	int i,sou,tar,L[5];
	quetype from,to;
	cin>>sou>>tar;
	if (sou==tar)
		cout<<"0\n";
	for (i=1;i<=3;i++)
		cin>>L[i];
	cin>>L[0];
	to.len=sou;
	to.tim=0;
	que.push(to);
	got[to.len]=true;
	while (!que.empty())
	{
		from=que.front();
		to.tim=from.tim+1;
		
		/*1*/
		for (i=1;i<=3;i++)
		{
			to.len=from.len+L[i];
			if (to.len<=32767)
			{
				if (!got[to.len])
				{
					if (to.len==tar)
					{
						cout<<to.tim<<endl;
						return(0);
					}
					got[to.len]=true;
					que.push(to);
				}
			}
		}
		/*1*/
		
		/*2*/
		to.len=L[0];
		if (to.len>0&&to.len<=32767)
		{
			if (!got[to.len])
			{
				if (to.len==tar)
				{
					cout<<to.tim<<endl;
					return(0);
				}
				got[to.len]=true;
				que.push(to);
			}
		}
		to.len=from.len-L[0];
		if (to.len>0&&to.len<=32767)
		{
			if (!got[to.len])
			{
				if (to.len==tar)
				{
					cout<<to.tim<<endl;
					return(0);
				}
				got[to.len]=true;
				que.push(to);
			}
		}
		/*2*/
		
		/*3*/
		to.len=(from.len>>1);
		if (to.len>0)
		{
			if (!got[to.len])
			{
				if (to.len==tar)
				{
					cout<<to.tim<<endl;
					return(0);
				}
				got[to.len]=true;
				que.push(to);
			}
		}
		/*3*/
		
		que.pop();
	}
	cout<<"No solution.\n";
	return(0);
}