http://acm.hdu.edu.cn/showproblem.php?pid=1495
非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14084 Accepted Submission(s): 5612
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S (S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S==N+M,101>S>0,N>0,M>0) 。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数,否则输出"NO"。
Sample Input
7 4 3
4 1 3
0 0 0
Sample Output
NO
3
Author
seeyou
Source
Recommend
LL
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<map> using namespace std; const int maxn=206; const int INF=0x3f3f3f3f; int a, b, c, k; int vis[110][110][110]; struct node { int s, n, m, step; }; int bfs() { memset(vis, 0, sizeof(vis)); queue<node>Q; node now, next; now.s=c; now.n=0; now.m=0; now.step=0; Q.push(now); vis[now.s][now.n][now.m]=1; while(!Q.empty()) { now=Q.front(); Q.pop(); if((now.s==k && now.n==k) || (now.s==k && now.m==k) || (now.n==k && now.m==k))return now.step; for(int i=0; i<6; i++) { if(i==0)///s->n { if(now.s==0) continue; if(now.s>=(a-now.n)) { next.s=now.s-(a-now.n); next.n=a; } else { next.s=0; next.n=now.n+now.s; } next.m=now.m; } else if(i==1)///n->m { if(now.n==0) continue; if(now.n>=(b-now.m)) { next.n=now.n-(b-now.m); next.m=b; } else { next.n=0; next.m=now.m+now.n; } next.s=now.s; } else if(i==2)///s->m { if(now.s==0) continue; if(now.s>=(b-now.m)) { next.s=now.s-(b-now.m); next.m=b; } else { next.s=0; next.m=now.m+now.s; } next.n=now.n; } if(i==3)///n->s { if(now.n==0) continue; if(now.n>=(c-now.s)) { next.n=now.n-(c-now.s); next.s=c; } else { next.n=0; next.s=now.n+now.s; } next.m=now.m; } if(i==4)///m->n { if(now.m==0) continue; if(now.m>=(a-now.n)) { next.m=now.m-(a-now.n); next.n=a; } else { next.m=0; next.n=now.n+now.m; } next.s=now.s; } if(i==5)///m->s { if(now.m==0) continue; if(now.m>=(c-now.s)) { next.m=now.m-(c-now.s); next.s=c; } else { next.m=0; next.s=now.m+now.s; } next.n=now.n; } if(!vis[next.s][next.n][next.m]&&next.s>=0&&next.s<=c&&next.n>=0&&next.n<=a&&next.m>=0&&next.m<=b) { vis[next.s][next.n][next.m]=1; next.step=now.step+1; Q.push(next); } } } return 0; } int main() { while(scanf("%d %d %d", &c, &a, &b), a+b+c) { if(c%2) { printf("NO "); continue; } /* if(a>b) swap(a, b);*/ k=c/2; int ans=bfs(); if(ans) printf("%d ", ans); else printf("NO "); } return 0; }