Beyond the Void
BYVoid
USACO 3.2.3 Spinning Wheels 纺车的轮子

由于题目对某些细节描述不清,导致开始我一直看不懂题,相信也有人看不懂什么意思。解释一下题的意思:

有5个半径相同的同心圆的轮子叠在一起,每个轮子上有1~5个缺口,缺口为一个扇形。每个轮子每秒可以逆时针转动一定角度。现在给定每个轮子的初始状态,求多少时间后,每个轮子至少有一个缺口重叠在一起,以至于可以让一条光线通过。其实就像保险柜一样,每个轮子必须转动到缝隙对齐才可以。时间和角度都是整数。输出这个时间。如果永远也不能实现,则输出none。

有一个这样的事实,转动事件在0,360秒内是有意义的,360秒过后所有轮子会回归到初始状态。 于是这道题就可以简单的模拟了。枚举时间t=0 to 360,当时间为t时,寻找是否有一条光线能穿过每个轮子的缺口。如果存在即输出t。如果枚举完成还没有找到,则输出none。

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: spin
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2840 KB]
   Test 2: TEST OK [0.011 secs, 2840 KB]
   Test 3: TEST OK [0.011 secs, 2836 KB]
   Test 4: TEST OK [0.011 secs, 2840 KB]
   Test 5: TEST OK [0.000 secs, 2836 KB]
   Test 6: TEST OK [0.032 secs, 2836 KB]
   Test 7: TEST OK [0.011 secs, 2836 KB]
   Test 8: TEST OK [0.043 secs, 2836 KB]

All tests OK.

YOUR PROGRAM ('spin') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations. 
/*
ID: cmykrgb1
PROG: spin
LANG: C++
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
	long speed;
	long qcnt;
	long q_s[5],q_e[5];
}wheel;
FILE *fi,*fo;
wheel W[5];

void init()
{
	long i,j,l;
	fi=fopen("spin.in","r");
	fo=fopen("spin.out","w");
	for (i=0;i<5;i++)
	{
		fscanf(fi,"%ld%ld",&W[i].speed,&W[i].qcnt);
		for (j=0;j<W[i].qcnt;j++)
		{
			fscanf(fi,"%ld%ld",&W[i].q_s[j],&l);
			W[i].q_e[j]=W[i].q_s[j]+l;
			if (W[i].q_e[j]>=360) W[i].q_e[j]-=360;
		}
	}
}

void print(long k)
{
	if (k==-1)
		fprintf(fo,"nonen");
	else
		fprintf(fo,"%ldn",k);
	fclose(fi);
	fclose(fo);
	exit(0);
}

bool check()
{
	long i,a,b,p;
	bool flag;
	for (i=0;i<360;i++) //角度为i的一条线同时穿过5个轮子,每个轮子中任意一个缺口
	{
		p=0;
		for (a=0;a<5;a++)
		{
			flag=false;
			for (b=0;b<W[a].qcnt;b++)
			{
				if  (   (i>=W[a].q_s[b] && i<=W[a].q_e[b] && W[a].q_s[b]<=W[a].q_e[b])
				      ||( (i<=W[a].q_e[b] || i>=W[a].q_s[b]) && W[a].q_s[b]>W[a].q_e[b])
					)
				{
					flag=true;
					break;
				}
			}
			if (flag)
				p++;
		}
		if (p==5)
			return true;
	}
	return false;
}

void turn()
{
	long t,i,j;
	for (t=0;t<360;t++)
	{
		if (check())
			print(t);
		for (i=0;i<5;i++)
		{
			for (j=0;j<W[i].qcnt;j++)
			{
				W[i].q_s[j]+=W[i].speed;
				if (W[i].q_s[j]>=360) W[i].q_s[j]-=360;
				W[i].q_e[j]+=W[i].speed;
				if (W[i].q_e[j]>=360) W[i].q_e[j]-=360;
			}
		}
	}
	print(-1);
}

int main()
{
	init();
	turn();
	return 0;
}

上次修改时间 2017-02-03

相关日志