Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为S(S<101)毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且 S=N+M,101>S>0,N>0,M>0) 。聪明的ACMER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出"NO"。
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数,否则输出"NO"。
7 4 3
4 1 3
0 0 0
Sample Output
NO
3
Idea1
每一次操作有选取两个瓶子,并从中选取一个瓶子倒入另一个瓶子,因此每一次操作有C32×C21=6种选择。
于是可以利用BFS枚举每一次状态的六种选择。
Code1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
| #include<queue> #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N=120; struct state { int a,b,c; int step; }; bool ok; int s,n,m; bool vis[N][N][N]; void init() { ok=0; memset(vis,0,sizeof(vis)); } void bfs() { vis[s][0][0]=1; state start; start.a=s; start.b=0; start.c=0; start.step=0; queue<state>q; q.push(start); int i; while(!q.empty()) { state nxt; state now=q.front(); for(i=1;i<=6;i++) { if(i==1) { if(now.a+now.b<=n) { nxt.a=0; nxt.b=now.a+now.b; nxt.c=now.c; } else { nxt.b=n; nxt.c=now.c; nxt.a=now.a+now.b-n; } } else if(i==2) { if(now.a+now.b<=s) { nxt.b=0; nxt.a=now.a+now.b; nxt.c=now.c; } else { nxt.a=s; nxt.b=now.a+now.b-s; nxt.c=now.c; } } else if(i==3) { if(now.a+now.c<=m) { nxt.a=0; nxt.c=now.a+now.c; nxt.b=now.b; } else { nxt.c=m; nxt.b=now.b; nxt.a=now.a+now.c-m; } } else if(i==4) { if(now.a+now.b<=s) { nxt.c=0; nxt.a=now.a+now.c; nxt.b=now.b; } else { nxt.b=now.b; nxt.a=s; nxt.c=now.a+now.c-s; } } else if(i==5) { if(now.b+now.c<=m) { nxt.b=0; nxt.a=now.a; nxt.c=now.b+now.c; } else { nxt.a=now.a; nxt.c=m; nxt.b=now.b+now.c-m; } } else if(i==6) { if(now.b+now.c<=n) { nxt.c=0; nxt.b=now.b+now.c; nxt.a=now.a; } else { nxt.b=n; nxt.a=now.a; nxt.c=now.b+now.c-n; } } if(vis[nxt.a][nxt.b][nxt.c]) continue; else { nxt.step=now.step+1; if((!nxt.a&&nxt.b==nxt.c)||(!nxt.b&&nxt.a==nxt.c)||(!nxt.c&&nxt.a==nxt.b)) { ok=1; cout<<nxt.step<<endl; return; } else { vis[nxt.a][nxt.b][nxt.c]=1; q.push(nxt); } } } q.pop(); } } void solve() { init(); if(s&1) ok=0; else bfs(); if(!ok) puts("NO"); } int main() { while(cin>>s>>n>>m) { if(!s&&!n&&!m) break; else solve(); } return 0; }
|
Idea2
设两个小瓶子容积分别为a,b,问题转化成通过两个小瓶子的若干次倒进或倒出操作得到(a+b)/2体积的可乐,设两个小瓶子被倒进或倒出x次和y次;这里的x和y是累加后的操作即x=第一个瓶子倒出的次数−倒进的次数,y=第二个瓶子倒出的次数−倒进的次数。
那么问题转化成:
所以∣x∣+∣y∣的最小值为2c+d=2gcd(a,b)s,通过x和y的通解形式显然可以看出x和y一正一负,不妨设x<0,那么就是往第一个小瓶子倒进x次,第二个小瓶子倒出y次,但是由于瓶子容积有限,所以倒进倒出操作都是通过大瓶子来解决的,一次倒进操作后为了继续使用小瓶子还要将小瓶子中可乐倒回大瓶子中,倒出操作同理,所以总操作次数是2c+d×2=c+d=gcd(a,b)s,但是注意最后剩下的2s体积的可乐一定是放在两个小瓶子中较大的那个中,而不是再倒回到大瓶子中,所以操作数要减一,答案就是gcd(a,b)s−1。
Code2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include<algorithm> #include<cstdio> #include<iostream> using namespace std; int s,n,m; void solve() { s/=__gcd(n,m); if(s&1) puts("NO"); else cout<<s-1<<endl; } int main() { while(cin>>s>>n>>m) { if(!s&&!n&&!m) break; else solve(); } return 0; }
|