Hdu1495 非常可乐

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 1k | 阅读时长 ≈ 5

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

1
2
3
7 4 3
4 1 3
0 0 0

Sample Output

1
2
NO
3

Analysis

此题可以数论，可以BFS，然而菜鸡我根本不会数论，所以在此记录BFS做法。因为容器没有刻度，所以每次倒只能将目标倒满或者将自己倒空，每次进行倒的操作，共有6种倒法，S->N，S->M，N->S，N->M，M->S，M->N，放进队列进行BFS即可，只需要记录倒的次数，并在最早达成条件时返回这个次数，即最少次数。

Code

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <queue>
using namespace std;
int s, n, m, s2;
struct node
{
	int s, n, m, t;
};
int bfs()
{
	if (s % 2 == 1)
		return -1;
	queue<node> q;
	s2 = s / 2;
	bool vis[100][100][100] = { false };
	node f;
	f.s = s;
	f.n = 0;
	f.m = 0;
	f.t = 0;
	q.push(f);
	vis[f.s][f.n][f.m] = true;
	while (!q.empty())
	{
		f = q.front();
		q.pop();
		if ((f.s == f.n&&f.s == s2) || (f.s == f.m&&f.s == s2) || (f.m == f.n&&f.m == s2))
			return f.t;
		node v;
		//s-->n
		if (f.s&&n - f.n > 0)
		{
			if (f.s > n - f.n)
			{
				v.s = f.s - (n - f.n);
				v.n = n;
				v.m = f.m;
			}
			else
			{
				v.s = 0;
				v.n = f.n + f.s;
				v.m = f.m;
			}
			if (vis[v.s][v.n][v.m] == false)
			{
				vis[v.s][v.n][v.m] = true;
				v.t = f.t + 1;
				q.push(v);
			}
		}
		//s-->m
		if (f.s&&m - f.m > 0)
		{
			if (f.s > m - f.m)
			{
				v.s = f.s - (m - f.m);
				v.n = f.n;
				v.m = m;
			}
			else
			{
				v.s = 0;
				v.n = f.n;
				v.m = f.m + f.s;
			}
			if (vis[v.s][v.n][v.m] == false)
			{
				vis[v.s][v.n][v.m] = true;
				v.t = f.t + 1;
				q.push(v);
			}
		}
		//n-->s
		if (f.n&&s - f.s > 0)
		{
			if (f.n > s - f.s)
			{
				v.s = s;
				v.n = f.n - (s - f.s);
				v.m = f.m;
			}
			else
			{
				v.s = f.s + f.n;
				v.n = 0;
				v.m = f.m;
			}
			if (vis[v.s][v.n][v.m] == false)
			{
				vis[v.s][v.n][v.m] = true;
				v.t = f.t + 1;
				q.push(v);
			}
		}
		//n-->m
		if (f.n&&m - f.m > 0)
		{
			if (f.n > m - f.m)
			{
				v.s = f.s;
				v.n = f.n - (m - f.m);
				v.m = m;
			}
			else
			{
				v.s = f.s;
				v.n = 0;
				v.m = f.m + f.n;
			}
			if (vis[v.s][v.n][v.m] == false)
			{
				vis[v.s][v.n][v.m] = true;
				v.t = f.t + 1;
				q.push(v);
			}
		}
		//m-->s
		if (f.m&&s - f.s > 0)
		{
			if (f.m > s - f.s)
			{
				v.s = s;
				v.n = f.n;
				v.m = f.m - (s - f.s);
			}
			else
			{
				v.s = f.s + f.m;
				v.n = f.n;
				v.m = 0;
			}
			if (vis[v.s][v.n][v.m] == false)
			{
				vis[v.s][v.n][v.m] = true;
				v.t = f.t + 1;
				q.push(v);
			}
		}
		//m-->n
		if (f.m&&n - f.n > 0)
		{
			if (f.m > n - f.n)
			{
				v.s = f.s;
				v.n = n;
				v.m = f.m - (n - f.n);
			}
			else
			{
				v.s = f.s;
				v.n = f.n + f.m;
				v.m = 0;
			}
			if (vis[v.s][v.n][v.m] == false)
			{
				vis[v.s][v.n][v.m] = true;
				v.t = f.t + 1;
				q.push(v);
			}
		}
	}
	return -1;
}
int main()
{
	while (cin >> s >> n >> m)
	{
		if (s == 0 && n == 0 && m == 0)
			break;
		int ans = bfs();
		if (ans < 0)
			cout << "NO" << endl;
		else
			cout << ans << endl;
	}
	return 0;
}