Page 1 of 1

### 679 - Dropping Balls

Posted: Thu Jun 03, 2004 11:59 am
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).

### 679-Dropping Balls confusing input

Posted: Tue Jun 22, 2004 11:42 am
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?

### 679 - Dropping Balls

Posted: Sat Apr 27, 2013 9:09 pm

My code is the following:

Code: Select all

``````
AC

``````

### Re: 679 - Dropping Balls

Posted: Tue Nov 05, 2013 9:34 pm
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]

### Re: 679 - Dropping Balls

Posted: Wed Nov 06, 2013 10:01 pm
Precompute the output for all possible inputs.

### Re: 679 - Dropping Balls

Posted: Sun Nov 29, 2015 2:58 pm
Thank you brainfry713. You saved my time!