20111201

ACM 305 Joseph

「before the first good guy」,
有兩個意思:
(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;
    }
}

沒有留言: