Robert Anderson's Blog

蠻簡單的一題
不過蠻有趣的
觀察出規律就可以輕鬆寫出了
 

先求SCC
再來你要求是不是有一個group
可以被其他所有groups到達
一開始我想太複雜

DFS搜尋
State只有3^(N-1)種
最大N = 15
所以可以通過

推導出公式
L(2a + L - 1)/2 = N
=>L(2a + L - 1) = 2N
故對2N相除

Idea #1: Heuristic Pruning
The easiest and most common use for heuristic functions is to prune
the search space. Assume the problem is to find the solution with the
minimum total cost. With an admissible heuristic function, if the cost
of the current solution thus far is A, and the heuristic function returns
B, then the best possible solution which is a child of the current
solution is A+B. If the a solution has been found with cost C, where C
< A+B, there is no reason to continue searching for a solution from
this state.

先做好Precalculation
時間複雜度是O(maxN)
再來每次查詢是O(1)
 

判斷有點多
以下說明有哪些不合法情況
 
1.數量不對型

很簡單的一題
如果你用其他方法做（應該都比較麻煩）
還得注意是不是中間有一堆空白（茶）
 

先找出1 - 10000的質數
再來就是求Consecutive的Sum
用一個table去紀錄結果
這樣看來時間複雜度約O( primes.size() ^ 2 )

先預算好所有答案
因為他規定number不能recurring
所以可以在自己電腦裡面看table要開多大