非常可乐 (HDU - 1495)
题面
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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"结束。
输出
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
样例输入
17 4 3
24 1 3
30 0 0
样例输出
1NO
23
提示
无
思路
倒水问题，当S为奇数时无解。数论有简便解法
代码
1using namespace std;
2
3#define out(a) (cout<<__LINE__<<" : "#a" = "<<(a)<<endl)
4typedef long long ll;
5const int inf = 0x3f3f3f3f;
6const int N = 1e2+5;
7
8bool vis[N][N][N] = {{{0}}};
9int s, n, m, ans = 0;
10
11struct P {
12 int n, m, s;
13 int step;
14};
15
16bool bfs() {
17 memset(vis, 0, sizeof(vis));
18
19 P sp;
20 sp.s = s;
21 sp.n = 0;
22 sp.m = 0;
23 sp.step = 0;
24
25 queue<P> q;
26 q.push(sp);
27 vis[sp.s][sp.n][sp.m] = 1;
28
29 while(!q.empty()) {
30 P tp = q.front();
31 q.pop();
32
33 if((!tp.n&&tp.m==tp.s) || (!tp.m&&tp.n==tp.s) || (!tp.s&&tp.n==tp.m)) {
34 ans = tp.step;
35 return true;
36 }
37 P np = tp;
38 int t;
39
40 if(tp.n) {
41 t = tp.n+tp.m;
42 if(t>m) {
43 np.m = m;
44 } else {
45 np.m = t;
46 }
47 np.n = t-np.m;
48 np.s = tp.s;
49
50 if(!vis[np.s][np.n][np.m]) {
51 np.step = tp.step+1;
52 q.push(np);
53 vis[np.s][np.n][np.m] = 1;
54 }
55
56 t = tp.n+tp.s;
57 if(t>s) {
58 np.s = s;
59 } else {
60 np.s = t;
61 }
62 np.n = t-np.s;
63 np.m = tp.m;
64
65 if(!vis[np.s][np.n][np.m]) {
66 np.step = tp.step+1;
67 q.push(np);
68 vis[np.s][np.n][np.m] = 1;
69 }
70 }
71
72 if(tp.m) {
73 t = tp.m+tp.n;
74 if(t>n) {
75 np.n = n;
76 } else {
77 np.n = t;
78 }
79 np.m = t-np.n;
80 np.s = tp.s;
81
82 if(!vis[np.s][np.n][np.m]) {
83 np.step = tp.step+1;
84 q.push(np);
85 vis[np.s][np.n][np.m] = 1;
86 }
87
88 t = tp.m+tp.s;
89 if(t>s) {
90 np.s = s;
91 } else {
92 np.s = t;
93 }
94 np.m = t-np.s;
95 np.n = tp.n;
96
97 if(!vis[np.s][np.n][np.m]) {
98 np.step = tp.step+1;
99 q.push(np);
100 vis[np.s][np.n][np.m] = 1;
101 }
102 }
103
104 if(tp.s) {
105 t = tp.s+tp.n;
106 if(t>n) {
107 np.n = n;
108 } else {
109 np.n = t;
110 }
111 np.s = t-np.n;
112 np.m = tp.m;
113
114 if(!vis[np.s][np.n][np.m]) {
115 np.step = tp.step+1;
116 q.push(np);
117 vis[np.s][np.n][np.m] = 1;
118 }
119
120 t = tp.s+tp.m;
121 if(t>m) {
122 np.m = m;
123 } else {
124 np.m = t;
125 }
126 np.s = t-np.m;
127 np.n = tp.n;
128
129 if(!vis[np.s][np.n][np.m]) {
130 np.step = tp.step+1;
131 q.push(np);
132 vis[np.s][np.n][np.m] = 1;
133 }
134 }
135 }
136 return false;
137}
138
139int main(void) {
140 while(scanf("%d%d%d", &s, &n, &m)==3 && s && n && m) {
141 if(s%2==0 && bfs()) {
142 printf("%d\n", ans);
143 } else {
144 printf("NO\n");
145 }
146 }
147 return 0;
148}