1.2.2 小球钟
【例题讲解】小球钟（ballclock）POJ 1879
小球钟是一种通过不断在轨道上移动小球来度量时间的设备。每分钟，一个转动臂将一个小球从小球队列的底部移走，让它上升到钟的顶部，并将它安置在一个表示1分钟、5分钟、15分钟和小时的轨道上。它可以显示从1:00到24:59（这正是奇怪之处）内的时间，若有3个球在1分钟轨道，1个球在5分钟轨道，2个球在15分钟轨道及15个球在小时轨道上，就表示时间为15:38。
当小球通过钟的机械装置被移动后，它们就会改变其初始次序。仔细研究它们次序的改变，可以发现相同的次序会不断出现。由于小球的初始次序迟早会重复出现，因此这段时间的长短是可以被度量的，这完全取决于所提供的小球的总数。
每分钟，最近最少被使用的那个小球从位于球钟底部的小球队列被移走，并将上升到显示1分钟的轨道上，这里可以放置4个小球。当第5个小球滚入该轨道，它们的重量（重量为质量的俗称）使得轨道倾斜，原先在轨道上的4个小球按照与它们原先滚入轨道的次序相反的次序加入钟底部的小球队列。引起倾斜的第5个小球滚入显示5分钟的轨道。该轨道可以放置2个球。当第3个小球滚入该轨道，它们的重量使得轨道倾斜，原先的2个小球同样以相反的次序加入钟底部的小球队列。而第3个小球滚入了显示15分钟的轨道。这里可以放置3个小球。当第4个小球滚入该轨道，它们的重量使得轨道倾斜，原先在轨道上的3个小球按照与它们原先滚入轨道的次序相反的次序加入钟底部的小球队列，而这第4个小球滚入了显示小时的轨道。该轨道可以放置23个球，但这里有一个外加的、固定的（不能被移动的）小球，这样小时的值域就变为1～24。从15分钟轨道滚入的第24个小球将使小时轨道倾斜，这23个球同样以相反的次序加入钟底部的小球队列，然后第24个小球同样加入钟底部的小球队列。
【输入格式】
输入小球时钟序列。每个时钟都按照前面描述的那样运作。所有时钟的区别仅在于它们在时钟启动时刻小球初始个数的不同。在输入的每行上给出一个时钟的小球数，它并不包括那个在小时轨道上的固定的小球。合法的数据为33～250。0表示输入的结束。
【输出格式】
输出中的每一行只有一个数，表示对应的输入情形中给出的小球数量的时钟在经过多少天的运行后可以回到它的初始小球序列。
【输入样例】
33
55
0
【输出样例】
22
50
【算法分析】
可以通过模拟出每个小球回到原来位置上所需的天数，然后求它们的最小公倍数的方法来解决这个问题，但这样速度仍然很慢。改进方法是先模拟小球钟最先24小时的运行情况，得到24小时后的钟底部的新小球队列。设初始时，钟底部的小球编号依次是1,2,3,…,n。24小时后，钟底部的小球编号依次是p1, p2, p3,…, pn。则可以建立这样的置换：
1 2 3 … n
p1 p2 p3 … pn
注意到小球钟的运作规则保证了上述置换是不变的，就可以计算出小球钟运行48小时后、72小时后……钟底部的小球队列情况，直至队列情况重新是1,2,3,…,n。这样，在求得以上置换的基础上，我们可以求每一个小球回到原位置的周期，然后求它们的最小公倍数即可。
现举例说明每一个小球（如1号小球）回到原位置的周期是怎么计算的。
如图1.2所示，假设初始队列为1 2 3 4，则24小时后的队列为4 1 2 3。可以看出4号位置上的4号小球跑到了1号位置上，3号位置上的3号小球跑到了4号位置上。显然再过24小时，4号位置上的3号小球会跑到1号位置上，而3号位置上的2号小球会跑到4号位置上。
图1.2
再过24小时，4号位置上的2号小球跑到1号位置，而4号位置将被1号小球占据，因为第1个24小时后，1号位置上的1号小球跑到了2号位置上。
再过24小时，4号位置上的1号小球跑到了初始的1号位置上，1号小球的周期计算完毕。
参考代码如下。
1 //小球钟
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 const int Limit[4] = {5,3,4,24};//定义每种轨道容纳的小球数
6 int Line[4][25]; //4种轨道,即1分钟、5分钟、15分钟、小时轨道
7 int solved[300]; //保存计算好的结果
8 deque<int> Q; //队列
9
10 int GCD(int m, int n) //求最大公约数
11 {
12 return n==0?m:GCD(n,m%n);
13 }
14
15 long long GetDay(int n)
16 {
17 int j,k;
18 long long ans = 1;
19 for (int i = 0; i < n; ++i) //枚举每个小球
20 {
21 for (j = Q[i], k = 1; j != i; j = Q[j], ++k);//计算每个小球的周期k
22 ans=ans*k/GCD(ans, k);//求此小球与之前所有小球的周期的最小公倍数
23 }
24 return ans;
25 }
26
27 int Solve(int n)
28 {
29 Q.clear(); //清空队列
30 for (int i = 0; i < n; ++i) //初始化队列
31 Q.push_back(i);
32 while(1)
33 {
34 Line[0][++Line[0][0]]=Q.front(); //Line[i][0]记录第i种轨道已有的球数
35 Q.pop_front();
36 for (int i = 0; i < 3; ++i) //枚举1分钟、5分钟、15分钟的轨道
37 if (Line[i][0] == Limit[i]) //若本轨道达到了容纳极限
38 {
39 Line[i+1][++Line[i+1][0]]=Line[i][Line[i][0]--];//最后一个球滚入下一轨道
40 while (Line[i][0] != 0)
41 Q.push_back(Line[i][Line[i][0]--]);//剩余的球依次逆序入队列
42 }
43 if (Line[3][0] == Limit[3]) //若24小时到了
44 {
45 int o = Line[3][0]--; //先记录本球的编号
46 while (Line[3][0] != 0) //其他球依次入队列
47 Q.push_back(Line[3][Line[3][0]--]);
48 Q.push_back(Line[3][0]); //最后一个球滚入队列
49 break;
50 }
51 }
52 return GetDay(n);
53 }
54
55 int main()
56 {
57 int n;
58 while (cin >> n, n != 0)
59 if (solved[n] != 0) //如果之前已计算过，直接输出结果
60 cout<<solved[n]<<'\n';
61 else
62 cout<<(solved[n]=Solve(n))<<'\n'; //记录计算结果并输出
63 return 0;
64 }