Spinning Wheels1998 ACM NE Regionals
Each of five opaque spinning wheels has one or more wedges cutout of its edges. These wedges must be aligned quickly and correctly.Each wheel also has an alignment mark (at 0 degrees) so that thewheels can all be started in a known position. Wheels rotate inthe `plus degrees’ direction, so that shortly after they start,they pass through 1 degree, 2 degrees, etc. (though probably notat the same time).
This is an integer problem. Wheels are never actually at 1.5degrees or 23.51234123 degrees. For example, the wheels areconsidered to move instantaneously from 20 to 25 degrees during asingle second or even from 30 to 40 degrees if the wheel is spinningquickly.
All angles in this problem are presumed to be integers in therange 0 <= angle <= 359. The angle of 0 degrees follows theangle of 359 degrees. Each wheel rotates at a certain integernumber of degrees per second, 1 <= speed <= 180.
Wedges for each wheel are specified by an integer start angleand integer angle size (or `extent’), both specified in degrees.Wedges in the test data will be separated by at least one degree.The ‘extent’ also includes the original "degree" of the wedge, so’0 180′ means degrees 0..180 inclusive — one more than most wouldimagine.
At the start, which is time 0, all the wheels’ alignment marksline up. Your program must determine the earliest time (integerseconds) at or after the start that some wedge on each wheel willalign with the wedges on the other wheel so that a light beam canpass through openings on all five wedges. The wedges can align atany part of the rotation.
PROGRAM NAME: spinINPUT FORMAT
Each of five input lines describes a wheel.
The first integer on an input line is the wheel’s rotation speed.The next integer is the number of wedges, 1 <= W <= 5. The nextW pairs of integers tell each wedge’s start angle and extent.
SAMPLE INPUT (file spin.in) 30 1 0 12050 1 150 9060 1 60 9070 1 180 18090 1 180 60OUTPUT FORMAT
A single line with a single integer that is the first time thewedges align so a light beam can pass through them. Print `none’ (lowercase, no quotes) if the wedges will never align properly.
SAMPLE OUTPUT (file spin.out)9
分析
用模拟求解此题，外层循环是转过的时间，单位为秒，范围为[0,359]，因为超过此范围相当于循环，没有意义。在每一时刻判断是否存在对齐，此时枚举出所有可能的对齐角度[0,359]（离散化思想），检查光线能否通过5个轮子的任意一个缺口。T(n)=360*360*25=3*10^6。需要注意的是，边界对齐也是符合要求的（？），所谓边界对齐，就是一个缺口与另一个缺口的交集只有边界。举例来说，，缺口[0,1]和[1,2]就是边界对齐的，光线可以同时穿过这两个缺口。
在检查任意时刻缺口是否对齐问题上，我曾想过求五个轮子的缺口交集，如果交集为空，则不对齐。这种方法不好，最坏情况下，交集的个数非常之多，极端情况有5^5个，当然这是不可能的，因为轮子一共才360度，考虑到这点，最坏情况下，交集的个数也可以达到360个，而且计算过程非常耗时。
部分借鉴blog
https://www.byvoid.com/blog/usaco-323-spinning-wheels/
通过代码Executing… Test 1: TEST OK [0.003 secs, 3500 KB] Test 2: TEST OK [0.008 secs, 3500 KB] Test 3: TEST OK [0.008 secs, 3500 KB] Test 4: TEST OK [0.014 secs, 3500 KB] Test 5: TEST OK [0.005 secs, 3500 KB] Test 6: TEST OK [0.027 secs, 3500 KB] Test 7: TEST OK [0.005 secs, 3500 KB] Test 8: TEST OK [0.019 secs, 3500 KB]/*ID: c1033311LANG: C++TASK: spin*/#include<stdio.h>struct{int s;int len;int e;}wheel[5][5];int speed[5],holeNum[5];//枚举所有角度[0,359]，看光线是否能通过int check(void){int i,j,k;for(i=0;i<360;++i) //角度{int sum=0;for(j=0;j<5;++j)//轮子{for(k=0;k<holeNum[j];++k)if((i>=wheel[j][k].s && i<=wheel[j][k].e)||(i<wheel[j][k].s && i+360<=wheel[j][k].e)){sum++;break;}}if(sum==5)return 1;}return 0;}int main(){FILE *fin=fopen("spin.in","r");FILE *fout=fopen("spin.out","w");int time;int i,j;//输入数据for(i=0;i<5;++i){fscanf(fin,"%d%d",&speed[i],&holeNum[i]);for(j=0;j<holeNum[i];++j){fscanf(fin,"%d%d",&wheel[i][j].s,&wheel[i][j].len);wheel[i][j].s%=360;wheel[i][j].e=wheel[i][j].s+wheel[i][j].len;}}//求解for(time=0;time<360;++time){if(check()==1){fprintf(fout,"%d\n",time);break;}else //转动1s的距离{for(i=0;i<5;++i)for(j=0;j<holeNum[i];++j){wheel[i][j].s+=speed[i];wheel[i][j].s%=360;wheel[i][j].e=wheel[i][j].s+wheel[i][j].len;}}//end else}if(time==360)fprintf(fout,"none\n");return 0;}
多对自己说“我能行，我一定可以”，
