699 - The Falling Leaves

[eXon]

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]

[zilnus]

[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[255];
int heap[1000],i,x,logik,hasil[1000],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]

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

Thanks in advance.

[green leaf]

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 [20], b [20]; /* 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] == 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[0]);
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[0] contains the value of the pile under the root of the tree
- a[1], a[2], ... the values of the piles on the rigth of the root (from center to rigth)
- b[0], b[1], ... 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]

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]

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.

[justcodeit]

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[80]={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]

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