ACM/ICPC 小球鐘——時間與運動

問題描述

時間是運動的一種方式，所以常常用運動來度量時間。如圖所示的小球鍾就是一個通過不斷在軌道上移動小球來度量時間的簡單設備。

每分鐘，一個轉動臂將一個小球從小球隊列的底部擠走，將它上升到鐘的頂部並安置在一個表示分鐘， 5 分鐘和小時的軌道上。這裡可以顯示從 1:00 到 12:59 範圍內的時間，但無法表示 “a.m.” 和 “p.m.” 。若有 2 個球在分鐘軌道， 6 個球在 5 分鐘軌道及 5 個球在小時軌道上，就顯示時間 5:32 。

不幸的是，大多數市場上提供的小球鍾無法顯示日期，儘管只需要簡單地加上一些軌道就可以了。當小球通過鐘的機械裝置被移動後，它們就會改變其初始次序。仔細研究它們隨著時間的流逝發生的次序的改變，可以發現相同的次序會不斷出現。由於小球的初始次序最後遲早會被重複，所以這段時間的長短是可以被度量的，這完全取決於所提供小球的總數。

每分鐘，最近最少使用的那個小球從位於球鍾底部的小球隊列被移走，並將上升安置於顯示分鐘的軌道上，這裡可以放置 4 個小球。當第 5 個小球滾入該軌道，它們的重量使得軌道傾斜，原先在軌道上的 4 個小球按照與它們原先滾入軌道相反加入到鍾底部的小球隊列。引起傾斜的第 5 個小球滾入顯示 5 分鐘的軌道，該軌道可以放置 11 個球。當第 12 個小球滾入該軌道，它們的重量使得軌道傾斜，原先 11 個小球同樣以相反的次序加入鍾底部的小球隊列。而這第 12 個小球滾入了顯示小時的軌道。該軌道同樣可以放置 11 個球，但這裡有一個外加的固定不能被移動的小球，這樣小時的值域就變為 1 到 12 。從 5 分鐘軌道滾入的第 12 個小球將使小時軌道傾斜，這 11 個球同樣以相反的次序加入鍾底部的小球隊列，然後第 12 個小球同樣加入鍾底部的小球隊列。

輸入小球的個數，輸出該時鐘在經過多少天的運行可以回到它的初始小球序列。例如有 45 個小球的鐘經過 378 天會回到初始狀態。

 

【輸入格式】

輸入文件只有一行,有一個整數n,表示小球的個數.

【輸出格式】

輸出文件也只有一行,有一個整數m,表示小球鍾回到初始狀態的天數.

【輸入輸出樣例】

輸入文件名： xqz.in

45

輸出文件名： xqz.out

378

【分析】

詳見劉汝佳的黑書。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25686

001 #include <cstdio>
002 #include <cstdlib>
003 #include <deque>
004 using namespace std;
005 const int MAXN=720;
006 typedef deque<int> Deque;
007 Deque Minute;
008 Deque Five;
009 Deque Hour;
010 Deque Bot;
011 int N;
012 int M=0;
013
014 bool check()
015 {
016     for(int i=0;i<N;i++)
017     {
018         if(Bot[i]!=i+1)
019             return false;
020     }
021     return true;   
022 }
023
024 void Into3()
025 {
026     int tmp;
027     int tmp2;
028     tmp2=Hour.back();
029     Hour.pop_back();
030     for(int i=1;i<=11;i++)
031     {
032         tmp=Hour.back();
033         Hour.pop_back();
034         Bot.push_back(tmp);
035     }
036     Bot.push_back(tmp2);
037 }
038
039 void Into2()
040 {
041     int tmp;
042     tmp=Five.back();
043     Five.pop_back();
044     Hour.push_back(tmp);
045     for(int i=1;i<=11;i++)
046     {
047         tmp=Five.back();
048         Five.pop_back();
049         Bot.push_back(tmp);
050     }
051 }
052
053 void Into1()
054 {
055     int tmp;
056     tmp=Minute.back();
057     Minute.pop_back();
058     Five.push_back(tmp);
059     for(int i=1;i<=4;i++)
060     {
061         tmp=Minute.back();
062         Minute.pop_back();
063         Bot.push_back(tmp);
064     }
065 }
066
067 void work()
068 {
069     bool flag=false;
070     while(!flag)
071     {
072         M++;
073         int tmp;
074         for(int a=1;a<=12;a++)
075         {
076             for(int b=1;b<=12;b++)
077             {
078                 for(int c=1;c<=5;c++)
079                 {
080                     tmp=Bot.front();
081                     Bot.pop_front();
082                     Minute.push_back(tmp);
083                 }
084                 Into1();
085             }
086             Into2();
087         }
088         Into3();
089         flag=check();
090     }
091     printf("%d\n",(M+1)/2);
092 }
093
094 int main()
095 {
096     freopen("xqz.in","r",stdin);
097     freopen("xqz.out","w",stdout);
098     scanf("%d\n",&N);
099     for(int i=1;i<=N;i++) Bot.push_back(i);   
100     work();
101     return 0;
102 }