申請SAE

如果您發現本博客的外觀很難看,那是因為部分外觀文件被中國.國家.防火.牆屏.蔽所致!
請翻~牆!

我的Wordpress博客的地址: http://zhuyf.tk/
顯示具有 ACM 標籤的文章。 顯示所有文章
顯示具有 ACM 標籤的文章。 顯示所有文章

2012年2月27日 星期一

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 天會回到初始狀態。

[搜索]ACM練習題:分球 ball 解題報告

題目來源:
1. 浙江理工大學 OnlineJudge 2584
2. 山東理工大學 OnlineJudge 1406
【問題描述】
在一個裝滿財寶的屋子裡,有2N個盒子排成一排。除了兩個相鄰的空盒外,其餘的每個盒子裡都裝有一個金球或者一個銀球,總共有N-1個金球和N-1個銀球。用圖6.3所示為一個N=5時的例子,G表示金球,S表示銀球。
G
S
S
G
G
S
G
S

任意兩個相鄰的非空的盒子裡的球可以移動到兩個相鄰的空盒中,移動不能改變這兩個球的排列順序。寫一個程序,用最少的移動次數把所有的金球都移到所有的銀球的左邊。