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小時后，鐘底部的小球編號依次是p₁, p₂, p₃,…, p_n。則可以建立這樣的置換：

1  　2 　 3　… n

p₁ 　p₂　 p₃  … p_n

注意到小球鐘的運作規則保證了上述置換是不變的，就可以計算出小球鐘運行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  }