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;
    }
}