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

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

839 - Not so Mobile

Post by broderic » Tue Jul 30, 2002 12:30 am

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jul 30, 2002 12:50 am

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.
The problem, which made people like me use Pascal instead of C/C++, is already fixed.

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

Post by broderic » Tue Jul 30, 2002 1:01 am

hmm,
wouldn't one of the "if (!mobile()) return 0;" catch the case where
a subsequent mobile is not in equilibrium?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jul 30, 2002 1:11 am

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

Post by htl » Fri Aug 09, 2002 7:45 am

How about this code? It got WA. Is anything I didn't consider yet?
[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

Post by xenon » Fri Aug 09, 2002 8:50 am

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

Post by htl » Mon Aug 12, 2002 5:23 pm

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?

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

Read complete input...

Post by WhiteShadow » Tue Aug 13, 2002 12:46 am

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.....

Post by .. » Thu Jan 16, 2003 6:20 am

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....... :o
But it seems that "checking equilibrium of sub-mobile" is the key to accepted.........
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

839 Why WA Please help me!!

Post by Daredevil » Tue Apr 01, 2003 8:25 am

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

Post by ashutoshkorde » Fri May 16, 2003 12:42 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

Post by lowai » Thu Jun 12, 2003 4:42 am

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
readln(w1, d1, w2, d2);
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
readln(kase);
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

Post by Sanghack » Thu Aug 14, 2003 8:40 am

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.

Post by Sanghack » Thu Aug 14, 2003 8:54 am

Hi.
Thanks for reading my question.

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;
bool readMore=false;
cin >> lw >> ll >> rw >> rl;
root=newMobile(lw,ll,rw,rl);
if(lw==0)
readMore=true;
if(rw==0)
readMore=true;
if(readMore){
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)

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

839 - Why the WA?

Post by Sarmento » Tue Sep 30, 2003 6:06 pm

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

Post Reply

Return to “Volume 8 (800-899)”