`

HDU_1495_非常可乐

阅读更多
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;
}
1
2
分享到:
评论

相关推荐

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    hdu_ACM.rar_ACM_hdu_hdu acm_hdu_ACM_杭电ACM

    杭电hdu acm资料所用杭电的acm题

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu_2102_passed

    hdu_2102_passed_sorce

    HDU_ACM培训课件(完整版)

    HDU_ACM培训课件是面向参与ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC)的学员准备的一套完整的教程资源。这个压缩包包含了丰富的学习资料,旨在帮助参赛者提升编程技能...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    HDU_ACM_1002_大数相加C源代码

    HDU_ACM_1002_大数相加C源代码,利用字符串处理

    杭电期中期末复习资料档案库_HDU_QuickLearner.zip

    杭电期中期末复习资料档案库_HDU_QuickLearner

    HDU_软工_计组实验1~8

    【标题】"HDU_软工_计组实验1~8"所涵盖的知识点主要集中在计算机组织(简称计组)的实践操作层面,这通常包括对计算机硬件结构、指令系统、存储器体系、数据表示以及处理器工作原理等基础知识的深入理解和应用。...

    HDU.rar_hdoj 2000 2999 chm_hdoj 2000-2099_hdu_hdu acm 20_杭电ACM

    这份名为"HDU.rar"的压缩包文件,包含了针对杭电(Hangzhou Dianzi University,简称HDU)ACM竞赛平台上的2000至2099号题目的一系列解题报告。这些报告以".chm"(Compiled Help Manual)格式存储,是专门为ACM(国际...

    模式识别_hdu_期末复习资料集合_试卷笔记.zip

    在本压缩包文件“模式识别_hdu_期末复习资料集合_试卷笔记.zip”中,我们可以期待找到与杭州电子科技大学(HDU)模式识别课程相关的期末复习资料,可能包括过去的试卷、笔记和其他学习材料。 模式识别的基本概念...

    B_(HDU_1231)(最大子段和,分治).cpp

    B_(HDU_1231)(最大子段和,分治).cpp

    sanguosha.rar_hdu_三国杀_标程

    【标题】"sanguosha.rar_hdu_三国杀_标程" 提供的是一个关于 HDU(杭州电子科技大学在线判题系统)3378 题目的解题报告,该题目名为“三国杀”,并且包含了一份用 C++ 编写的程序代码“san guo sha.cpp”。...

    Rightmost Digit_hdu_

    【标题】"Rightmost Digit HDU" 这道题目来源于HDU(杭州电子科技大学)的在线判题系统,通常这类题目是编程竞赛或者算法训练的一部分。"Rightmost Digit"直译为“最右边的数字”,我们可以推测这是一个关于数字...

    code_hdu.rar_ACM_The First_hdu_test case example

    For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x&gt;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.rar_hdu_hdu oj第十一页_page_搜题_杭电oj

    本资料"HDU Page 11 Answer"正是针对杭电OJ中第11页的题目,提供了一系列题解,旨在帮助初学者快速掌握基础算法,并提升编程能力。 一、ACM入门基础知识 ACM竞赛强调的是团队协作和快速解决问题的能力,其核心是...

    数字图像处理_hdu_期末复习资料_试卷等.zip

    这个压缩包“数字图像处理_hdu_期末复习资料_试卷等.zip”显然是为杭州电子科技大学(HDU)的学生准备的期末复习材料,包含了一些关于这门课程的试卷。下面,我们将详细探讨数字图像处理的一些核心知识点。 1. 图像...

    DP.rar_DP_hdu_动态规划_动态规划 C++

    动态规划(Dynamic ...这个压缩包是学习动态规划和C++编程的好资源,不仅提供了理论知识,还提供了实践代码,对于提升算法能力和参加编程竞赛都非常有帮助。深入学习和理解这些内容,有助于成为一名更优秀的程序员。

Global site tag (gtag.js) - Google Analytics