## 699 - The Falling Leaves

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

eXon
New poster
Posts: 17
Joined: Sun Mar 23, 2003 2:04 pm
Location: Russia
Contact:

### 699 RE

I wrote a prog, solving problem #699, but it causes RuntimeError (SIGSEGV):(. What may cause it in muy prog? Please, find out an error in this listing:
[cpp]
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <fstream.h>
#include <string.h>

#ifndef ONLINE_JUDGE

#include <conio.h>

#endif

int finish;
long caseNo;
#ifdef ONLINE_JUDGE
const long MAX = 20000;
#else
const long MAX = 100;
#endif

struct node{
node *left, *right, *root;
long num, pos;
};

node *tree;
long res[MAX], rescnt, min, max;

node *create(node *root = NULL, int num = 0){//creates new node
node *nd = new node;

nd->left = NULL;
nd->right = NULL;
nd->root = root;
nd->num = num;
nd->pos = 0;
return nd;
}

void Input(node *root, int l = 1){//l == 1 means left child, else - right
int x;
node *nd;

cin >> x;
if (x == -1)
return;
nd = create(root, x);
if (l){
root->left = nd;
nd->pos = root->pos - 1;//pos may be a negative
}
else{
root->right = nd;
nd->pos = root->pos + 1;
}
if (nd->pos < min)
min = nd->pos;// I store min and max pos to calculate offset(see below)
if (nd->pos > max)
max = nd->pos;
Input(nd, 1);//Input for left subtree
Input(nd, 0);//Input for right subtree
}

void calc(node *r){
if (!r)
return;
res[r->pos - min] += r->num;//in res I store summary of leaves weight
calc(r->left);//for left subtre
calc(r->right);//for right subtree
}

void Solve(){
memset(res, 0, sizeof res);
rescnt = max - min + 1;//count of positions
calc(tree);//fills res with result values
}

void Output()
{
cout << "Case " << caseNo + 1 << ":" << endl;
for (int i = 0; i < rescnt; i++){
if (i)
cout << " ";
cout << res;
}
delete tree;
}

//#define DEBUG
#define MULTIINPUT

int main(){
#ifndef ONLINE_JUDGE
ifstream is = "input.txt";
cin = is;
#ifdef DEBUG
clrscr();
cout << endl;
#else
ofstream os = "output.txt";
cout = os;
#endif
#endif

#ifdef MULTIINPUT
for (caseNo = 0; !finish; caseNo++){
#endif
int x;

min = 0xFFFFF;
max = -min;
cin >> x;
if (x == -1)//end of file
return 0;
tree = create();//creates tree root
tree->num = x;//weight
Input(tree, 1);//Input for left subtree
Input(tree, 0);//Input for right subtree
#ifdef MULTIINPUT
if (finish)
return 0;
#endif
Solve();
if (caseNo)
cout << endl;
Output();
#ifdef MULTIINPUT
cout << endl;
}
#endif
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]
Who am I? Just eXon...
zilnus
New poster
Posts: 9
Joined: Sat Mar 08, 2003 11:59 am

### 699 - The Falling Leaves

[cpp]

#include <iostream.h>
#include <string.h>
#include <stdio.h>

void rekursif(int heap[],int i,int *logik);
void rekursif2(int heap[],int hasil[],int i,int j);

int main()
{
char input;
int heap,i,x,logik,hasil,kasus;

logik = 1;
kasus = 0;
while(1)
{
if (!logik) break;
for(i=0;i<1000;i++) {
heap = -1;
hasil = 0;
}
rekursif(heap,1,&logik);
if (logik)
{
kasus++;
rekursif2(heap,hasil,1,500);
if (kasus > 1) printf("\n");
printf("Case %d:\n",kasus);
for(i=0;i<1000;i++) {
if (hasil != 0)
printf("%d ",hasil);
}
printf("\n");
}
}
return 0;
}

void rekursif(int heap[],int i,int *logik) {
int in;

scanf("%d",&in);
if ( (in == -1)&&(i==1) ) *logik = 0;
if (in != -1)
{
heap = in;
rekursif(heap,2*i,logik);
rekursif(heap,2*i+1,logik);
}
}

void rekursif2(int heap[],int hasil[],int i,int j)
{
hasil[j] += heap;

if (heap[2*i] != -1)
rekursif2(heap,hasil,2*i,j-1);
if (heap[2*i+1] != -1)
rekursif2(heap,hasil,2*i+1,j+1);
}
[/cpp]

Please help me. Is there any test case that make runtime error ? Thanx everyone.
beeplove
New poster
Posts: 17
Joined: Tue Sep 30, 2003 9:28 pm
Location: Boston, MA, USA
Contact:

### 699

Can anyone please submit more sample input and sample output for problem 699.
You help would be appreciated.

Thanks in advance.
green leaf
New poster
Posts: 1
Joined: Tue Jun 01, 2004 12:20 pm

### 699 WA... and I don't understand why! ("The falling lea

Hi!
I get WA but I don't understand what's wrong in my code.
Please, will you give me a hand?
Thanks very much!
Bye [c]
#include <stdio.h>

void fun (int);

int a , b ; /* a: left subtree's + root's piles
b: rigth subtree's piles */

int main(){

int i, num;

num = 1;

while (1){

/* at beginning the piles have value 0 */
for (i=0; i<20; i++)
a = b = 0;

/* calls the function */
fun(0);

/* check if there are other test cases */
if (a == 0)
return(0);
else {
/* print the result */
printf("Case %d:\n", num);
for (i=0; b>0; i++);
for (i=i-1; i>=0; i--)
printf("%d ", b);
printf("%d", a);
for (i=1; a>0; i++)
printf(" %d", a);
printf("\n\n");
}

num++; /* test cases counter */

}

return(0);
}

/*
Read root's value and adds its value to the right pile:
to a[ind] if ind>=0, to b[-ind-1] otherwise.
*/
void fun (int ind){

int value;

scanf("%d", &value); /* read root's value */

if (value != -1){
/* add the value to the pile */
if (ind >= 0)
a[ind] += value;
else
b[-ind-1] += value;

/* recursive calls */
fun(ind-1); /* left subtree */
fun(ind+1); /* rigth subtree */
}
}
[/c]

Maybe it's better I explain my algorithm.
The value of the piles of leaves are stored in 2 arrays of int:
- a contains the value of the pile under the root of the tree
- a, a, ... the values of the piles on the rigth of the root (from center to rigth)
- b, b, ... the values of the piles on the left of the root (from center to left).
The result is computed by recursive calls of the function "fun".
The variable ind identifies the pile on which the leaves of the current root will fall. If ind=0 we are considering the real root of the tree, if ind>0
we are on the rigth, else we are onthe left. After adding the leaves to the rigth pile, there are 2 recursive calls respectively for the left subtree and for the rigth one.

I tested the program for several input cases and I obtained the result I was expecting, but online-judge always tells me WA. Input:

Code: Select all

``````5 7 -1 6 -1 -1 3 -1 -1

8 2 9 -1 -1 6 5 -1 -1 12 -1
-1 3 7 -1 -1 -1

14 12 5 7 -1 -1 -1 2 3 -1 -1 4 -1 -1 1 2 11 -1 22 -1 -1 -1 3 -1 1 2 -1 -1 -1

1 3 4 -1 5 6 -1 2 -1 -1 2 -1 -1 -1 -1

-1
``````
Output:

Code: Select all

``````Case 1:
7 11 3

Case 2:
9 7 21 15

Case 3:
7 5 26 40 5 5 1

Case 4:
10 10 3
``````
Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

### Misundarstanding in 699 , "The Falling Leaves".

I can not figure out with my poor english what means in the problem explanation the phrase:

"...This display must start in column 1, and will not exceed the width of an 80-character line...."

that we will take as a fact that the output lines will be less than 80 characters, or that we should take care to change line when the line becomes such big?

Thanks in advance for any reply,
Grazyna
DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 699 - The Falling Leaves

Grazyna wrote:I can not figure out with my poor english what means in the problem explanation the phrase:

"...This display must start in column 1, and will not exceed the width of an 80-character line...."

that we will take as a fact that the output lines will be less than 80 characters, or that we should take care to change line when the line becomes such big?

Thanks in advance for any reply,
Grazyna
Hi Grazyna,

You don't need to consider the changing line when output, just output your answers one by one is fine. Since I also did not consider that, I still got A.C.
Last edited by DD on Sun Nov 16, 2008 8:23 am, edited 1 time in total.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
justcodeit
New poster
Posts: 4
Joined: Fri Dec 17, 2010 8:28 am

### Re: 699 - WA

I think my code is correct i tried many test case still i m getting wrong answer

Code: Select all

``````#include<iostream>
#include<queue>
using namespace std;
struct node
{
int info;
int pos;
node *left;
node *right;
};
int max,min;
node * left_input(int a,int *pmax,int *pmin);
node * right_input(int a,int *pmax,int *pmin);
node * left_input(int a,int *pmax,int *pmin)
{
if(a>*pmax)
*pmax=a;
if(a<*pmin)
*pmin=a;
int in;
cin>>in;
if(in==-1)
return NULL;
node *n=new node;
n->info=in;
n->pos=a;
n->left=left_input((n->pos)-1,pmax,pmin);
n->right=right_input((n->pos)+1,pmax,pmin);
return n;
}
node * right_input(int a,int *pmax,int *pmin)
{
if(a>*pmax)
*pmax=a;
if(a<*pmin)
*pmin=a;
int in;
cin>>in;
if(in==-1)
return NULL;
node *n=new node;
n->info=in;
n->pos=a;
n->left=left_input((n->pos)-1,pmax,pmin);
n->right=right_input((n->pos)+1,pmax,pmin);
return n;
}

void inorder(node *r,int arr[])
{
if(r==NULL)
return;
inorder(r->left,arr);
arr[r->pos+50]+=r->info;
inorder(r->right,arr);
}

int main()
{
int in,t=0;
while(cin>>in && in!=-1)
{
node *root=new node;
int max=0,min=0;
root->pos=0;
root->info=in;
root->left=left_input((root->pos)-1,&max,&min);
root->right=right_input((root->pos)+1,&max,&min);
int arr={0};
inorder(root,arr);
cout<<"Case "<<++t<<":"<<endl;
for(int i=min+51;i<max+50;i++)
{
cout<<arr[i];
if(i==max+50-1)
cout<<endl;
else
cout<<" ";
}
cout<<endl;
}

return 0;
}
``````
PLease help.....
Gabrielwer
New poster
Posts: 6
Joined: Thu Sep 08, 2011 12:27 pm

### Re: 699 - The Falling Leaves

do you get the wrong answers all the time? try to reinstall spy phone the system