## 839 - Not so Mobile

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

### 839 - Not so Mobile

Hello...besides the sample input being wrong, is there something else
tricky with this question? Somebody in the ranklist said to use pascal
if it doesn't work, but people did solve it using c++.

I'll post my code since it's so short (in case I did something really
dumb), but I'll only keep it up till somebody helps me.
Last edited by broderic on Tue Jul 30, 2002 2:52 am, edited 1 time in total.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
With your code you don't consider the case, that the mobile is in equilibrium in the highest level, but not in equilibrium in a lower level. Use a flag to indicate if anywhere was a level where the mobile wasn't in equilibrium.

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
hmm,
wouldn't one of the "if (!mobile()) return 0;" catch the case where
a subsequent mobile is not in equilibrium?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
What about rd = ld = 0?
Last edited by Adrian Kuegel on Tue Jul 30, 2002 2:03 am, edited 1 time in total.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
[c]
#include<stdio.h>
#define YES 1
#define NO 0
int error;
int mobile(int);
void main(void)
{
int count,x;
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
error=NO;
mobile(0);
if(error)
printf("NO\n");
else
printf("YES\n");
}
}
int mobile(int depth)
{
int wl,dl,wr,dr;
scanf("%d %d %d %d",&wl,&dl,&wr,&dr);
if(wl==0)
wl=mobile(depth+1);
if(error)
return;
if(wr==0)
wr=mobile(depth+1);
if(error)
return;
if(wl*dl==wr*dr)
return wl+wr;
else
{
error=YES;
return;
}
}
[/c]

BTW, I think the data might be wrong:

0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 2 3 -> I think it's 1 6 3 2

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
Read the complete input, even if you know there is an error at an early stage. Your function mobile() returns if it encounters an error in the left branch and leaves the right branch unread.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
I still don't understand why I have to read the complete input.
If I got error in reading left branch, do I have to read the
right branch? Is it necessary?

New poster
Posts: 10
Joined: Tue Jun 18, 2002 12:08 pm
Location: Portugal
Contact:

I still don't understand why I have to read the complete input.
If I got error in reading left branch, do I have to read the
right branch? Is it necessary?
Well, don't forget that this problem has multiple input, ie, more than one mobile may be present in the input. Therefore, it is necessary to read a single mobile completely in order to correctly read the start of the next mobile....
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 839 - I don't understand.....

Can anyone tell me, why is the following case should give "No"?

1

0 2 0 2
1 3 1 1
1 1 1 3

From the problem specification, I can't find a clear statement stating that all the sub-mobiles are also required to be in equilibrium.......
But it seems that "checking equilibrium of sub-mobile" is the key to accepted.........
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Daredevil
New poster
Posts: 19
Joined: Tue Apr 01, 2003 7:47 am
Location: Earth

Equilibrium in this problem is defined as a condition where the product of the left distance with the TOTAL left mobile weight (although there may be a sub mobile in the left mobile not equilibrium) equals to that of the right.
Example:

Input =
0 12 96 1
1 2 3 2
2 4 2 4

Left - mobile : 0 left distance : 12

sub 1 : 1 2 3 2 (not equilibrium)

sub 2 : 2 4 2 4 (equilibrium)

Total weight of left - mobile is 8

Right - mobile : 96 right distance : 1

so the math : left weight * left distance = 12 * 8 = 96
right weight * right distance = 96 * 1 = 96

So this system, according to me is equilibrium. Is this correct?
If false, what's the right definition of 'equilibrium' ?

ashutoshkorde
New poster
Posts: 6
Joined: Mon May 05, 2003 1:48 pm
you need to have equilibrium in each and every sub moblie branch..
its not mentioned in the problem but that's the case...

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
i got wa with the code following...
can anyone help me to check it/
[pascal]
var
kase : integer;
equ : boolean;

function balance : double;
var w1, d1, w2, d2 : longint;
l, r : double;
begin
if not equ then exit;

if w1 > 0 then l := w1 else l := balance;
if w2 > 0 then r := w2 else r := balance;
if abs(l * d1 - r * d2) > 1e-7 then begin equ := false; exit; end;
balance := r * (d1 + d2) / d1;
end;

begin
while kase > 0 do
begin
equ := true;
balance;
if equ then
writeln('YES')
else
writeln('NO');
dec(kase);
if kase > 0 then writeln;
end;
end.
[/pascal]

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea
You wrote that
0 12 96 1
1 2 3 2
2 4 2 4

But how this input could be...
0 12 96 1 shows that this root mobile needs only one left sub - mobile.

and
1 2 3 2 sub-mobile's total weight is 2 + 2 = 4 , not 1*2 + 3*2...

the right definition of 'equilibrium' ?
-> All sub-mobile's left-weight and right weight is equal.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

### 839 WA. still confused.

Hi.

I solved ( not yet ) this problem with

stack ( to make mobile - as tree data type ),
and
dfs ( to traverse all the sub-mobiles ).

I tested some kinds of input with several test cases.
I thought my code would work well... But I got WA.

(My code is so complex)

typedefinition...
pushStack.. (also links the mobile and pop from stack list..)
traverse ( easy to see... DFS method.)
and...
main...

[cpp]#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

typedef struct mobile MOB;
struct mobile{
int leftWeight,leftLength,rightWeight,rightLength;
int totalWeight;
MOB* l_Mob;
MOB* r_Mob;
MOB* stack;
};
MOB* stackLast;
MOB* root;

MOB* newMobile(int lw,int ll,int rw,int rl){
MOB* result=(MOB*)malloc(sizeof(MOB));
result->leftWeight=lw;
result->l_Mob=NULL;
result->leftLength=ll;

result->rightWeight=rw;
result->r_Mob=NULL;
result->rightLength=rl;

result->totalWeight=0;
return result;
}

void pushStack(MOB* pushed){
if(stackLast==NULL){
//stackStart=pushed;
stackLast=pushed;
pushed->stack=NULL;
}
else{
if(stackLast->leftWeight==0 && stackLast->l_Mob==NULL){
stackLast->l_Mob=pushed;
// all mobile hanged.
if(stackLast->rightWeight!=0 || stackLast->r_Mob!=NULL){
// new mobile should be pushed
if(pushed->leftWeight==0 || pushed->rightWeight==0){
pushed->stack=stackLast->stack;
stackLast=pushed;
}
// don't have to
else{
stackLast=stackLast->stack;
}
}
// wait right sub mobile.
else{
// & push current
if(pushed->leftWeight==0 || pushed->rightWeight==0){
pushed->stack=stackLast;
stackLast=pushed;
}
}
}
else if(stackLast->rightWeight==0 && stackLast->r_Mob==NULL){
stackLast->r_Mob=pushed;
// all mobile hanged.
// new mobile should be pushed
if(pushed->leftWeight==0 || pushed->rightWeight==0){
pushed->stack=stackLast->stack;
stackLast=pushed;
}
// don't have to
else{
stackLast=stackLast->stack;
}
}
}
}

bool traverse(MOB* at){
if(at->leftWeight!=0 && at->rightWeight!=0){
if(at->leftWeight*at->leftLength == at->rightWeight*at->rightLength){
at->totalWeight=at->leftWeight+at->rightWeight;
return true;
}
else
return false;
}
else{
bool balance;
int lw,rw;
if(at->leftWeight==0){
balance=traverse(at->l_Mob);
if(balance==false)
return false;
lw=at->l_Mob->totalWeight;
}
else
lw=at->leftWeight;
if(at->rightWeight==0){
balance=(balance && traverse(at->r_Mob));
if(balance==false)
return false;
rw=at->r_Mob->totalWeight;
}
else
rw=at->rightWeight;
if(lw*at->leftLength == rw*at->rightLength){
at->totalWeight=lw+rw;
return true;
}
else
return false;
}
}

void main(){
freopen("839.txt","r+",stdin);
int testCase;
int lw,ll,rw,rl;
cin >> testCase;
while(testCase--){
root=NULL;
stackLast=NULL;
cin >> lw >> ll >> rw >> rl;
root=newMobile(lw,ll,rw,rl);
if(lw==0)
if(rw==0)
pushStack(root);
}
while(stackLast){
cin >> lw >> ll >> rw >> rl;
MOB* subMobile=newMobile(lw,ll,rw,rl);
pushStack(subMobile);
}
if(traverse(root)){
printf("YES\n");
}
else{
printf("NO\n");
}
if(testCase){
printf("\n");
}
}
}[/cpp]

Sample Input
11

0 2 6 5
0 2 6 3
1 8 0 1
0 5 0 3
1 2 2 1
2 3 3 2

0 2 6 6
0 2 6 3
1 8 0 1
0 5 0 3
1 2 2 1
2 3 3 2

0 2 0 4
0 3 0 2
1 1 1 1
2 4 4 2
1 6 3 2

0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

1 6 3 1

2 4 4 2

0 4 8 1
1 1 1 3

1 1 1 1

2 100 100 2

2 100 2 100

0 3 0 3
0 2 0 2
1 1 1 1
1 1 1 1
0 2 0 2
1 1 1 1
1 1 1 1

Sample Output

YES

NO

NO

YES

NO

YES

NO

YES

YES

YES

YES

It seems like 'delegating my responsibility'. But I can't do it more without your help...

Any help appreciated-
(sorry to read my poor English)

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

### 839 - Why the WA?

Can anyone help me out? I dunno why I get WA. I tried out all the input I could find/create and the answer is accurate. Maybe I'm missing something.

Code: Select all

``````[c]
#include <stdio.h>

int balanced;

void mobile(int *weight){
int w1, d1, w2, d2;
scanf("%d %d %d %d",&w1,&d1,&w2,&d2);
if (balanced == 1){
if (w1 == 0)
mobile(&w1);
if (w2 == 0)
mobile(&w2);
if (w1*d1 != w2*d2)
balanced = 0;
*weight = w1 + w2;
}
}

int main(){
int n;
int weight;
scanf("%d",&n);
for(; n>0; n--){
weight = 0;
balanced = 1;
mobile(&weight);
if (balanced)
printf("\nYES\n");
else
printf("\nNO\n");
}
return 0;
}
[/c]``````
-----------------
Jo