http://acm.hdu.edu.cn/showproblem.php?pid=1495
Problem 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
7 4 3
4 1 3
0 0 0
Sample Output
NO
3
因为每次倒的方法只有6种,所以可以利用广搜枚举所有方法
#include <iostream>
#include <queue>
using namespace std;
struct cola{
int x, y, z, num; //x,y,z 表示当前杯子中的含量
}front, temp;
int s, n, m; //s,n,m 分别是装[x,y,z]的杯子的容积
bool hash[105][105][105]; //hash记忆到达状态,第二次出现,死循环,说明已经不可能
void bfs () //6种情况,分别独立对待,可倒成功者都入队列
{
queue<cola> q;
q.push (front);
while (!q.empty())
{
front = q.front(), q.pop();
if ((front.x == 0 && front.y == front.z) ||
(front.y == 0 && front.x == front.z) ||
(front.z == 0 && front.x == front.y))
{
printf ("%d\n", front.num); //符合平分情况,跳出
return ;
}
temp = front; //每步独立进行,所以都需要初始化
temp.num = front.num + 1;
//x -> y ①, x倒给y 【给出此步分析,下面同理】
if (temp.x > 0 && temp.y < n)
{
int left = n - temp.y; //求出容积是n的杯子还剩多少体积没装
if (temp.x >= left) //装x的杯子中的含量x>left, 即不可以全部倒入y那个杯子, 倒完后x那个杯子倒去left, y就满了--达到最大容积n
temp.x -= left, temp.y = n;
else temp.y += temp.x, temp.x = 0; //反之可以全部倒入
//cout << "-" << temp.x << ' ' << temp.y << ' ' << temp.z << endl;
if (!hash[temp.x][temp.y][temp.z])
{ //记录出现的3个杯子当前状态,如果再次出现,肯定是死循环,所以必无答案
hash[temp.x][temp.y][temp.z] = true;
q.push (temp);
}
}
temp = front; //初始化,下面同理
temp.num = front.num + 1;
//x -> z ②
if (temp.x > 0 && temp.z < m)
{
int left = m - temp.z;
if (temp.x >= left)
temp.x -= left, temp.z = m;
else temp.z += temp.x, temp.x = 0;
//cout << "--" << temp.x << ' ' << temp.y << ' ' << temp.z << endl;
if (!hash[temp.x][temp.y][temp.z])
{
hash[temp.x][temp.y][temp.z] = true;
q.push (temp);
}
}
temp = front;
temp.num = front.num + 1;
//y -> x ③
if (temp.y > 0 && temp.x < s)
{
int left = s - temp.x;
if (temp.y >= left)
temp.y -= left, temp.x = s;
else temp.x += temp.y, temp.y = 0;
if (!hash[temp.x][temp.y][temp.z])
{
hash[temp.x][temp.y][temp.z] = true;
q.push (temp);
}
}
temp = front;
temp.num = front.num + 1;
//y -> z ④
if (temp.y > 0 && temp.z < m)
{
int left = m - temp.z;
if (temp.y >= left)
temp.y -= left, temp.z = m;
else temp.z += temp.y, temp.y = 0;
if (!hash[temp.x][temp.y][temp.z])
{
hash[temp.x][temp.y][temp.z] = true;
q.push (temp);
}
}
temp = front;
temp.num = front.num + 1;
//z -> x ⑤
if (temp.z > 0 && temp.x < s)
{
int left = s - temp.x;
if (temp.z >= left)
temp.z -= left, temp.x = s;
else temp.x += temp.z, temp.z = 0;
if (!hash[temp.x][temp.y][temp.z])
{
hash[temp.x][temp.y][temp.z] = true;
q.push (temp);
}
}
temp = front;
temp.num = front.num + 1;
//z -> y ⑥
if (temp.z > 0 && temp.y < n)
{
int left = n - temp.y;
if (temp.z >= left)
temp.z -= left, temp.y = n;
else temp.y += temp.z, temp.z = 0;
if (!hash[temp.x][temp.y][temp.z])
{
hash[temp.x][temp.y][temp.z] = true;
q.push (temp);
}
}
}
puts ("NO"); //还未跳出,说明不可平分
return ;
}
int main()
{
while (scanf ("%d%d%d", &s, &n, &m) != EOF)
{
if (!s && !n && !m)
break;
if (s % 2)
{
puts ("NO");
continue;
}
memset (hash, false, sizeof(hash));
hash[s][0][0] = true;
front.x = s, front.y = 0, front.z = 0, front.num = 0;
bfs ();
}
return 0;
}
分享到:
相关推荐
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
杭电hdu acm资料所用杭电的acm题
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
hdu_2102_passed_sorce
HDU_ACM培训课件是面向参与ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)的学员准备的一套完整的教程资源。这个压缩包包含了丰富的学习资料,旨在帮助参赛者提升编程技能...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
HDU_ACM_1002_大数相加C源代码,利用字符串处理
杭电期中期末复习资料档案库_HDU_QuickLearner
【标题】"HDU_软工_计组实验1~8"所涵盖的知识点主要集中在计算机组织(简称计组)的实践操作层面,这通常包括对计算机硬件结构、指令系统、存储器体系、数据表示以及处理器工作原理等基础知识的深入理解和应用。...
这份名为"HDU.rar"的压缩包文件,包含了针对杭电(Hangzhou Dianzi University,简称HDU)ACM竞赛平台上的2000至2099号题目的一系列解题报告。这些报告以".chm"(Compiled Help Manual)格式存储,是专门为ACM(国际...
在本压缩包文件“模式识别_hdu_期末复习资料集合_试卷笔记.zip”中,我们可以期待找到与杭州电子科技大学(HDU)模式识别课程相关的期末复习资料,可能包括过去的试卷、笔记和其他学习材料。 模式识别的基本概念...
B_(HDU_1231)(最大子段和,分治).cpp
【标题】"sanguosha.rar_hdu_三国杀_标程" 提供的是一个关于 HDU(杭州电子科技大学在线判题系统)3378 题目的解题报告,该题目名为“三国杀”,并且包含了一份用 C++ 编写的程序代码“san guo sha.cpp”。...
【标题】"Rightmost Digit HDU" 这道题目来源于HDU(杭州电子科技大学)的在线判题系统,通常这类题目是编程竞赛或者算法训练的一部分。"Rightmost Digit"直译为“最右边的数字”,我们可以推测这是一个关于数字...
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?...
本资料"HDU Page 11 Answer"正是针对杭电OJ中第11页的题目,提供了一系列题解,旨在帮助初学者快速掌握基础算法,并提升编程能力。 一、ACM入门基础知识 ACM竞赛强调的是团队协作和快速解决问题的能力,其核心是...
这个压缩包“数字图像处理_hdu_期末复习资料_试卷等.zip”显然是为杭州电子科技大学(HDU)的学生准备的期末复习材料,包含了一些关于这门课程的试卷。下面,我们将详细探讨数字图像处理的一些核心知识点。 1. 图像...
动态规划(Dynamic ...这个压缩包是学习动态规划和C++编程的好资源,不仅提供了理论知识,还提供了实践代码,对于提升算法能力和参加编程竞赛都非常有帮助。深入学习和理解这些内容,有助于成为一名更优秀的程序员。