## 679 - Dropping Balls

Moderator: Board moderators

Examiner
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm

### 679 - Dropping Balls

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
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

### 679-Dropping Balls confusing input

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?
Just another brick in the wall...

123321321
New poster
Posts: 4
Joined: Fri Mar 29, 2013 2:13 pm

### 679 - Dropping Balls

My code is the following:

Code: Select all

``````
AC

``````

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 679 - Dropping Balls

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]
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 679 - Dropping Balls

Precompute the output for all possible inputs.
Check input and AC output for thousands of problems on uDebug!

iceman126
New poster
Posts: 5
Joined: Tue Feb 07, 2012 9:13 pm

### Re: 679 - Dropping Balls

Thank you brainfry713. You saved my time!