diff options
author | Iru Cai <mytbk920423@gmail.com> | 2018-04-16 19:06:32 +0800 |
---|---|---|
committer | Iru Cai <mytbk920423@gmail.com> | 2018-04-16 19:06:32 +0800 |
commit | ad4e2420e822b8a115aac6124307b89447578782 (patch) | |
tree | 6f4db875081597e2e64dd4221a97bbff25503dcc /1.5/milk3.c | |
parent | a7721767628a51b752ad3a96eb334734241dcd8b (diff) | |
download | usaco-ad4e2420e822b8a115aac6124307b89447578782.tar.xz |
1.2~1.5
Diffstat (limited to '1.5/milk3.c')
-rw-r--r-- | 1.5/milk3.c | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/1.5/milk3.c b/1.5/milk3.c new file mode 100644 index 0000000..f50a61d --- /dev/null +++ b/1.5/milk3.c @@ -0,0 +1,148 @@ +/* +ID: mytbk921 +LANG: C +TASK: milk3 +*/ + +#include <stdio.h> +#include <string.h> + +int possible[21]; +int searched[21][21][21][3]; + +typedef struct +{ + int amount; + int capacity; +}bucket; + +void test_0(bucket, bucket, bucket); +void test_1(bucket, bucket, bucket); +void test_2(bucket, bucket, bucket); + +void pour(const bucket *a, const bucket *b, bucket *_a, bucket *_b) +{ + _a->capacity = a->capacity; + _b->capacity = b->capacity; + + if (b->amount+a->amount<=b->capacity){ + _a->amount = 0; + _b->amount = a->amount+b->amount; + }else{ + _a->amount = a->amount-(b->capacity-b->amount); + _b->amount = b->capacity; + } +} + +void test_0(bucket a, bucket b, bucket c) +{ + if (a.amount==0){ + possible[c.amount] = 1; + return; + } + + if (searched[a.amount][b.amount][c.amount][0]){ + return; + }else{ + searched[a.amount][b.amount][c.amount][0] = 1; + } + + bucket _a,_b,_c; + if (b.amount!=b.capacity){ + pour(&a, &b, &_a, &_b); + if (_a.amount==0){ + possible[c.amount] = 1; + } + test_1(_a, _b, c); + test_2(_a, _b, c); + } + if (c.amount!=c.capacity){ + pour(&a, &c, &_a, &_c); + if (_a.amount==0){ + possible[_c.amount] = 1; + } + test_1(_a, b, _c); + test_2(_a, b, _c); + } +} + +void test_1(bucket a, bucket b, bucket c) +{ + if (b.amount==0){ + return; + } + + if (searched[a.amount][b.amount][c.amount][1]){ + return; + }else{ + searched[a.amount][b.amount][c.amount][1] = 1; + } + + bucket _a,_b,_c; + if (a.amount!=a.capacity){ + pour(&b, &a, &_b, &_a); + test_0(_a, _b, c); + test_2(_a, _b, c); + } + if (c.amount!=c.capacity){ + pour(&b, &c, &_b, &_c); + test_0(a, _b, _c); + test_2(a, _b, _c); + } +} + +void test_2(bucket a, bucket b, bucket c) +{ + if (c.amount==0){ + return; + } + + if (searched[a.amount][b.amount][c.amount][2]){ + return; + }else{ + searched[a.amount][b.amount][c.amount][2] = 1; + } + + bucket _a,_b,_c; + if (a.amount!=a.capacity){ + pour(&c, &a, &_c, &_a); + test_0(_a, b, _c); + test_1(_a, b, _c); + } + if (b.amount!=b.capacity){ + pour(&c, &b, &_c, &_b); + test_0(a, _b, _c); + test_1(a, _b, _c); + } +} + +int main() +{ + FILE *fin, *fout; + bucket a, b, c; + int i; + + a.amount = b.amount = 0; + + fin = fopen("milk3.in", "r"); + fout = fopen("milk3.out", "w"); + fscanf(fin, "%d%d%d", &a.capacity, &b.capacity, &c.capacity); + fclose(fin); + + c.amount = c.capacity; + + memset(possible, 0, sizeof(possible)); + memset(searched, 0, sizeof(searched)); + + possible[c.amount] = 1; + test_2(a, b, c); + + for (i=0; i<c.amount; i++){ + if (possible[i]){ + fprintf(fout, "%d ", i); + } + } + fprintf(fout, "%d\n", c.amount); + fclose(fout); + return 0; +} |