679 - Dropping Balls

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

679 - Dropping Balls

Post by Examiner » 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).

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

679-Dropping Balls confusing input

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

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

679 - Dropping Balls

Post by 123321321 » Sat Apr 27, 2013 9:09 pm

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

My code is the following:

Code: Select all


AC


User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 679 - Dropping Balls

Post by mahade hasan » 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]
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

Post by brianfry713 » Wed Nov 06, 2013 10:01 pm

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

Post by iceman126 » Sun Nov 29, 2015 2:58 pm

Thank you brainfry713. You saved my time!

Post Reply

Return to “Volume 6 (600-699)”