571 - Jugs

[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

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

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

[IRA]

Jan,Thank you!
I got AC

[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!


[Jan]

Try the case '465 706 146'. Hope it helps.

[DanielMarques]

Thanks, got AC!

[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);
}

[Shafaet_du]

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