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次方, 會通電一次

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

簡單吧!!