Posted on 2009-05-13 10:14
superman 阅读(195)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 class Wheel
6 {
7 public:
8 void rotate()
9 {
10 for (int i = 0; i < wedge_num; i++)
11 {
12 wedges_start_angle[i] += rotation_speed;
13 wedges_start_angle[i] %= 360;
14 }
15 }
16
17 int rotation_speed;
18 int wedge_num;
19 int wedges_start_angle[5];
20 int wedges_extent[5];
21 } wheels[5];
22
23 bool light_can_pass_all_wheels()
24 {
25 int c[360] = { 0 };
26 for (int i = 0; i < 5; i++)
27 for (int j = 0; j < wheels[i].wedge_num; j++)
28 {
29 int s = wheels[i].wedges_start_angle[j];
30 for (int k = 0; k <= wheels[i].wedges_extent[j]; k++)
31 c[(s + k) % 360] += 1;
32 }
33
34 for (int i = 0; i < 360; i++)
35 if (c[i] == 5)
36 return true;
37 return false;
38 }
39
40 int main()
41 {
42 freopen("spin.in", "r", stdin);
43 freopen("spin.out", "w", stdout);
44
45 for (int i = 0; i < 5; i++)
46 {
47 cin >> wheels[i].rotation_speed >> wheels[i].wedge_num;
48 for (int j = 0; j < wheels[i].wedge_num; j++)
49 cin >> wheels[i].wedges_start_angle[j] >> wheels[i].wedges_extent[j];
50 }
51
52 if (light_can_pass_all_wheels())
53 {
54 cout << 0 << endl;
55 return 0;
56 }
57 for (int t = 1; t < 360; t++)
58 {
59 for (int i = 0; i < 5; i++)
60 wheels[i].rotate();
61 if (light_can_pass_all_wheels())
62 {
63 cout << t << endl;
64 return 0;
65 }
66 }
67
68 cout << "none" << endl;
69
70 return 0;
71 }
72