USACO 1.4 Mother’s Milk

发布于 2019-04-09  961 次阅读


题目描述

农民约翰有三个容量分别是A,B,C升的桶,A,B,C分别是三个从1到20的整数, 最初,A和B桶都是空的,而C桶是装满牛奶的。有时,农民把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约,牛奶不会有丢失。

写一个程序去帮助农民找出当A桶是空的时候,C桶中牛奶所剩量的所有可能性。

输入

单独的一行包括三个整数A,B和C。

输出

只有一行,升序地列出当A桶是空的时候,C桶牛奶所剩量的所有可能性。

思路

强行枚举每一种情况就可以了(居然可以过= =)

/*
ID: a1192631
PROG: milk3
LANG: C++
*/
#include 
int a[50][50][50],f[50],l[50][50][50];
int x,y,z;
int dfs(int i,int j,int k)
{
    if (l[i][j][k]==1) return 0;
    l[i][j][k]=1;
    if (i==0)
    {
        f[k]=1;
    }
    if (k<=x-i) dfs(i+k,j,0);
    if (k>x-i) dfs(x,j,k-x+i);
    if (k<=y-j) dfs(i,j+k,0);
    if (k>y-j) dfs(i,y,k-y+j);

    if (j<=x-i) dfs(i+j,0,k);
    if (j>x-i) dfs(x,j-x+i,k);
    if (j<=z-k) dfs(i,0,k+j);
    if (j>z-k) dfs(i,j-z+k,z);

    if (i<=y-j) dfs(0,j+i,k);
    if (i>y-j) dfs(i-y+j,y,k);
    if (i<=z-k) dfs(0,j,k+i);
    if (i>z-k) dfs(i-z+k,j,z);
    return 0;
}
int main()
{
    freopen("milk3.in", "r", stdin);
    freopen("milk3.out", "w", stdout);
    scanf("%d%d%d",&x,&y,&z);
    dfs(0,0,z);
    for (int i=0;i<=z-1;i++)
    {
        if (f[i]==1) printf("%d ",i);
    }
    printf("%d\n",z);
    return 0;
}
]]>