USACO Training>My Training>Section 1.4>Mother's Milk

Mother's Milk

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT
A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in) 

8 9 10

OUTPUT FORMAT
A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in) 

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

Solution (Me)


/*
ID: sgospod1
PROG: milk3
LANG: C++
*/
#include <stdio.h>
#include <string.h> 
#include <time.h> 
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <set>

#define STANDARD_INPUT
/*#define PRINT_DEBUG*/
#define BUCKET_COUNT 3
#define MAX_AMOUNT 20

using namespace std;

int Capacity[BUCKET_COUNT]; /* 1<=Capacity[i]<=20*/
int Buckets[BUCKET_COUNT] = {0,0,0}; 
int Amount[MAX_AMOUNT+1];
char done[MAX_AMOUNT+1][MAX_AMOUNT+1][MAX_AMOUNT+1];

#ifdef PRINT_DEBUG
#include <sys/timeb.h>
ofstream log ("log.out");
#endif    

bool Done(int* b)
{
    if(done[b[0]][b[1]][b[2]]==1) return true;
    done[b[0]][b[1]][b[2]] = 1;
    return false;
}

void Pour(int* b, int from, int to)
{
#ifdef PRINT_DEBUG
    log << "{" << b[0] << "," << b[1] << "," << b[2] << "}  " << from << " " << to << endl;
#endif

    int m = b[from];
    if(Capacity[to]-b[to] < b[from]) m = Capacity[to]-b[to];
    
    b[to] += m;
    b[from] -= m;
}

void NextPour(int* b)
{
    if(Done(b)) return;

    if(b[0]==0) 
    {    
        Amount[b[BUCKET_COUNT-1]]=1;
#ifdef PRINT_DEBUG
        log << "amount " << b[BUCKET_COUNT-1] << endl;
#endif    
    }

    for(int from=0; from<BUCKET_COUNT; from++)
    {
        for(int to=0; to<BUCKET_COUNT; to++)
        {
            int* bb = new int[3];
            bb[0]=b[0]; bb[1]=b[1]; bb[2]=b[2];
            Pour(bb, from, to);
            NextPour(bb);
            delete bb;
        }
    }
}


int main()
{
#ifdef PRINT_DEBUG
    struct _timeb timebuf;
    char currtime[26];
    _ftime_s(&timebuf); 
    ctime_s( currtime, 26, &(timebuf.time));
    cerr << "Start time: " << setw(19) << currtime <<  "." << timebuf.millitm << endl;
#endif
#ifdef STANDARD_INPUT
    istream &fin = cin;
    ostream &fout = cout;
#else
    ofstream fout ("milk3.out");
    ifstream fin ("milk3.in");
#endif
    assert(fin != NULL && fout != NULL);
 
    memset(done, 0, (MAX_AMOUNT+1)*(MAX_AMOUNT+1)*(MAX_AMOUNT+1));
    memset(Amount, 0, (MAX_AMOUNT+1)*sizeof(int));

    for(int i=0; i<BUCKET_COUNT; i++) fin >> Capacity[i];

    Buckets[BUCKET_COUNT-1] = Capacity[BUCKET_COUNT-1];
    NextPour(Buckets);

    int i=0;
    for(; i<=MAX_AMOUNT; i++) if(Amount[i]) {fout << i; i++; break;} 
    for(; i<=MAX_AMOUNT; i++) if(Amount[i]) fout << " " << i;
    fout << endl;

#ifdef PRINT_DEBUG
    _ftime_s(&timebuf); 
    ctime_s( currtime, 26, &(timebuf.time));
    cerr << "End time  : " << setw(19) << currtime <<  "." << timebuf.millitm << endl;
#endif
    return 0;
}

All solutions

Tests
Input Output