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
題意：
給出五個(gè)圓的角速度和若干缺角的起始角度及缺角大小（角度單位).求出何時(shí)五個(gè)圓才能有缺角層疊，使得光線能通過這五個(gè)圓
代碼如下：
/*
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轉(zhuǎn)過的角度
start = (circle[i].s[j][0] + round) % 360;
end = (circle[i].s[j][1] + round) % 360;
if (end < start)//如果end < start，表示從起點(diǎn)到終點(diǎn)經(jīng)過了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++)//有一個(gè)點(diǎn)大于或等于5，就表示光線能穿過。
{
if (t[i] >= 5)
{
return 1;
}
}
return 0;
}
void judge()
{
int i;
//至多只需要判斷360秒，每個(gè)圓旋轉(zhuǎn)最多只需要360秒就能復(fù)位，這樣對(duì)于所有的圓，在360內(nèi)一定能回到初始位置
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;//求出其中一個(gè)缺角的結(jié)尾
circle[i].s[j][0] = start, circle[i].s[j][1] = end;
}
}
judge();
fclose(stdin), fclose(stdout);
//system("pause");
return 0;
}