679 - Dropping Balls

[Examiner]

I notice that the reverse of I - 1 (in binary form) is the position of the ball in the last row. For example,

• when n = 4,
  I = 1 = 000 + 1, p = 000 = 0, ans = 0 + 2**3;
  I = 2 = 001 + 1, p = 100 = 4, ans = 4 + 2**3;
  I = 3 = 010 + 1, p = 010 = 2, ans = 2 + 2**3;
  I = 4 = 011 + 1, p = 110 = 6, ans = 6 + 2**3;
  ... .

But my program needs about a second to pass the test. Is there any shortcut?

Answer: stdio.h takes only a quarter of the time (used by iostream).

[helmet]

l is no of test cases and a constant -1 representing the end of the input file


which to use? I am getting WA.Any tricky test cases?

[123321321]

Hello, I have got many WAs with problem 679 - Dropping Balls .... Please help me.

My code is the following:

Code: Select all

AC

[mahade hasan]

getting tle
help need

Code: Select all

#include<stdio.h>

int main()
{
    long I,K,L,M,N,P;
    
    while(scanf("%ld",&P)&&P>0){
        while(P--){
            scanf("%ld %ld",&I,&K);
        bool Tree[1048580]={0};
        
        for(L=1;L<=K;L++){
            M=0;
            N=1;
            while(++M<I){
                if(!Tree[N]){
                    Tree[N]=true;
                    N*=2;
                }
                else{
                    Tree[N]=false;
                    N=N*2+1;
                }
            }
        }
        printf("%ld\n",N);
        }
    }
    return 0;
    
}

[/color]

[brianfry713]

Precompute the output for all possible inputs.

[iceman126]

Thank you brainfry713. You saved my time!