571 - Jugs

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

Moderator: Board moderators

Post Reply
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar »

By simulating the problem, i derived a greedy(!?) algorithm. But i was thinking that it might be got Run time error in the UVa judges. and it was happened so. My code outputed correctly for little joey's given input:

Code: Select all

fill B
pour B A
empty A
pour B A
fill B
pour B A
success
// ---- Step: 6
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
// ---- Step: 6
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
// ---- Step: 6
fill A
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
// ---- Step: 14
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
// ---- Step: 6
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
success
// ---- Step: 10
fill B
success
// ---- Step: 1
Now my greedy solution was become greedy of some critical input
[ Common thing of every man is that, everyone thinks that he is uncommon ]
Top
IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA »

First,I use BFS search and pruning to solve the problem
When I submit my code.I got Runtime Error.
I don't know what is worng in my code.
Who can help me to look my code.
Thanks in advance!

Code: Select all

Accept...
Last edited by IRA on Tue Oct 09, 2007 2:59 am, edited 1 time in total.
Top
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Contact Jan

Post by Jan »

Check your ini() function.

Code: Select all

for(i=0;i<=1001;i++) // why <= ?
suppose you have declared

Code: Select all

int a[10];
That means you can access a[0] to a[9], a[10] is not a valid position. Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Top
IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA »

Jan,Thank you!
I got AC
Top
DanielMarques
New poster
Posts: 5
Joined: Thu Jan 24, 2008 7:13 pm
Location: Rio de Janeiro

Re: [571] Jugs --Help

Post by DanielMarques »

I'm getting Runtime Error with the following code:
My idea seems to be ok, i'm doing the bfs from (0, 0) to (0, N).

Code: Select all

Accepted!
Last edited by DanielMarques on Fri Apr 18, 2008 5:31 pm, edited 1 time in total.
Top
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Contact Jan

Re: 571 - Jugs

Post by Jan »

Try the case '465 706 146'. Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Top
DanielMarques
New poster
Posts: 5
Joined: Thu Jan 24, 2008 7:13 pm
Location: Rio de Janeiro

Re: 571 - Jugs

Post by DanielMarques »

Thanks, got AC! :D
Top
anitha
New poster
Posts: 1
Joined: Wed Dec 30, 2009 4:26 pm

Re: 571 - Jugs

Post by anitha »

I solved the problem with a BFS but i don't know why my prog get Runtime error. Does anyone see what is wrong? please help me. here is my code:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct{
int jarra1,jarra2,padre,litros1,litros2,op;
}cosa;
cosa cola[10000000];
typedef struct
{char p[9];
}cosa2;
cosa2 letras[7]={{},{"fill A"},{"fill B"},{"empty A"},{"empty B"},{"pour A B"},{"pour B A"}};
char cadena[20];
int cont,k,pos,fin=-1,ini,ban,a,b,n,marcas[1001][1001],res[1000000],cont2;
void meter(int agua1,int num1,int agua2,int num2)
{//llenar la jarra A
if (agua1<num1 && marcas[num1][agua2]==0)
{cola[++fin].jarra1=num1;
cola[fin].litros1=num1;
cola[fin].padre=ini;
cola[fin].jarra2=num2;
cola[fin].litros2=agua2;
cola[fin].op=1;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[num1][agua2]=1;
}
//llenar la jarra B
if (agua2<num2 && marcas[agua1][num2]==0)
{cola[++fin].jarra1=num1;
cola[fin].litros1=agua1;
cola[fin].padre=ini;
cola[fin].jarra2=num2;
cola[fin].litros2=num2;
cola[fin].op=2;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[agua1][num2]=1;
}
//vaciar la jarra A
if (agua1>=0 && marcas[0][agua2]==0)
{cola[++fin].jarra1=num1;
cola[fin].litros1=0;
cola[fin].padre=ini;
cola[fin].jarra2=num2;
cola[fin].litros2=agua2;
cola[fin].op=3;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[0][agua2]=1;
}
//vaciar la jarra B
if (agua2>=0 && marcas[agua1][0]==0)
{cola[++fin].jarra1=num1;
cola[fin].litros1=agua1;
cola[fin].padre=ini;
cola[fin].jarra2=num2;
cola[fin].litros2=0;
cola[fin].op=4;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[agua1][0]=1;
}
//pasar de A a B
if (agua1>=0 && agua2<num2)
{if ((agua1+agua2)>num2)
{cola[++fin].litros1=agua1-(num2-agua2);
cola[fin].litros2=num2;
}
else
{cola[++fin].litros1=0;
cola[fin].litros2=agua1+agua2;
}
if (marcas[cola[fin].litros1][cola[fin].litros2]==0)
{cola[fin].jarra1=num1;
cola[fin].jarra2=num2;
cola[fin].padre=ini;
cola[fin].op=5;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[cola[fin].litros1][cola[fin].litros2]=1;
}
else
fin--;
}
//pasar de B a A
if (agua2>=0 && agua1<num1)
{if ((agua1+agua2)>num1)
{cola[++fin].litros2=agua2-(num1-agua1);
cola[fin].litros1=num1;
}
else
{cola[++fin].litros2=0;
cola[fin].litros1=agua1+agua2;
}
if (marcas[cola[fin].litros1][cola[fin].litros2]==0)
{cola[fin].jarra1=num1;
cola[fin].jarra2=num2;
cola[fin].padre=ini;
cola[fin].op=6;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[cola[fin].litros1][cola[fin].litros2]=1;
}
else
fin--;
}
return;
}
main(){
while (strlen(gets(cadena))>1)
{sscanf(cadena,"%d %d %d",&a,&b,&n);
cola[++fin].padre=-1;
cola[fin].jarra1=a;
cola[fin].jarra2=b;
marcas[0][0]=1;
while (ban==0)
{meter(cola[ini].litros1,cola[ini].jarra1,cola[ini].litros2,cola[ini].jarra2);
ini++;
}
pos=fin;
while(cola[pos].padre!=-1)
{res[k++]=cola[pos].op;
pos=cola[pos].padre;
}
for (cont=k-1;cont>=0;cont--)
{printf("%s\n",letras[res[cont]].p);
}
printf("success\n");
fin=-1;
ban=0;
ini=0;
k=0;
for (cont=0;cont<=a;cont++)
for (cont2=0;cont2<=b;cont2++)
marcas[cont][cont2]=0;
}
exit(0);
}
Top
Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:
Contact Shafaet_du

Re: 571 - Jugs

Post by Shafaet_du »

To solve the problem model the it as a graph then Run a breadth first search :wink:
Top
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

571 - Jugs

Post by outsbook »

BFS Problem

Pouring rule:
Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.

1. At first push to queue jugA=0, jugB=0 and command=""
2. Pop from queue
3. If jugB==N then print command and break
4. Find 6 adjacency of pop value of jugA and jugB
a. If jugA<Ca then change jugA=Ca and command="fill A" and push to queue
b. If jugB<Cb then change jugB=Cb and command="fill B" and push to queue
c. If jugA>0 then change jugA=0 and command="empty A" and push to queue
d. if jugB>0 then change jugB=0 and command="empty B" and push to queue
e. if jugA>0 and jugB<Cb then change the value of jugA and jugB using the pouring rule and command="pour A B" and push to queue
f. if jugA<Ca and jugB>0 then change the value of jugA and jugB using the pouring rule and command="pour B A" and push to queue
goto step 2

try this
Input:

Code: Select all

11 13 9
27 59 17
19 37 1
67 91 19
1 1 1
465 706 146
Output:

Code: Select all

fill A
pour A B
fill A
pour A B
empty B
pour A B
success
fill A
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
success
fill B
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
empty B
pour A B
success
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed
Top
Post Reply

Return to “Volume 5 (500-599)”