Spinning Wheels
1998 ACM NE Regionals
Each of five opaque spinning wheels has one or more wedges cut
out of its edges. These wedges must be aligned quickly and correctly.
Each wheel also has an alignment mark (at 0 degrees) so that the
wheels can all be started in a known position. Wheels rotate in
the `plus degrees' direction, so that shortly after they start,
they pass through 1 degree, 2 degrees, etc. (though probably not
at the same time).
This is an integer problem. Wheels are never actually at 1.5
degrees or 23.51234123 degrees. For example, the wheels are
considered to move instantaneously from 20 to 25 degrees during a
single second or even from 30 to 40 degrees if the wheel is spinning
quickly.
All angles in this problem are presumed to be integers in the
range 0 <= angle <= 359. The angle of 0 degrees follows the
angle of 359 degrees. Each wheel rotates at a certain integer
number of degrees per second, 1 <= speed <= 180.
Wedges for each wheel are specified by an integer start angle
and 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 would
imagine.
At the start, which is time 0, all the wheels' alignment marks
line up. Your program must determine the earliest time (integer
seconds) at or after the start that some wedge on each wheel will
align with the wedges on the other wheel so that a light beam can
pass through openings on all five wedges. The wedges can align at
any part of the rotation.
PROGRAM NAME: spin
INPUT 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 next
W pairs of integers tell each wedge's start angle and extent.
SAMPLE INPUT (file spin.in)
30 1 0 120
50 1 150 90
60 1 60 90
70 1 180 180
90 1 180 60
OUTPUT FORMAT
A single line with a single integer that is the first time the
wedges align so a light beam can pass through them. Print `none' (lower
case, no quotes) if the wedges will never align properly.
SAMPLE OUTPUT (file spin.out)
9
题意：
给出五个圆的角速度和若干缺角的起始角度及缺角大小（角度单位).求出何时五个圆才能有缺角层叠，使得光线能通过这五个圆
代码如下：
/*
LANG: C
TASK: spin
*/
#include<stdio.h>
struct circle
{
int w, n, s[360][2];
}circle[5];
int t[360];
void setZero()
{
int i;
for (i = 0; i < 360; i++)
{
t[i] = 0;
}
}
int insert(int time)
{
int i, j, k, round, start, end;
for (i = 0; i < 5; i++)
{
for (j = 0; j < circle[i].n; j++)
{
round = circle[i].w * time;//求出从0到time转过的角度
start = (circle[i].s[j][0] + round) % 360;
end = (circle[i].s[j][1] + round) % 360;
if (end < start)//如果end < start，表示从起点到终点经过了0(X轴)
{
for (k = start; k < 360; k++)
{
t[k]++;
}
for (k = 0; k <= end; k++)
{
t[k]++;
}
}
else
{
for (k = start; k <= end; k++)
{
t[k]++;
}
}
}
}
for (i = 0; i < 360; i++)//有一个点大于或等于5，就表示光线能穿过。
{
if (t[i] >= 5)
{
return 1;
}
}
return 0;
}
void judge()
{
int i;
//至多只需要判断360秒，每个圆旋转最多只需要360秒就能复位，这样对于所有的圆，在360内一定能回到初始位置
for (i = 0; i < 360; i++)
{
setZero();//
if (insert(i))
{
printf("%d\n", i);
return;
}
}
printf("none\n");
}
int main()
{
freopen("spin.in", "r", stdin), freopen("spin.out", "w", stdout);
int i, j, start, r, end;
for (i = 0; i < 5; i++)
{
scanf("%d%d", &circle[i].w, &circle[i].n);
for (j = 0; j < circle[i].n; j++)
{
scanf("%d%d", &start, &r);
end = (start + r) % 360;//求出其中一个缺角的结尾
circle[i].s[j][0] = start, circle[i].s[j][1] = end;
}
}
judge();
fclose(stdin), fclose(stdout);
//system("pause");
return 0;
}