839 - Not so Mobile

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

Moderator: Board moderators

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon Oct 06, 2003 4:54 am

You need to read the entire mobile, even if an earlier has already caused balanced to be set to 0. So, if you went down the left side, determined one of those submobiles is out of whack, set balance to 0, go back up your tree, start going to the right, and then only read the first one, 'cause any subsequent reads will get stopped by the balanced variable. Thus, the second mobile is not being read from the correct starting position.

User avatar
Sarmento
New poster
Posts: 15
Joined: Tue Apr 22, 2003 9:50 pm
Location: Lisboa, Portugal

Post by Sarmento » Mon Oct 06, 2003 6:49 pm

You were right. Got AC. Thanks, UFP2161.
-----------------
Jo

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

839 any one giver some critical input / output?

Post by efr_shovo » Wed Sep 29, 2004 9:26 am

839 any one giver some critical input / output?

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Nov 15, 2004 5:14 pm

Hi, Just Got Acc in this problem :D ....so I thought I should keep some hints to help those who got frustrated trying to understand the problem description( u know, its not very clear).....

The problem is very easy except that the description is not clear enough.

* do- d1*w1 and d2*w2 only in the 1st step

* where there is nomore submobile(neither left nor right), check d1*w1==d2*w2 or not, set global status to mark answer but dont stop right now if u get a negative answer...continue....

* Recursively sum up right and left weight and u must compute all the weights both in left and right submobiles for the 1st mobile

hope this helps......no critical input.....quit simple...huh? :wink:
Jalal : AIUB SPARKS

Sargonmetal
New poster
Posts: 1
Joined: Sat Mar 12, 2005 6:35 pm

Post by Sargonmetal » Sat Mar 12, 2005 7:41 pm

I am desperate to solve this problem.
I can't find any error and all I get is WA.
Please, somebody help me!
Here is my code:

Code: Select all

#include <stdio.h>

#define MAXLINES 1000

int mobile[MAXLINES][4];
/*int balanced=1;*/

int read_mobile(int*);
int work(int);
int calculate_level(int);
int print_mob(int);

int read_mobile(int *size)
{

       int i, j, t, space;

       char ch;
       for(i=0;i<MAXLINES;i++)
       {
		ch=getchar();
		j=0;
		t=0;
		space=0;
		if(ch=='\n') break;
		while (j<4) 
		{
			if (ch == EOF) 
			{
				*size=i;
				return 0;
			}
			if (ch == '\n')
				break;
			if (isdigit (ch))
			{
				space=0;
				t = (t*10) + (ch-'0');
			}
			else
			{
				if (space == 0)
				{
				/*printf("JUMP %d, jumdata %d, isneg*t %d\n", data[jumdata], jumdata, isneg*t);*/
					mobile[i][j++] = t;
					t = 0;
					space++;
				}
			}
			ch = getchar();
		}
		mobile[i][j++] = t;
		
      	}

	
      *size=i;

      return 0;

}

int work(int level)
{

        int wl, wr, dl, dr;
	int balanced;

       dl=mobile[level][1];
       dr=mobile[level][3];

	/*if (level>20) return -1;
       printf("Current level: %d = %d %d %d %d\n", level, mobile[level][0], mobile[level][1], mobile[level][2], mobile[level][3]);*/

       if (mobile[level][0] == 0)
       {
               wl=work(level+1);
               /*if (wl==-1) return -1;*/
       }

       else
               wl=mobile[level][0];

       if (mobile[level][2] == 0)
       {
               level=calculate_level(level);
               wr=work(level);
               /*if (wr==-1) return -1;*/
       }

       else
               wr=mobile[level][2];

       balanced = (wl*dl==wr*dr);
       /*printf("wl*dl: %d, wr*dr: %d, wl: %d, wr: %d, balanced?: %d\n", wl*dl, wr*dr, wl, wr, balanced);*/

	if (balanced==0) return -1;
	else return wr+wl;

}

int calculate_level(int level)
{
       int aux=0, i=0;
       if (mobile[level][0]==0)
       		level++;

       while(mobile[level][0]==0 || aux>0)
       {
               if (mobile[level][2]==0) aux++;
               else aux--;
               level++;
       }
       level++;
       level+=aux;
       /*printf("Busca level: %d %d %d %d, aux: %d, level: %d\n", mobile[level][0], mobile[level][1], mobile[level][2], mobile[level][3], aux, level);*/
       return level;
}

int main()

{

       int ninputs, size=0, i,j, result;
       char a;

       scanf("%d\n", &ninputs);

       	for (i=0; i<ninputs; i++)
       	{
               	read_mobile(&size);

               result=work(0);
               if (result==-1) printf("NO\n");
               else printf("YES\n", result);
               /*print_mob(size);*/
               if(i!=ninputs-1) printf("\n");

       }

       return 0;
}
Thanks a lot

szstream
New poster
Posts: 4
Joined: Sat Feb 09, 2013 12:05 am

839 - Not so Mobile

Post by szstream » Sat Mar 30, 2013 3:46 pm

why do I always get WA?
Who can help me find out the problem?
Here are my code:

Code: Select all

#include<stdio.h>
#include<iostream>
using namespace std;
struct node{
	int llen;
	int lvalue;
	int rlen;
	int rvalue;
	int value;
	node* lchild;
	node* rchild;
};
int in[4];
int ok;
node* build()
{
	for(int i=0;i<4;i++)
	cin>>in[i];
	node* p=new node;
	p->llen=in[1];
	p->rlen=in[3];
	p->lvalue=in[0];
	p->rvalue=in[2];
	p->value=in[0]+in[2];
    if(in[0]==0&&in[2]==0)
	{
		p->lchild=build();
	    p->rchild=build();
	}
	else 
	{
		p->lchild=NULL;
	    p->rchild=NULL;
	}
	return p;
}
int set_value(node* p)
{
	if(!p->value)
		p->value=set_value(p->lchild)+set_value(p->rchild);
    else
		return p->value;
}
void add(node* p)
{
   if(p->lchild)
   {
	   p->lvalue=p->lchild->value;
       add(p->lchild);
   }
   if(p->rchild)
   {
	   p->rvalue=p->rchild->value;
	   add(p->rchild);
   }
}
void traverse(node* p)
{
	if(p->lchild)
		traverse(p->lchild);
	if(p->rchild)
		traverse(p->rchild);
	if(p->lvalue*p->llen!=p->rvalue*p->rlen)
		 ok=0;
}
int main()
{
   int n;
   while(cin>>n)
   {
	   while(n--)
	   {
		   ok=1;
		  node* root=build();
		  set_value(root);
		  add(root);
		  traverse(root);
		  cout<<(ok?"YES":"NO")<<endl;
		  if(n)
		cout<<endl;
	   }
   }
   return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 839 - Not so Mobile

Post by brianfry713 » Mon Apr 01, 2013 9:55 pm

Only read the number of test cases once.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 8 (800-899)”