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;
}

Related posts