ACM 151 Power Crisis

一開始的想法：
難道是弄個array然後一個一個慢慢數？
好笨的方法……
結果看來也沒其他方法 orz。

由於覺得有別的方法，
於是就用array + linklist的寫法解，
當然指標是很會飄的（抖）。

不過看來我的解法也是一個一個慢慢數，囧。

在網路上看到幾個151的AC code，
不過有些在n = 14時，答案都錯，
看來測資沒有n = 14這組 =w=。

/* ACM 151 Power Crisis
 * mythnc
 * 2011/11/09 10:55:26   
 * run time: 0.004
 */
#include <stdio.h>

#define MAXN 99

typedef struct list {
    int i;
    struct list *next;
    struct list *pre;
} List;

void init(List *array, int n);
int findm(List *p, int n);
void link(List *p, int n);

int main(void)
{
    List array[MAXN];
    int n;

    while (scanf("%d", &n) && n != 0) {
        init(array, n);
        printf("%d\n", findm(array, n));
    }
    return 0;
}

/* init: initialize array */
void init(List *array, int n)
{
    int i;

    for (i = 0; i < n; i++)
        array[i].i = i + 1;
}

/* findm: find and return the number m */
int findm(List *ary, int n)
{
    int count, i, m;
    List *p;

    for (m = 1; ; m++) {  /* find m */
        link(ary, n);     /* link all again */
        p = ary;
        count = 1;
        while (count < n) {
            p->pre->next = p->next;  /* link arrange */
            p->next->pre = p->pre;
            for (i = 0; i < m; i++)  /* move */
                p = p->next;
            count++;
            if (p->i == 13) {
                if (count == n)
                    return m;
                break;
            }
        }
    }
}

/* link: link array elements one by one
 * in a circle */
void link(List *p, int n)
{
    int i;

    i = 0;
    p[i].next = &p[i + 1];
    p[i].pre = &p[n - 1];
    for (i = 1; i < n - 1; i++) {
        p[i].next = &p[i + 1];
        p[i].pre = &p[i - 1];
    }
    p[i].next = &p[0];
    p[i].pre = &p[i - 1];
}