Google Code Jam 2010 Qualification C

Problem C: Theme Park

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p2&a=2
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=2

這題是最後一題, 應該也算是最簡單的一題

不過有點Tricky, 想答對Large的難度, 要做點最佳化才有辦法

題目是說, 一般遊客去做雲霄飛車的時候, 都習慣一群一群人一起坐上去, 如果有人做不上去的話, 就會等下一班車. 然後, 每個人坐一次會付1元, 我們要算出雲霄飛車一天可以賺多少錢.

例如:

雲霄飛車有 6 個位置, 每天會開 4 次, 遊客有 4 群人, 每群遊客依序有 1, 4, 2, 1 人, 而這些遊客會整天一直排隊坐雲霄飛車.

所以, 第一次雲霄飛車會載 [1, 4] 人 (因為不能插隊, 所以不會把後面一個人的往前補)

第二次會載 [2, 1, 1] 人

第三次會載 [4, 2] 人

最後一次會載 [1, 1, 4] 人

因此, 最後一共賺了 21 元

在解法的方面, 應該都大同小異

我是用一個 Array 存了遊客人數 [1, 4, 2, 1]

另外還有一個相對應的快取 Array 存了計算過的結果 [5, 6, 4, 6]

快取Array, 初始為[?, ?, ?, ?] 
第一次載完 [1, 4] 人, 所以是 [5, ?, ?, ?]
第二次由第三群遊客開始, 載完 [2, 1, 1] 人, 所以是 [5, ?, 4, ?]
第三次載完 [4, 2] 人, 所以是 [5, 6, 4, ?]
第四次載完 [1, 1, 4] 人, 所以是 [5, 6, 4, 6]
第五次之後, 就不需要再計算, 而是直接使用快取的結果
速度上來說, 已經足以解決這個問題

官方提供了三種最佳化, 有興趣的人可以在上去看看

Google Code Jam 2010 Qualification B

Problem B: Fair Warning

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p1&a=1
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=1


這一題的題目很有趣, 但是解起來就不是那麼有趣了, 因為牽扯到大數的問題.
還好我是用JAVA解題, 內建就有大數的函式庫可以使用

題目是說, 在Jamcode星球上, 有一種預言, 西元前發生的幾件大事件, 會暗示哪一天是世界末日

例如:
西元前26000, 11000, 6000年發生了大事件, 則西元4000年會導致世界末日.
因為西元4000年, 離這三個事件分別是30000, 15000, 10000年, 都是5000的倍數, 並且, 5000是一個最大的因數

以這個例子來看
(26000+4000) % 5000 = (11000+4000) % 5000 
(11000+4000) % 5000 = (6000+4000) % 5000 
(26000-11000) % 5000 = 0
(11000-6000) % 5000 = 0

所以
(a + y) % T = (b + y) % T
(a - b) % T = 0

因此, 所有年份的相差值中, 去取出最大公因數, 就是解答

Google Code Jam 2010 Qualification A

Problem A: Snapper Chain

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0

這題蠻有趣的
題目是說, 有一種聲控的延長線
只要你一拍手, 有插電的延長線就會開啟或者關閉

我們以0代表關閉, 1代表開啟
如果有兩條延長線, 由左至右連接
則一開始的情況依序為
[0 0]
再做了一次拍手之後, 則變成
[1 0]
接著為
[0 1]
[1 1]
則使得延長線為通電的狀況

如果有四條延長線, 則為以下的情況
[0 0 0 0]
[1 0 0 0]
[0 1 0 0]
[1 1 0 0]
[0 0 1 0]
[1 0 1 0]
[0 1 1 0]
[1 1 1 0]
[0 0 0 1]
[1 0 0 1]
[0 1 0 1]
[1 1 0 1]
[0 0 1 1]
[1 0 1 1]
[0 1 1 1]
[1 1 1 1]

所以聰明的你
是不是發現, 每16次會通電一次

因此可以歸納出
每2的N次方, 會通電一次

這個歸納, 應該比官方的快一點

簡單吧!!