/* ID: mytbk921 LANG: C TASK: milk3 */ #include #include 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