## 571 - Jugs

Moderator: Board moderators

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 Bpour B Aempty Apour B Afill Bpour B Asuccess// ---- Step: 6fill Apour A Bfill Apour A Bempty Bpour A Bsuccess// ---- Step: 6fill Apour A Bfill Apour A Bempty Bpour A Bsuccess// ---- Step: 6fill Apour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bsuccess// ---- Step: 14fill Apour A Bfill Apour A Bempty Bpour A Bsuccess// ---- Step: 6fill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bsuccess// ---- Step: 10fill Bsuccess// ---- 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 ]

Tariq Shahriar
New poster

Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

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.

Code: Select all
`Accept...`
Last edited by IRA on Tue Oct 09, 2007 2:59 am, edited 1 time in total.
IRA
Learning poster

Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

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
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Jan,Thank you!
I got AC
IRA
Learning poster

Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

### Re: [571] Jugs --Help

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.
DanielMarques
New poster

Posts: 5
Joined: Thu Jan 24, 2008 7:13 pm
Location: Rio de Janeiro

### Re: 571 - Jugs

Try the case '465 706 146'. Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### Re: 571 - Jugs

Thanks, got AC!
DanielMarques
New poster

Posts: 5
Joined: Thu Jan 24, 2008 7:13 pm
Location: Rio de Janeiro

### Re: 571 - Jugs

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{
}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"}};
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].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].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].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].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].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].op=6;
if (cola[fin].litros2==n)
{ban=1;
return;
}
marcas[cola[fin].litros1][cola[fin].litros2]=1;
}
else
fin--;
}
return;
}
main(){
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;
{res[k++]=cola[pos].op;
}
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);
}
anitha
New poster

Posts: 1
Joined: Wed Dec 30, 2009 4:26 pm

### Re: 571 - Jugs

To solve the problem model the it as a graph then Run a breadth first search
Shafaet_du
Experienced poster

Posts: 147
Joined: Mon Jun 07, 2010 11:43 am

### 571 - Jugs

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 927 59 1719 37 167 91 191 1 1465 706 146`

Output:
Code: Select all
`fill Apour A Bfill Apour A Bempty Bpour A Bsuccessfill Apour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bsuccessfill Apour A Bfill Apour A Bempty Bpour A Bsuccessfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bsuccessfill Bsuccessfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bfill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bempty Bpour A Bsuccess`
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

outsbook
New poster

Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Previous