Spinning Wheels

題意：有5個不透明圓盤，有各自的轉速，每個圓盤上有W個缺口（1<=W<=5），給定缺口的位置和大小。将這5個圓盤串到一根棍子上，0度對齊，求多少秒後一束光能穿過這5個圓盤？

解題思路：

1. 簡單模拟一下就行。對每個圓盤，根據轉速确定多少秒後會回到初始狀态，求這些時間的最小共倍數。隻需要模拟到這個最小共倍數就行。為了簡單，可以模拟到359秒，因為360秒後每個圓盤一定同時回到初始狀态。
2. 對每個模拟的狀态，确定會不會有缺口有重疊，則光可以穿過，得到結果。
3. 确定缺口重疊的方法：用一個數組wedges[i][j][k]儲存這些缺口，代表第i個圓盤的第j個缺口的角度。wedges[i][j][0]為缺口起點，wedges[i][j][1]為缺口終點。因為每個圓盤有若幹個缺口，是以這裡有一個組合的問題。
4. 對特定的缺口組合，用left儲存缺口重疊的起點，right儲存缺口重疊的終點。left初始化為第1個圓盤的缺口起點，right初始化為第1個圓盤的缺口終點。然後周遊後面的圓盤，計算重疊部分，更新left，right。如果計算到最後都有重疊，則此缺口組合滿足光可以通過。如果計算過程中right > left則不能使光通過。計算過程中涉及到的角度轉換問題詳見代碼。

代碼：

/*
ID: zc.rene1
LANG: C
PROG: spin
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int speeds[5];
int wedge_num[5];
int wedges[5][5][2];

void Rotate(void)
{
    int i, j;
    for (i=0; i<5; i++)
    {
	for (j=0; j<wedge_num[i]; j++)
	{
	    wedges[i][j][0] = (wedges[i][j][0] + speeds[i]) % 360;
	    wedges[i][j][1] = (wedges[i][j][1] + speeds[i]) % 360;
	}
    }
}

int min(int a, int b)
{
    return a < b ? a : b;
}

int max(int a, int b)
{
    return a > b ? a : b;
}

int CanPass(int *index)
{
    int left = wedges[0][index[0]][0];
    int right = wedges[0][index[0]][1];
    int i, temp_left, temp_right;

    for (i=1; i<5; i++)
    {
	if (right < left)
	{
	    right += 360;
	}
	else
	{
	    left += 360;
	    right += 360;
	}
	temp_left = wedges[i][index[i]][0];
	temp_right = wedges[i][index[i]][1];
	if (temp_right < temp_left)
	{
	    temp_right += 360;
	}
	else
	{
	    temp_left += 360;
	    temp_right += 360;
	}
	left = max(left, temp_left);
	right = min(right, temp_right);

	if (right < left)
	{
	    return 0;
	}
	else
	{
	    left %= 360;
	    right %= 360;
	}
    }
    return 1;
}

int Check(void)
{
    int index[5];

    for (index[0]=0; index[0]<wedge_num[0]; index[0]++)
    {
	for (index[1]=0; index[1]<wedge_num[1]; index[1]++)
	{
	    for (index[2]=0; index[2]<wedge_num[2]; index[2]++)
	    {
		for (index[3]=0; index[3]<wedge_num[3]; index[3]++)
		{
		    for (index[4]=0; index[4]<wedge_num[4]; index[4]++)
		    {
			if (CanPass(index))
			{
			    return 1;
			}
		    }
		}
	    }
	}
    }
    return 0;
}

int main(void)
{
    FILE *fin, *fout;
    int i, j, angle, angle_size;

    fin = fopen("spin.in", "r");
    fout = fopen("spin.out", "w");

    memset(wedges, -1, 5*5*2*sizeof(int));

    for (i=0; i<5; i++)
    {
	fscanf(fin, "%d %d", &speeds[i], &wedge_num[i]);
	for (j=0; j<wedge_num[i]; j++)
	{
	    fscanf(fin, "%d %d", &angle, &angle_size);
	    wedges[i][j][0] = angle;
	    wedges[i][j][1] = (angle + angle_size) % 360;
	}
    }	

    for (i=0; i<360; i++)
    {
	if (Check())
	{
	    break;
	}
	Rotate();
    }

    if (i < 360)
    {
	fprintf(fout, "%d\n", i);
    }
    else
    {
	fprintf(fout, "none\n");
    }

    return 0;
}