#include
#include
/*
Theory of operation: We know the output line is no more than 80 columns.
So if we start with an array of 100 integers, we've got more than
enough integers to span the area where the leaves will fall. We
assume that the tree will be 'rooted' at the center of the ground.
Since this is a binary tree, every tree (if it exists), consists
of at most two subtrees, one to the left, and one to the right.
For the left subtree, we move one position left (x-1) and center
the subtree at that point. For the right subtree, we move one
position to the right (x+1) and center the subtree at that point.
If a subtree has a value for the head of that tree, that value is
the number of leaves for that position. We add that value to the
contents of our array at our given position. We then recursively
look to the left subtree (with the call subtree(x-1)) and to the
right subtree (with subtree(x+1)).
*/
int ground[100];
int ref=50;
int dir=0;
int subtree(int x)
{
char input[10];
int val;
/* grab the next number */
fscanf(stdin,"%s",input);
val=atoi(input);
if (val!=-1) {
/* subtree has a value... 'drop' the leaf into the
current slot */
ground[x]+=val;
/* go left... */
subtree(x-1);
/* go right... */
subtree(x+1);
return 0;
}
return 1; /* ignored for all but main() */
}
void print_ground(int num)
{
int i;
int started;
printf("Case %d:\n",num);
started=0;
for (i=0;i<100;i++) {
/* don't print anything if it's zero... and there
could be lots of zeros before any leaves are
found. */
if (ground[i]!=0) {
started=1;
printf("%d ",ground[i]);
} else if (started==1) {
/* all done! */
printf("\n\n");
return;
}
}
}
int main()
{
int done;
int num;
int i;
printf("Problem 699 by team X\n");
num=1;
done=0;
while(!done) {
/* initialize the 'ground' */
for(i=0;i<100;i++)
ground[i]=0;
/* shake the tree... start 'half-way' into the
array to leave lots of room for the leaves.
*/
done = subtree(50);
/* if the tree existed, then
print out the leaf counts */
if (!done)
print_ground(num);
num++;
}
}