I got TLE for this problem by using brute force ,is there anyway to imporve it?
More over,the problem said that when either of the jugs containing exactly N gallons of water ,you can show the result .But in the example output ,the result is shown only when jug B has N gallons of water .Pls explain for me because there's a shorter way if we can also fill N-gallons in jugA .
Thanks
a brute-force solution will obviously get TLE. Backtracking and minor pruning should be enough. -- make sure you don't get the same combination of water in the jugs twice.
There is a yellow tick associated with it -- meaning it has got multiple outputs. So it does not matter which jug ends up having the liquid. It does not always have to be B.
I try to solve it with BFS (something like state machine in which I walk only to unvisited states).
Are there some special, tricky inputs ?
I can send my code to intrested persons
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
I don't understand you, Aleksandrs ... Coudl you explain it ?
I don't get TLE but WA ... So I think that I find solution if it exist. When I use BFS it's impossible (I think) that I'll find solution which is longer that shortest one ... So why WA ?
I consider six operations on jugs: fill/empty A, fill/empty B, pour A->B , pour B->A.
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
There is a contadiction in the problem description
A solution is a sequence of steps that leaves exactly N gallons in jug B.
and
Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water.
Looking at the output for the second example, it's clear that only the first condition holds (B should contain N) because A contains N one step earlier.
My program only stops when B contains N and gets accepted, so that is the proper condition.
As is often the case with Miguel A. Revilla's problems, the descriptions are in crooked English, ambiguous or contradictory as in this case, and sometimes the judges i/o doesn't match the description. This results in a lot of wasted submissions. On the other side, this man has done a lot to set up and maintain this wonderful site, and has written countles, mostly very interesting and original problems. He is invaluable to our programmers community, but he should have his texts looked over by someone with a better command of the English language
I have answers with the same length as you , little joey ... (If I dont count 'success' as step) ... and still WA ...
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Finally I solved it with nice time (0.016 sec). I made stupid (!!!!!!) mistake in output So BFS works fine
Best regadrs
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Anyway, I'll explain what I was trying to hint at.
Since A and B are relatively prime, the sequence A, A+A, A+A+A, ... yields every modulo B (0...B-1). As you can see, it's pretty trivial from now on.
By the way, my code stops when the amount needed is in any of the jugs. So no problem here, I guess.
I tried to use BFS to solve this problem, but got SIGSEV. Does anyone see what is wrong? I've tried littering the code with asserts, but it was no help. :( The idea of my code is to keep track of which states have been visited in the states array. states[j][2] is 0 iff we haven't visited the state yet where jug A has i gallons and jug B has j gallons. otherwise, states[j][2] represents what operation we performed to get to state i,j from the state states[j][0],states[j][1]. once BFS finds a state where jug B has the target amount of gallons, we run backwards through the states array 'til we get back to 0,0, then we print forwards again.
EDIT: Note to people who looked at this code before this edit. I have changed states from a char array to an int one since states[j][0] and states[j][1] can be as large as 1000. i still get sigsev though, save me please! :)
int done,states[1001][1001][3];
enum { pour_a=1,pour_b,fill_a,fill_b,empty_a,empty_b };
queue<pair<int,int> > q;
int a,b,n;
void print_out(int x, int y) {
int i,xx=x,yy=y,temp;
vector<int> ops;
while (xx || yy) {
ops.push_back(states[xx][yy][2]);
temp = xx;
xx = states[xx][yy][0]; yy = states[temp][yy][1];
}
for (i=ops.size()-1;i>=0;i--) {
if (ops==fill_a) printf("fill A\n");
else if (ops==fill_b) printf("fill B\n");
else if (ops==empty_a) printf("empty A\n");
else if (ops==empty_b) printf("empty B\n");
else if (ops[i]==pour_a) printf("pour A B\n");
else printf("pour B A\n");
}
}
void go(int x, int y) {
if (y==n) {
done = 1;
return;
} else {
int xx,yy;
yy = y + x;
xx = x - (b-y);
if (xx<0) xx = 0; if (yy>b) yy = b;
if (!states[xx][yy][2]) {
states[xx][yy][2] = pour_a;
states[xx][yy][0] = x; states[xx][yy][1] = y;
q.push(make_pair(xx,yy));
}
xx = x + y;
yy = y - (a-x);
if (yy<0) yy = 0; if (xx>a) xx = a;
if (!states[xx][yy][2]) {
states[xx][yy][2] = pour_b;
states[xx][yy][0] = x; states[xx][yy][1] = y;
q.push(make_pair(xx,yy));
}
}
}
int main() {
int i,j;
char buff[20];
while (strlen(gets(buff))>1) {
q = queue<pair<int,int> >();
sscanf(buff,"%d %d %d",&a,&b,&n);
done = 0;
q.push(make_pair(0,0));
for (i=0;i<=a;i++) for (j=0;j<=b;j++) states[i][j][2] = 0;
states[0][0][2] = 1;
while (!q.empty()) {
pair<int,int> p = q.front();
q.pop();
go(p.first,p.second);
if (done) {
print_out(p.first,p.second);
break;
}
}
printf("success\n");
}
exit(0);
}
If you output is one or two steps longer than the judge sample, so it is not the minimum steps. Hint: Use bfs, its solution will ensured to be minimum length.