Johnny and the Beanstalk

When it results in a runtime error, it would be great if I can see the error somewhere. It would be of great help to find where and why the error comes.

Wanted to confirm : johnny can eat from any level except the last one...am i rit ?

we need to make sure when k==1 leaves at level1 = 1;

This is fixed. Please check now.

Is there a trick to do this in Java? BigInteger performs terribly when trying to manipulate a number 301030 digits long. That's with the simple test case of having a stalk with 999,999 levels with 0 leaves and then 2^1000000 leaves at the millionth level. It's far worse when I need to process large numbers at ever level up to the millionth level.

You don't need big integers for th.is problem in any language. See Tutorial for Johnny and the Bean Stalk for solution methods.

i have successfully submitted this problem but my prog has runtime of 12.36sec whereas thr r other submissions havng runtime of just 0.2sec in the same language c++, so how is that possible?can anyone tell? 

after submission its showing accepted for all testcases where max(k)=1000000 but gives wrong answer when max(k)=6 only...can any1 help me out on what could i be missing??

It says it accepts answers in C++ but refuses my submission and tells me that the it won't take answers in this language for this problem.

This is fixed. It should work now.

Hi ,

for some reason I keep on failing on the first test (the one with 6 levels) . Any hint about what testcase might fail my prog ?

Thanks !

same here , i keep failing for 1st case with 6 levels..

any hints plz ..

got it at last ,

we were not taking all levels as input , wich were passed on to next test cases..

I swear the people on this site suck at writing descriptions for their problems.  ;o

plz help.

#include<stdio.h>
int main()
{
long int t,k,cur,n,i,no_of_stems,next;
int flag ;
scanf("%d",&n);
t=0;
while(t<n)
{
scanf("%d",&k);
flag=1;
i=0;
//scanf("%d",&cur);

no_of_stems=1;
while(i<k)
{
scanf("%d",&next);
if(no_of_stems<next)
{
flag=0;           
break;
}
no_of_stems=2*(no_of_stems-next);
i++;
}
/*if(flag!=0)
{
scanf("%d",&next);
if(no_of_stems*2!=next)
flag=0;                
}*/
if(no_of_stems!=0||flag==0)
{
while(i<k)
{          scanf("%d",&next);               
i++;
}
printf("No");
}
else if(flag==1)
printf("Yes");
t++;
}
return 0;
}                
why this code returns wrong answer  for max(k)=6

Please read the FAQ.

Testing your code properly will reveal multiple easy to fix errors.

isn't the second test case given in the problem statement wrong?? shouldn't it give 'Yes' as the answer??

This is my line of reasoning:

1st level: 0 leaves i.e. 2 stems

2nd level: 0 leaves i.e. 2x2=4 stems

3rd level: can have maximum of 4 leaves i.e. 3 leaves is a permissible soln.

Correct me if i am wrong..

What do you plan to do with the 4th stem? You can't just ignore it entirely.

hey, can somebody plz xplain y its not workin for max(k)=6

plz..plz

well my code is working fine for all except one for max(k)=100000 but how can this be...

can any one explain its not working for test case 3:

please help..!!!

Why does it say "Time Limit Exceeded" on Test #6 when supposedly it only took 0.08s for my code to complete the test?

Somebody please tell me why am I getting a wrong answer for max(k)=6 ,

http://www.codechef.com/viewsolution/285066

i had many troubles with this one.

as you go counting the stems, it should never go below zero (even if the total is positive), that's why my correct-algorithm did not pass the 3rd test case.

Can someone help me with my code? Among the 6 test cases, it passed 4. Only Test #1 (k=6) and Test #3(k=1000000) output wrong answer. My code follows the 2nd solution the tutorial provides. Thanks in advance !!!

 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <math.h>
using namespace std;

int main(){
 int cases;
 scanf("%d",&cases);
 while(cases-->0){
  long length;
  scanf("%ld",&length);
  long arr[length];
  for(long i=0;i<length;i++) {
   scanf("%ld",&arr[i]);
  }

  long stems=0;
  int no=0;
  
  if(length==1){ // only one level one leaf
   if(arr[0]==1){
    printf("Yesn");
   }
   else{
    printf("Non");
   }
   break;
  }
  if(arr[length-1]> pow(2,length-1)){ // cannot exceed max
   printf("Non");
   break;
  }
  
  for(long i=length-1;i>0;i--){
   stems=arr[i]+stems;
   if(stems%2!=0){
    printf("Non");
    no=1;
    break;
   }
   stems/=2;
  }
  if(stems==1 && no==0){
   printf("Yesn");
  }   
 }
}

#include <iostream>
#include <math.h>
using namespace std;

int main(){
 int cases;
 scanf("%d",&cases);
 while(cases-->0){
  long length;
  scanf("%ld",&length);
  long arr[length];
  for(long i=0;i<length;i++) {
   scanf("%ld",&arr[i]);
  }

  long stems=0;
  int no=0;
  
  if(length==1){ // only one level one leaf
   if(arr[0]==1){
    printf("Yesn");
   }
   else{
    printf("Non");
   }
   break;
  }
  if(arr[length-1]> pow(2,length-1)){ // cannot exceed max
   printf("Non");
   break;
  }
  
  for(long i=length-1;i>0;i--){
   stems=arr[i]+stems;
   if(stems%2!=0){
    printf("Non");
    no=1;
    break;
   }
   stems/=2;
  }
  if(stems==1 && no==0){
   printf("Yesn");
  }   
 }
}

@above pow(2,length) can be a huge number2^(10,6)

now whats the problem with this.. i m getting wrong ans..

[code]

#include<iostream>
using namespace std;
int main()
{
int t,i,j,l,flag=0;
int *a,*x;
//a stores leaves and x stores stems
cin>>t;
a = new int[t];
x = new int[t];
for(i=0;i<t;i++)
{
cin>>l;
for(j=0;j<l;j++)
{cin>>a[j];}
x[0]=1;
for(j=1;j<l;j++)
{
x[j]=x[j-1]*2-a[j];if(x[j]<0){flag=1;break;}
}
if( flag==0 && x[l-1]==0)
cout<<"Yesn";
else cout<<"Non";
}
return 0;
}
[/code]

@ a jhey.. don't flaunt ur attitude here. The world doesn't go the way u think. This is a forum for discussions only

The time and memory for my submission is showing 0 and 0 is this correct?

Hello admin,

I am getting error while submitting:

:( internal error occurred in the system

what to do?

When I attempt to submit a haskell solution, the system refuses with "You can't submit in this language for this problem. Try link.".  The list of accepted languages includes HASK.  Thank you.

I resubmitted the solution submitted by Rajesh Kumar and i got time 2.6 sec and Mem 2.5 ......... why this difference????

why do I always get answer wrong with test levels 6 ?

Any hint?

To Admin:

One thing that's conceptually shouldn't be there in this problem is- Once you have said the number of levels is 'K', then it should also be checked that there should be at least one stem reaching level 'K'. But I don't think its insured in here. You can give number of leaves at level 1 is 1 and then at rest all the levels number of leaves is 0. But does this imply that the height of the beanstalk is 'K'. No! Height of the beanstalk in this case is 1. So please look into it.

Thank you.

why this is giving wrong answer???????

#include<iostream>
using namespace std;
int main()
{
int t,j;
long int leaf,total_node,level;

cin>>t;
for(int i=0;i<t;++i)
{
cin>>level;
total_node=1;
int flag=1;
for(j=1;j<level;++j)//upto 2nd last level
{
cin>>leaf;
if( leaf>total_node )
{
flag=0;   
}
total_node=(total_node-leaf)*2;
}
cin>>leaf;//last level,all nodes should be leaf

if( leaf!=total_node )
{
flag=0;
}

if( 1==flag )
{
cout<<"nYES";
}
else
{
cout<<"nNO";
}
}
return 0;
}

Hi Guys,

some points to understand this problem :

1. Stem can be converted into single leaf.

2. Stem can either be a leaf into next level else split into 2 stems

3. before starting problem, consider stem as 1 so from level 1 onwards you can do calculations like if leaf if 0 then you can make stems twice.

Problem description was not so clear to understand.

Why is this wrong:

#include<stdio.h>

int check(int [],int);

main()

{

int t,i;

scanf("%d",&t);

int m,lev[1000005],j;

for(i=1;i<=t;i++)

{ scanf("%d",&m);

for(j=1;j<=m;j++)

scanf("%d",&lev[j]);

if(check(lev,m))

printf("Yesn");

else

printf("Non");

}

return 0;

}

int check(int lev[],int n)

{

if(n==1)

{ if(lev[1]==1)

return 1;

else

return 0;}

if(lev[n]%2!=0)

return 0;

int i=n;

while(i>1)

{ lev[i-1]+=lev[i]/2;

if(lev[n-1]%2!=0)

return 0;

i--;

}

if(lev[1]!=1)

return 0;

return 1;

}