USACO 3.2.3 Spinning Wheels 紡車的輪子
本文正體字版由OpenCC轉換
由於題目對某些細節描述不清，導致開始我一直看不懂題，相信也有人看不懂什麼意思。解釋一下題的意思:
有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