USACO Training Section 3.2 Spinning Wheels

英文原题  中文题译

大意：有五个纺车飞轮，每个都有最多五个缺口，飞轮转速恒定，有缺口对齐（飞梭可以跑）的最小时刻。

数据限制：全是整数，输出也是整数。

不用考虑真正的模拟，在小数时刻有缺口对齐的情况，只需考虑0-360秒下0-360度每个度是否是缺口。

这是我写的第二个版本。第一个版本试图模拟缺口，WA后发现描述中缺口可以大于180度，这样，一个缺口与另一个缺口的交可能是两个缺口，需考虑的情况过于复杂，想想，这肯定不是需要找的答案，就放弃先。唉。又一次。

ＰＳ:考虑一下不离散的情况，如何处理？

/*
ID: blackco3
TASK: spin
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
const int _n_wheel_(5), _max_wedge_(5), _max_degree_(360) ;
struct t_wheel {
	int speed, pos, is_wedge[_max_degree_] ;
} wheels[_n_wheel_] ;

bool all_wedge( int degree ) {
	for (t_wheel *pc=wheels; pc!=wheels+_n_wheel_; pc++ )
		if ( !pc->is_wedge[ (_max_degree_ - pc->pos + degree)%_max_degree_ ] ) 
			return false;
	return true;
}

int main() {
	freopen("spin.in", "r", stdin);
	freopen("spin.out", "w", stdout);
	memset( wheels, 0, sizeof(wheels) );
	for( int i=0; i<_n_wheel_; i++ ){
		int n_wedge, start, len ;
		cin >> wheels[i].speed >> n_wedge ;
		for( int j=0; j<n_wedge; j++ ){
			cin >> start >> len ;
			for( int d=start; d<=start+len; d++ )
				wheels[i].is_wedge[ d%_max_degree_ ] = 1 ;
		}
			
	}
	for( int t=0; t<_max_degree_; t++ ){
		for (int i = 0; i <_max_degree_; i++)
			if ( all_wedge(i) ) {
				cout << t << endl ;
				return 0;
			}
		for (t_wheel *pc=wheels; pc!=wheels+_n_wheel_; pc++ )
            pc->pos = (pc->pos+pc->speed) % _max_degree_ ;
	}
	cout << "none" << endl ;
	return 0;
}