USACO 3.2.3 Spinning Wheels 纺车的轮子
This post is written in Chinese. Please consider using Google Translate
由于题目对某些细节描述不清,导致开始我一直看不懂题,相信也有人看不懂什么意思。解释一下题的意思:
有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;
}