有兩個意思:
(a)排在好人列裡第一個好人,
(b)所有好人中的第一個好人。
本題採用(b),翻成國語就是
所有的好人都不能被殺死啦!
用ACM 151的方法去解,
但是不管演算法再怎麼修,
從k = 1算到k = 13都要花10秒的時間。
最後只好先算好答案再上傳了,囧。
後來參考別人的算法,
發現一招很厲害可以直接算的算則。
因為好人一定是前k個,壞人一定是最後的k個。
(共2k個)。
所以每次數完人頭後,m一定要是第k + 1個之後的數值,
否則就會殺到好人。
以k = 3為例,m直接用5代入。
0 1 2 3 4 5
g g g b b b
從0開始 + 5 - 1,為4,
4不為好人,之後刪掉一個壞人繼續做運算。
0 1 2 3 4
g g g b b
4 + (5 - 1) = 8
8 % 5(現有人口) = 3
3也不為好人,再刪掉一個壞人繼續做運算。
0 1 2 3
g g g b
3 + (5 - 1) = 7
7 % 4(現有人口) = 3
3也不為好人,再刪掉一個壞人。
現有人口為3,即k值。
表示當人口為k值時,即可停止運算,會傳m值。
當loop結束,而人口不為k值,表示殺錯人了,
m + 1從頭繼續運算。
真是好威的方法!
TLE code就不貼了。
用linked list移來移去好蠢,囧。
/* ACM 305 Joseph * mythnc * 2011/12/01 14:33:02 * version 2 * run time: 0.076 */ #include <stdio.h> #define MAX 13 int findm(int); int main(void) { int k, i; int answer[MAX]; for (i = 0; i < MAX; i++) answer[i] = findm(i + 1); while (scanf("%d", &k) && k != 0) printf("%d\n", answer[k - 1]); return 0; } /* findm: return minimum m */ int findm(int k) { int m, re, position; for (m = k + 1; ; m++) { for (position = 0, re = 2 * k; re > k; re--) { position = (position + m - 1) % re; if (position < k) break; } if (re == k) return m; } }
從1開始的版本寫完發現還是從0開始好 = =。
int findm(int k) { int m, re, position; for (m = k + 1; ; m++) { for (re = 2 * k, position = 0; re > k; re--) { if (position == 0) position = m % re; else position = (position + m - 1) % re; if (position <= k && position != 0) break; } if (re == k) return m; } }
沒有留言:
張貼留言