一楼喂度娘

NO1
题目出处：zhejiang University Local contest 2001
题目大意：在电影“虎胆龙威3-纽约大劫案”中，布鲁斯和杰里米遇到这样一个问题，给他们一个3加仑和一个5加仑水壶，要求在5加仑水壶里有准确装入4加仑的水。
假定两个水壶A和B，供水量不限。可以使用三种方法装水
（1）给一个水壶装水
（2）把一个水壶倒空
（3）从一个水壶倒进另一个水壶。
当从一个水壶倒进另一个水壶时，如果第一个水壶倒空，或者第二个水壶装满酒不能再倒进了。例如，一个水壶A是5加仑和另一个水壶B是6加仑，水量是8加仑，则从水壶A倒进水壶B时，让水壶B充满水壶A剩3加仑。
问题有三个参数：C[a],C[b]和N，分别表示水壶A和水壶B的容量，目标水量N。解决问题的目标是给出一系列倒水的步骤，使水壶B中的水量恰好是N。
“pour A B”，表示将从水壶A倒进水壶B；“success”表示目标已经完成。


输入：
输入有多行，每行都是一个难题。每个难题又三个正整数：C[a]，C[b]和N。假设0<C[a]≤C[b]和N≤C[b]≤1000, 且A和B互质。
输出：
输出是由一系列倒水操作构成的，其目标是实现水壶B中有N加仑的水。最后一行是“success”；从第一列开始输出，末行没有空格。


C++程序（个人观点，仅供参考）
#include <iostream>
using namespace std;
int main()
{
    int ca,cb,n;
    while(cin>>ca>>cb>>n)
    {
        int bnow;
        int b=0;
        while(b!=0)
        {
            //只要B水壶不溢出，就让A水壶灌个够
            for(int i=0;i<=(cb-b)/ca;i++)
            {
                cout<<"fill A"<<endl;
                cout<<"pour A B"<<endl;
                bnow=b+ca*(i+1);    //B水壶现在的容量
                if(bnow==n)break;
            }
            if(bnow==n) break;     //退出while循环
            cout<<"empty B"<<endl;
            //最后一次灌满B水壶时，A水壶剩下的容量
            int a;
            a=ca-(cb-b)%ca;
            cout<<"pour A B"<<endl;
            //A水壶剩余部分倒入B水壶中
            b=a;
            if(b==n) break;
        }
        cout<<"success"<<endl;
    }
    return 0;
}


坐等哥喷饭，同时等待更好的程序和方法。。。

(A,B)=1，那么tA mod B == [0..B-1]的一个循环。
枚举求t，然后一直fill A,pour A B,empty B。最后就success了~

这个题我能想到三种做法:
1)建立S(i,j)(0<=i<=1000,0<=j<=1000),表示A中有i升B中有j升,建图然后广搜/深搜
2)7L的方法
3)因(A,B)=1,根据bezout定理存在整数X,Y满足AX+BY=C,那么X,Y>0的可以对应加满X/Y次,<0的可以对应EMPTYX/Y次，例如:
A=3,B=5,C=4,X=-2,Y=2的情形:
FILL B
B->A
EMPTY A
B->A
FILL B
B->A
EMPTY A(可以略去)
即可