开发者

Need help with this programming problem involving flipping coins

Im trying to solve the flipping coins problem on codechef.com (http://www.codechef.com/problems/FLIPCOIN/) My code is in C, and i te开发者_运维技巧sted it using gcc v4.4.3 on my machine running Linux,and my program works for the sample input provided. However, on uploading to the judge i get the message "Wrong Answer". In my program i represent the flipping of coins by the toggling of bits.I think my algorithm is correct,and im not able to come up with a case where it would fail. Below is my code. Any help would be really appreciated.

Thank You.

#include <stdio.h>

long int n=0,temp,number_of_coins,number_of_inputs,bit_mask;
long int number_of_ones(long int i) //Return the number of bits set
{
   return __builtin_popcountl(i);
}
int main(void)
{
    long int ctr,lower,upper,length;
    int op;

    scanf("%ld %ld",&number_of_coins,&number_of_inputs);
    length = number_of_coins-1;
    for(ctr = 0 ; ctr < number_of_inputs;ctr++) //Main loop
    {
        scanf("%d %ld %ld",&op,&lower,&upper);
        bit_mask = ((1 << length-lower+1)-1) & ~((1 << length-upper)-1);

        if(op == 0)
        {   

            n ^= bit_mask ; //Toggle the bits in the range lower to upper

        }
        else
        {
            temp = n;
            temp &= bit_mask;
            printf("%ld\n",number_of_ones(temp)); //Print number of bits set
        }


    }



    return 0;

}


Since you use a bit sequence stored in a long int to represent the coins, your code won't work with more than 32 coins (or however many bits are in a long). The site specifies that there can be up to 100000 coins though.


There is probably a problem with the CodeChef method of checking the results, as i have gotten the same answer as well. There is not a problem with your code.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜