警告
本文最后更新于 2018-07-24，文中内容可能已过时。
非常可乐
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是 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
模拟一下倒水的过程，一共有三种倒法，a 向 bc，b 向 ac，c 向 ab。（相当于一共六个方向）搜索并记录搜索过的过程就好了。
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
| #include<bits/stdc++.h>
using namespace std;
int a,b,c;
int used[111][111][111];
struct node
{
int x,y,z;
int step;
}m,n;
int bfs()
{
queue<node>q;
m.x = a;
m.y = 0;
m.z = 0;
m.step = 0;
used[a][0][0] = 1;
q.push(m);
while (!q.empty())
{
int trans; //倒水量
m = q.front();
q.pop();
//成功分好的三种情况
if ((m.x == 0 && m.y == m.z) || (m.y == 0 && m.x == m.z) || (m.z == 0 && m.x == m.y))
return m.step;
//下面开始 6 个搜索（由一个杯子向另外两个倒水）
if (m.x)
{
//第一
trans = min(m.x , b - m.y);//自己模拟一下倒水过程就知道了
n.x = m.x - trans;
n.y = m.y + trans;
n.z = m.z;
n.step = m.step + 1;
if (!used[n.x][n.y][n.z])
{
q.push(n);
used[n.x][n.y][n.z] = 1;
}
//第二
trans = min(m.x , c - m.z);
n.x = m.x - trans;
n.y = m.y;
n.z = m.z + trans;
n.step = m.step + 1;
if (!used[n.x][n.y][n.z])
{
q.push(n);
used[n.x][n.y][n.z] = 1;
}
}
if (m.y)
{
//第三
trans = min(m.y , a - m.x);
n.x = m.x + trans;
n.y = m.y - trans;
n.z = m.z;
n.step = m.step + 1;
if (!used[n.x][n.y][n.z])
{
used[n.x][n.y][n.z] = 1;
q.push(n);
}
//第四
trans = min(m.y , c - m.z);
n.x = m.x;
n.y = m.y - trans;
n.z = m.z + trans;
n.step = m.step + 1;
if (!used[n.x][n.y][n.z])
{
used[n.x][n.y][n.z] = 1;
q.push(n);
}
}
if (m.z)
{
//第五
trans = min(m.z , a - m.x);
n.x = m.x + trans;
n.y = m.y;
n.z = m.z - trans;
n.step = m.step + 1;
if (!used[n.x][n.y][n.z])
{
used[n.x][n.y][n.z] = 1;
q.push(n);
}
//第六
trans = min(m.z , b - m.y);
n.x = m.x;
n.y = m.y + trans;
n.z = m.z - trans;
n.step = m.step + 1;
if (!used[n.x][n.y][n.z])
{
q.push(n);
used[n.x][n.y][n.z] = 1;
}
}
}
return 0;
}
int main()
{
while (~scanf ("%d %d %d",&a,&b,&c) && (a || b || c))
{
if (a&1) //先简单的剪枝一下，奇数肯定不能平分
printf ("NO\n");
else
{
memset (used,0,sizeof (used));
int ans = bfs();
if (ans)
printf ("%d\n",ans);
else
printf ("NO\n");
}
}
return 0;
}
|
然后杭电上讨论板子上提供一种数论题解，但是数据存在一点问题，只不过有些数据好像不对；比如： 10 6 5 的结果应该是 1 而不是 9， 也提示我们多维思考同一个问题！
数论推导
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<bits/stdc++.h>
using namespace std;
int main(){
int s,n,m;
while(cin>>s>>n>>m,s+n+m){
s/=__gcd(n,m);
if(s&1)//奇数
cout<<"NO\n";
else cout<<s-1<<endl;
}
return 0;
}
|
Jian YE
支付宝
微信