2014-05-05

UVa 10603 - Fill

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

There are three jugs with a volume of a, b and c liters. (a, b, and c are positive integers not greater than 200). The first and the second jug are initially empty, while the third

is completely filled with water. It is allowed to pour water from one jug into another until either the first one is empty or the second one is full. This operation can be performed zero, one or more times.

You are to write a program that computes the least total amount of water that needs to be poured; so that at least one of the jugs contains exactly d liters of water (d is a positive integer not greater than 200). If it is not possible to measure d liters this way your program should find a smaller amount of water d’ < d which is closest to d and for which d’ liters could be produced. When d’ is found, your program should compute the least total amount of poured water needed to produce d’ liters in at least one of the jugs.

Input

The first line of input contains the number of test cases. In the next T lines, T test cases follow. Each test case is given in one line of input containing four space separated integers - a, b, c and d.

Output

The output consists of two integers separated by a single space. The first integer equals the least total amount (the sum of all waters you pour from one jug to another) of poured water. The second integer equals d, if d liters of water could be produced by such transformations, or equals the closest smaller value d’ that your program has found.

Sample Input

1
2
3

2
2 3 4 2
96 97 199 62

Sample Output

1 2	2 2 9859 62

Solution

題目描述：

有三個桶子，它們各能裝 a ， b ，和 c 公升。（a , b , c 都為正整數而且不超過200。）第一，第二個桶子最剛開始是空的，但是第三個桶子卻是裝滿水的。你可以從 X 桶子把水倒入 Y 桶子裡並且把 Y 桶子裝滿，要不然就是把 X 桶子倒乾。倒水的步驟可以執行很多次。

你要寫一個程式去計算整個過程中至少要倒多少水才能達成目標，即這三個桶子中有一個桶子剩 d 公升的水。（d 為正整數而且不超過200。）但是如果你沒有辦法達成目標，也就是沒有辦法讓任何一個桶子剩下 d 公升的水，那麼請達成 d’ 公升，d’ 比 d小但是最接近 d。當 d’ 找到了，請你輸出整個過程至少要倒多少水才能達成 d’ 公升。

luckycatluckycat.kshs.kh.edu.tw/homework/q10603.htm

題目解法：

這題重新測試，導致之前寫的 DFS 方式直接 TLE 炸掉，只要改寫成 BFS 即可通關。
原理仍一樣，模擬六種互倒入的方式，每一種倒入又牽扯到溢滿的問題。

#include <stdio.h>
#include <queue>
using namespace std;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define oo 0xfffffff
int A, B, C, D, JUG[3];
int dp[201][201][201], res[201];
queue<int> QA, QB, QC, QTOT;
void pushNode(int a, int b, int c, int tot) {
    QA.push(a), QB.push(b), QC.push(c), QTOT.push(tot);
}
void update(int a, int b, int c, int tot) {
    if(tot >= res[D])   return;
    if(tot >= dp[a][b][c])  return;
    dp[a][b][c] = tot;
    res[a] = min(res[a], tot);
    res[b] = min(res[b], tot);
    res[c] = min(res[c], tot);
    if(a < B-b) pushNode(0, b+a, c, tot+a);
    else        pushNode(a-(B-b), B, c, tot+(B-b));
    if(a < C-c) pushNode(0, b, c+a, tot+a);
    else        pushNode(a-(C-c), b, C, tot+(C-c));
    if(b < A-a) pushNode(a+b, 0, c, tot+b);
    else        pushNode(A, b-(A-a), c, tot+(A-a));
    if(b < C-c) pushNode(a, 0, c+b, tot+b);
    else        pushNode(a, b-(C-c), C, tot+(C-c));
    if(c < A-a) pushNode(a+c, b, 0, tot+c);
    else        pushNode(A, b, c-(A-a), tot+(A-a));
    if(c < B-b) pushNode(a, b+c, 0, tot+c);
    else        pushNode(a, B, c-(B-b), tot+(B-b));
}
void bfs(int a, int b, int c, int tot) {
    QA.push(a), QB.push(b), QC.push(c), QTOT.push(tot);
    while (!QA.empty()) {
        a = QA.front(), QA.pop();
        b = QB.front(), QB.pop();
        c = QC.front(), QC.pop();
        tot = QTOT.front(), QTOT.pop();
        update(a, b, c, tot);
    }
    
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int i, j, k;
        scanf("%d %d %d %d", &A, &B, &C, &D);
        for(i = 0; i <= A; i++)
            for(j = 0; j <= B; j++)
                for(k = 0; k <= C; k++)
                    dp[i][j][k] = oo;
        JUG[0] = A, JUG[1] = B, JUG[2] = C;
        for(i = 0; i <= D; i++)
            res[i] = oo;
        bfs(0, 0, C, 0);
        while(res[D] == oo) D--;
        printf("%d %d\n", res[D], D);
    }
    return 0;
}

Morris' Blog