USACO : Mother’s Milk



/*
ID: tausiq11
PROG: milk3
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

set <int> output;
int vis [20 + 3] [20 + 3];
int cap_a, cap_b, cap_c;
int Total;

void pour_milk (int a, int b, int cb, int *ta, int *tb)
{
	while ( a && b < cb ) {
		a--;
		b++;
	}

	*ta = a;
	*tb = b;
}

void dp (int b, int c)
{
	if ( vis [b] [c] ) return;
	vis [b] [c] = true;

	int a = Total - b - c;
	int tmp_a = a, tmp_b = b, tmp_c = c;

	if ( a == 0 ) output.insert (c);

	pour_milk (c, a, cap_a, &tmp_c, &tmp_a); dp (b, tmp_c);
	pour_milk (c, b, cap_b, &tmp_c, &tmp_b); dp (tmp_b, tmp_c);
	pour_milk (a, b, cap_b, &tmp_a, &tmp_b); dp (tmp_b, c);
	pour_milk (a, c, cap_c, &tmp_a, &tmp_c); dp (b, tmp_c);
	pour_milk (b, c, cap_c, &tmp_b, &tmp_c); dp (tmp_b, tmp_c);
	pour_milk (b, a, cap_a, &tmp_b, &tmp_a); dp (tmp_b, c);
}

int main ()
{
	freopen ("milk3.in", "r", stdin);
	freopen ("milk3.out", "w", stdout);

	scanf ("%d %d %d", &cap_a, &cap_b, &cap_c);
	Total = cap_c;

	dp (0, cap_c);

	bool space = false;

	for ( set <int>::iterator it = output.begin (); it != output.end (); it++ ) {
		if ( space ) printf (" "); space = true;
		cout << *it;
	}

	cout << endl;

	return 0;
}
// @END_OF_SOURCE_CODE

One thought on “USACO : Mother’s Milk

  1. USER: [tausiq11]
    TASK: milk3
    LANG: C++
    
    Compiling...
    Compile: OK
    
    Executing...
       Test 1: TEST OK [0.022 secs, 3020 KB]
       Test 2: TEST OK [0.000 secs, 3020 KB]
       Test 3: TEST OK [0.000 secs, 3020 KB]
       Test 4: TEST OK [0.000 secs, 3020 KB]
       Test 5: TEST OK [0.000 secs, 3020 KB]
       Test 6: TEST OK [0.011 secs, 3020 KB]
       Test 7: TEST OK [0.000 secs, 3020 KB]
       Test 8: TEST OK [0.000 secs, 3020 KB]
       Test 9: TEST OK [0.000 secs, 3020 KB]
       Test 10: TEST OK [0.011 secs, 3020 KB]
    
    All tests OK.
    Your program ('milk3') produced all correct answers!  This is your
    submission #3 for this problem.  Congratulations!
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s