Problem Description

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是NN 毫升和MM 毫升 可乐的体积为S（S<101）S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S=N+M，101＞S＞0，N＞0，M＞0S=N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

Input

三个整数 : SS 可乐的体积 , NN 和 MM是两个杯子的容量，以"0 0 0"结束。

Output

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

Sample Input

7 4 3
4 1 3
0 0 0

Sample Output

NO
3

Idea1

每一次操作有选取两个瓶子，并从中选取一个瓶子倒入另一个瓶子，因此每一次操作有C32×C21=6C_3^2 \times C_2^1=6种选择。
于是可以利用BFSBFS枚举每一次状态的六种选择。

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)//a倒到b 
			{
				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)//b倒到a 
			{
				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)//a倒到c
			{
				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)//c倒到a
			{
				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)//b倒到c 
			{
				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)//c倒到b 
			{
				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,ba,b，问题转化成通过两个小瓶子的若干次倒进或倒出操作得到(a+b)/2体积的可乐，设两个小瓶子被倒进或倒出xx次和yy次；这里的xx和yy是累加后的操作即x=第一个瓶子倒出的次数−倒进的次数，y=第二个瓶子倒出的次数−倒进的次数x=第一个瓶子倒出的次数-倒进的次数，y=第二个瓶子倒出的次数-倒进的次数。
那么问题转化成：

所以∣x∣+∣y∣|x|+|y|的最小值为c+d2=s2gcd(a,b)\frac {c+d}{2}=\frac{s}{2gcd(a,b)}，通过xx和yy的通解形式显然可以看出xx和yy一正一负，不妨设x<0x<0，那么就是往第一个小瓶子倒进xx次，第二个小瓶子倒出yy次，但是由于瓶子容积有限，所以倒进倒出操作都是通过大瓶子来解决的，一次倒进操作后为了继续使用小瓶子还要将小瓶子中可乐倒回大瓶子中，倒出操作同理，所以总操作次数是c+d2×2=c+d=sgcd(a,b)\frac{c+d}{2}\times 2=c+d=\frac {s}{gcd(a,b)}，但是注意最后剩下的s2\frac{s}{2}体积的可乐一定是放在两个小瓶子中较大的那个中，而不是再倒回到大瓶子中，所以操作数要减一，答案就是sgcd(a,b)−1\frac {s}{gcd(a,b)}-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;
}