ZJU ACM #1350(The Drunk Jailer) : 偶爱偶家

ZJU ACM #1350(The Drunk Jailer)

枫叶

前几天在北极冰仔的博客上看到了一题ACM － the drunk jailer，突然有兴趣玩玩。我已经从大学毕业之后就没有再碰过C语言这么个玩意了而已了（除了上次用C语言写了一个google calendar的东东外）

题目如下：

A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked.

One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey, and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the hall locking every other cell (cells 2, 4, 6, …). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, …). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He repeats this for n rounds, takes a final drink, and passes out.

Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.

Given the number of cells, determine how many prisoners escape jail.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

Output

For each line, you must print out the number of prisoners that escape when the prison has n cells.

Sample Input

2

5

100

Sample Output

2

10

简单点翻译一下：

有一个监狱有n个牢房，每个牢房有一个罪犯，有一个狱卒一天闲着没事就开始喝酒。

喝了第一遍酒之后，把所有的牢门都打开了；然后喝了第二遍酒之后，把所有整除2的牢门给切换了一下状态（就是把开着的门关了，关着的门开了）；第三遍也是如何……，直到喝了n遍的酒，跑了n遍次数后，他终于醉倒了。

然后罪犯发现门开了，他们就开始越狱。

结果就是请问有多少的罪犯越狱了（只有门开着的才可以越狱）

输入

2（这是题目做的次数）

5（第一次设定牢房数5间）

100（第二次设定牢房数100间）

输出

2（第一次5间牢房的越狱数）

10（第二次100间牢房的越狱数）

正好这几天也没事干，所以就把这个题目给做了一下；其实做编程最有意思的是算法，当然这个东西我是不懂的，所以我就凭借着感觉和直观来写程序。

我觉得这题目中有两个点可以掌握，用来优化程序：

1、当大于n/2的时候，每跑一轮，只能切换一扇门，所以我觉得这个时候不需要再循环了，直接在后面统计开门的时候统计大于n/2的门哪些是关着的，其实这些关着的门就是最后会被打开的；

2、每一扇门其实就两个状态，一个是开，一个是关；如果用二进制表示的话，就是1、0，所以可以用一个位表示一扇门，这样比用一个字节表示一扇门可以节省8倍的内存（一个字节8个位，如果用二进制操作，就可以表示8扇门）

最后我按照上述原则写了两套程序：

程序一（不考虑优化点1，也就是说循环N遍，跑了N圈），这样的程序通俗易懂，读起来比较方便。

#define uint unsigned int
#define uchar unsigned char

#include <stdio.h>
#include <malloc.h>

int main(void){
    uint i, j, k, *cases, c, cell;
    uchar *p, *cells, bit, mask[]={1,2,4,8,16,32,64,128};

    scanf("%d",&c);

    if(!c)
        return -1;

    cases = (uint *)malloc((2*c+1) * sizeof(uint));

    *cases = c;

    while(c){
        scanf("%d",cases+2*c);

        k = *(cases+2*c) > k ? *(cases+2*c) : k;

        *(cases+2*c-1) = 0;

        c--;
    }

    if(!k)
        return -1;

    cells = (uchar *)malloc((k/8+1) * sizeof(uchar));

    c = *cases;

    while(c){
        cell = *(cases+2*c);

        k = cell/8+1;

        for(i=0;i<k;i++){
            p = cells+i;
            *p = (*p & 0x0) | 0x55;
        }

        for(i=3; i<=cell; i++){
            bit = (i-1)%8, j = (i-1)/8;
            while(j<k){
                p = cells+j;
                if(*p>>bit&0x01==1)
                    *p = *p&~mask[bit];
                else
                    *p = *p|mask[bit];
                j += (bit+i)/8;
                bit = (bit+i)%8;
            }
        }

        p = cells + k -1;

        *p = *p << (8-cell%8);
        *p = *p >> (8-cell%8);

        j=0;

        for(i=0; i<k; i++){
            p = cells+i;
            while(*p != 0){
                if(*p&0x01==1)
                    j++;
                *p = *p >> 1;
            }
        }
        *(cases+2*c-1) = j;
        c--;
    }

    free(cells);

    c = *cases;

    while(c){
        printf("%d\n",*(cases+2*c-1));
        c--;
    }

    free(cases);

    return 0;
}

程序二（两点都优化），这样的程序就比较晦涩些了，但优化的效果应该比较好！

#define uint unsigned int
#define uchar unsigned char

#include <stdio.h>
#include <malloc.h>

int main(void){
    uint i, j, k, *cases, c, cell;
    uchar *p, *cells, bit, mask[]={1,2,4,8,16,32,64,128};

    scanf("%d",&c);

    if(!c)
        return -1;

    cases = (uint *)malloc((2*c+1) * sizeof(uint));

    *cases = c;

    while(c){
        scanf("%d",cases+2*c);

        k = *(cases+2*c) > k ? *(cases+2*c) : k;

        *(cases+2*c-1) = 0;

        c--;
    }

    if(!k)
        return -1;

    cells = (uchar *)malloc((k/8+1) * sizeof(uchar));

    c = *cases;

    while(c){
        cell = *(cases+2*c);

        k = cell/8+1;

        for(i=0;i<k;i++){
            p = cells+i;
            *p = (*p & 0x0) | 0x55;
        }

        cell = (cell/16+1)*8;

        for(i=3; i<=cell; i++){
            bit = (i-1)%8, j = (i-1)/8;
            while(j<k){
                p = cells+j;
                if(*p>>bit&0x01==1)
                    *p = *p&~mask[bit];
                else
                    *p = *p|mask[bit];
                j += (bit+i)/8;
                bit = (bit+i)%8;
            }
        }

        cell = *(cases+2*c);

        p = cells + k -1;

        *p = *p << (8-cell%8);
        *p = *p >> (8-cell%8);

        j=0;

        k = cell/16+1;

        for(i=cell/8; i>=k; i--){
            p = cells+i;
            while(*p != 0){
                if(*p&0x01==1)
                    j++;
                *p = *p >> 1;
            }
        }
        if(cell > 8 )
            j = cell - k*8 -j;

        for(i=0; i<k; i++){
            p = cells+i;
            while(*p != 0){
                if(*p&0x01==1)
                    j++;
                *p = *p >> 1;
            }
        }
        *(cases+2*c-1) = j;
        c--;
    }

    free(cells);

    c = *cases;

    while(c){
        printf("%d\n",*(cases+2*c-1));
        c--;
    }

    free(cases);

    return 0;
}