Loading...

July 24, 2008

我的答案：浙大ACM#1350（The Drunk Jailer）

题目地址

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

我的代码是用 C 写的，运行耗时 0 秒，占用内存 392K，比高手们多出了 8K。在内存控制方面我始终把握得不好，不过比刚开始玩时写用了 STL 和类的 C++ 好多了。 :lol:

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

int main()
{
    int c, i, *cases = 0, *esc = 0;
    scanf("%d", &c);
    if (0 == c)
        return -1;
    cases = (int*)malloc(c * sizeof(int));
    esc = (int*)malloc(c * sizeof(int));
    for (i = 0; i <c; i++)
    {
        scanf("%d", cases + i);
        char* cells = (char*)malloc(*(cases + i) + 1);
        int j;
        for (j = 0; j <(*(cases + i)); j++)
            *(cells + j) = '0';
        *(cells + (*(cases + i))) = '\0';
        for (j = 0; j <(*(cases + i)); j++)
        {
            int k;
            for (k = 0; k <(*(cases + i)); k++)
            {
                if ((j * (1 + k) + k)>= *(cases + i))
                    break;
                if ('0' == *(cells + j * (1 + k) + k))
                    *(cells + j * (1 + k) + k) = '1';
                else if ('1' == *(cells + j * (1 + k) + k))
                    *(cells + j * (1 + k) + k) = '0';
            }
        }
        *(esc + i) = 0;
        for (j = 0; j <(*(cases + i)); j++)
        {
            if ('1' == *(cells + j))
                (*(esc + i))++;
        }
        free(cells);
    }
    free(cases);
    if (esc)
    {
        for (i = 0; i <c; i++)
            printf("%d\n", *(esc + i));
        free(esc);
    }
    return 0;
}

#更新：感谢 Jiang 的留言，经过改进，程序占用内存减少了 4K，hooray！下面是改进后的代码。（起初我以为不在最后把计算结果一起输出会 WA，事实上每次计算结束就输出也是 AC。再次感谢 Jiang！）

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

int main()
{
    int c, i, j, k, n, *cases = 0, e;
    scanf("%d", &c);
    if (0 == c)
        return -1;
    cases = (int*)malloc(c * sizeof(int));
    for (i = 0; i <c; i++)
    {
        e = 0;
        scanf("%d", cases + i);
        n = *(cases + i);
        char* cells = (char*)malloc(n + 1);
        for (j = 0; j <n; j++)
            cells[j] = '0';
        cells[n] = '\0';
        for (j = 0; j <n; j++)
            for (k = j; k <n; k += j + 1)
                cells[k]++;
        for (j = 0; j <n; j++)
        {
            if (1 == cells[j] % 2)
                e++;
        }
        printf("%d\n", e);
        free(cells);
    }
    free(cases);
    return 0;
}

C/C++, 程序设计 /  17 Comments Tags: ,

16Comment(s). Blabla or Trackback

  • Jiang at 16:53 Jul 24, 2008 ₪

    hi 北极，我大概看了一下，不考虑算法，光看程序的话可以做以下优化：
    1. 有一些不用lock/unlock的cell可以直接跳过，把k++改为k+j。另外可以不用每次都check是否lock/unlock，直接累加，最后通过奇偶数来判断escape的数量。for example:
    int k = -1;
    …
    for (j = 1; j <(*(cases + i)); j++)
    {
    k += j;
    while(k<=*(cases + i))
    {
    cells[k]++;
    k+=j;
    }
    k=0;
    }
    for(i=0;i<*(cases+i);i++)
    {
    if(i%2==1)
    numofesc++;
    }
    2. 对时间要求较高的程序可以尽量避免动态内存的分配，比如可以一开始就定义一个数组int cells[MAX],清空时用memset。另外还可以调整变量声明的位置，比如变量k的位置,可以避免大量的出栈入栈指令。
    3. 另外有些动态内存分配我感觉不是很必要，比如esc，得到一个答案可以直接输出，没必要等到最后一起输出。
    4. 你的程序中有很多数组位置的重复计算。

    以上是我的一点浅见：）

  • 北极冰仔 at 18:06 Jul 24, 2008 ₪

    @Jiang 真的有点受宠若惊！非常感谢你能如此认真地读了我的代码（一定很累，哈哈）并给出上面这些意见，我一直苦恼于无法了解到对于同样一个问题，别人的解决方法是什么样子的，也没有什么好的途径能挑出自己编写的代码中存在的问题，所以有时候觉得即使做ACM的题目也未必能使自己的水平有实质性的提高。真的感谢你的指点，我会按照上面的几点改进程序，如果遇到什么问题，还要麻烦你啦。 :-)

  • Jiang at 06:41 Jul 25, 2008 ₪

    建议可以把
    for (j = 0; j <n; j++)
    cells[j] = ‘0′;
    cells[n] = ”;
    替换为memset(cells,0,n+1);
    memset 中存在有大量的优化，一是可以提升速度，二是减小程序体积。

    还可以把
    if (1 == cells[j] % 2)
    e++;
    替换为 e += cells[j]%2;

    进而直接把
    for (j = 0; j <n; j++)
    for (k = j; k <n; k += j + 1)
    cells[k]++;
    for (j = 0; j <n; j++)
    {
    if (1 == cells[j] % 2)
    e++;
    }
    替换为
    for (j = 0; j <n; j++)
    {
    for (k = j; k <n; k += j + 1)
    cells[k]++;
    e+=cells[j]%2;
    }
    这样进一步减少了程序的体积，而且提高了性能（减少了for循环中counter的累加及check）。

  • 北极冰仔 at 09:40 Jul 25, 2008 ₪

    @Jiang 实在太佩服了，相比之下感觉自己的思路实在一般，要多多向你学习！^_^ 我先把上面的方法试试。

  • 偶爱偶家 at 15:42 Jul 25, 2008 ₪

    这个题目谁能帮忙解释一下? 英语太差了, 看不懂3个input的意思, 第一个2是什么, 5和100又是什么?

  • 北极冰仔 at 19:01 Jul 25, 2008 ₪

    @偶爱偶家 第一个2是指下面将会有两行输入，每行输入代表一个例子，5和100是指监狱里号房的数量。

    号房有N间，狱卒就会检查（门开着就锁上，锁着就打开，他在玩游戏-__-）N遍，第一次检查号房1、2、3、4……，第二次检查2、4、6、8……，每三次是3、6、9……，检查结束后就醉倒了，这个时候，号房门打开的囚犯就会越狱啦。

  • 偶爱偶家 at 15:59 Jul 29, 2008 ₪

    谢谢北极兄 我也编了一个玩玩, 怎么知道使用的内存数和运行的时间呢?

  • 偶爱偶家 at 23:36 Jul 29, 2008 ₪

    我是采用位操作的, 也是388k, 不过我估计它测试的数值很小, 大了就很有优势了, 数据内存可以节省将近8倍. 然后走一半的循环, 这样可以节省近一半的时间.

    #define uchar unsigned char
    #define uint unsigned int

    #include
    #include

    int main(void){
    uint icell, icases, *esc;
    uint i, j, k, t;
    uchar *m, *cell, bit, bit_value[]={1,2,4,8,16,32,64,128};

    scanf(”%d”, &icases);
    if (!icases)
    return -1;

    esc = (uint *)malloc(icases * sizeof(uint));

    t = icases;

    while(t–){
    scanf(”%d”, &icell);
    if(!icell)
    continue;
    k=icell/8+1;
    cell = (uchar *)malloc(k);
    for(i=0;i<k;i++){
    m = cell+i;
    *m = (*m | 0xFF) & 0×55;
    }

    m = cell+i-1;
    *m = *m <> (8-icell%8);

    k = (icell/16+1)*8;
    for(i=3; i<k+1; i++){
    bit=(i-1)%8, j=(i-1)/8;
    while((bit + j*8) >bit&0×01==1)
    *m = *m&~bit_value[bit];
    else
    *m = *m|bit_value[bit];
    j+=(bit+i)/8;
    bit=(bit+i)%8;
    }
    }

    j=0;
    k = icell/16+1;
    for(i=icell/8; i>=k; i–){
    m = cell+i;
    while(*m != 0){
    if(*m&0×01==1)
    j++;
    *m = *m >> 1;
    }
    }
    if(k != 1)
    j = icell - k*8 -j;

    for(i=0; i> 1;
    }
    }
    *(esc+t) = j;
    free(cell);
    }

    while(icases–)
    printf(”%d\n”, *(esc+icases));
    free(esc);
    return 0;
    }

  • 偶爱偶家 at 20:25 Jul 30, 2008 ₪

    北极冰仔, 如果要提高程序的运行速度, 可以采用循环一半的方式进行. 过了一半的时候, 其实走一遍就是切换一道门, 这个时候只要统计在走过之前的关着的门就可以了, 也就是走过之后的开的门. 这样当数据量大的话, 就是可以省一半的时间.

  • Jiang at 05:40 Jul 31, 2008 ₪

    “过了一半的时候, 其实走一遍就是切换一道门”,偶爱偶家说的没错，虽然在题目要求的数据量下差别不大，但是到了十万，百万级的时候，差别就会出来。看了你C程序binary操作那一块儿，你C的功力很深，大家交个朋友：）

  • 偶爱偶家 at 08:30 Jul 31, 2008 ₪

    @jiang, 客气了, 本来就是朋友吗

  • 偶爱偶家 at 08:31 Jul 31, 2008 ₪

    北极冰仔, 上面的我说错了, 是一半之前的门是开着的就是开着的, 一半之后的门是关着的是开着的. 听着这话好像很绕口的, 但我也不知道怎么说比较简单

  • 北极冰仔 at 22:53 Aug 01, 2008 ₪

    @偶爱偶家，Jiang 真是不好意思现在才来回复，我二十八号回家啦现在用手机上来才看到留言… 你上面说的循环一半我想明白了，比方说有十个房间，只需要循环五次，从第六次开始只检查那一个就可以了，向二位学习了！另外之前我就想学习如何位操作，只是翻了C的书也没看到有用的部分。我在很多题目里都见过类似这样的要求就是只使用一个字节表示输出，这就应该用到位操作了吧，现在不方便读代码，等我四号到学校后仔细读一下，实在很感谢把你的源代码分享出来，这也是我学习过程中最缺少的资源。

  • 北极冰仔 at 23:01 Aug 01, 2008 ₪

    晕，打了半天字不知道留言成功没有…

  • 偶爱偶家 at 17:18 Aug 05, 2008 ₪

    我把最终的源码留在我的博客上了

    你看最下面的pingback就是我的了.

  • 北极冰仔 at 18:37 Aug 05, 2008 ₪

    @偶爱偶家 看到了^_^

Blabla ↓

Connecting to server...

Back to Top ↑

1Pingbacks & Trackbacks