Uva 571 Jugs () | Winterfell30's Blog

Uva 571 Jugs () | Winterfell30's Blog
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=512
In the movie ``Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle.


You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.


A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are

fill A
fill B
empty A
empty B
pour A B
pour B A
success

where ``pour A B" means ``pour the contents of jug A into jug B", and ``success" means that the goal has been accomplished.


You may assume that the input you are given does have a solution.

Input 

Input to your program consists of a series of input lines each defining one puzzle. Input for each puzzle is a single line of three positive integers: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal. You can assume and  and that A and B are relatively prime to one another.

Output 

Output from your program will consist of a series of instructions from the list of the potential output lines which will result in either of the jugs containing exactly N gallons of water. The last line of output for each puzzle should be the line ``success". Output lines start in column 1 and there should be no empty lines nor any trailing spaces.

Sample Input 

3 5 4
5 7 3

Sample Output 

fill B
pour B A
empty A
pour B A
fill B
pour B A
success
fill A
pour A B
fill A
pour A B
empty B
pour A B
success

每次把A倒满，然后倒到B里面，B慢了就清空，然后再倒A，最后一定会有个时候能够在B中得到n升水。
证明：按这样去倒水的话，我们可以用(n*A)%B表示B中的水量，由于A与B互质，那么容易得到这个函数的最小周期是B，并且在一个周期内，我们易证明这个函数的值均是不同的，而一个周期内（准确来说要包含两个临界点）n的取值是0-B，那么对应的值也必然会恰好覆盖满0-B，因此这样我们就一定可以得到一个满足要求的操作序列。


X. http://blog.csdn.net/hyczms/article/details/42560825
还有个简便算法，因为a和b互质，那么a * 1 % b到a * (b - 1) % b将会出现1到b - 1的所有数且不重复，那么就会有n的存在（n < b），所以可以先计算a * k % b == n 时k的值，那么就是fill A 和 pour A B一共 k 次，中间如果出现 B满了，就empty B 并 pour A B。

 int ca, cb, n;
 while (scanf("%d%d%d", &ca, &cb, &n) == 3) {
  if (cb == n) {
   printf("fill B\nsuccess\n");
   continue;
  }
  int k = 1, a = ca;
  while (a % cb != n) {
   k++;
   a += ca;
  }
  int temp = 0;
  for (int i = 1; i <= k; i++) {
   printf("fill A\npour A B\n");
   temp += ca;
   if (temp > cb) {
    printf("empty B\npour A B\n");
    temp -= cb;
   }
  }
  printf("success\n");
 }

int ca, cb, n;
void solve()
{
 int a = 0;
 int b = 0;
 while(1)
 {
  if (b == n)
  {
   printf("success\n");
   break;
  }
  else if (b == cb)
  {
   printf("empty B\n");
   b = 0;
  }
  if (!a)
  {
   printf("fill A\n");
   a = ca;
  }
  printf("pour A B\n");
  if (a + b > cb)
  {
   a = a + b -cb;
   b = cb;
  }
  else
  {
   b += a;
   a = 0;
  }
 }
}

http://blog.csdn.net/synapse7/article/details/16953175

 int na, nb, N, ca, cb;
 while (~scanf("%d %d %d", &ca, &cb, &N))
 {
  na = 0, nb = 0;
  while (nb != N)
  {
   if (na == 0)
   {
    puts("fill A");
    na = ca;
   }
   if (nb == cb)
   {
    puts("empty B");
    nb = 0;
   }
   nb += na;
   puts("pour A B");
   if (nb > cb) na = nb - cb, nb = cb;
   else na = 0;
  }
  puts("success");
 }

X. BFS
https://github.com/lamphanviet/competitive-programming/blob/master/uva-online-judge/accepted-solutions/571%20-%20Jugs.cpp

http://blog.csdn.net/u014733623/article/details/43448971

int vis[1010][1010],pre[1010][1010][3],c;
struct node
{
    int a,b;
};
queue<node> qu;
node A,B;
void solve(int num)
{
    if(vis[B.a][B.b]==0)
    {
        vis[B.a][B.b]=1;
        pre[B.a][B.b][0]=num;pre[B.a][B.b][1]=A.a;pre[B.a][B.b][2]=A.b;
        qu.push(B);
    }
}
void print(int a,int b)
{
    if(a==0 && b==0)
      return;
    print(pre[a][b][1],pre[a][b][2]);
    int k=pre[a][b][0];
    if(k==1)
      printf("fill A\n");
    else if(k==2)
      printf("fill B\n");
    else if(k==3)
      printf("empty A\n");
    else if(k==4)
      printf("empty B\n");
    else if(k==5)
      printf("pour A B\n");
    else if(k==6)
      printf("pour B A\n");
}
int main()
{
    int n,m,i,j,k,a,b;
    while(~scanf("%d%d%d",&a,&b,&c))
    {
        memset(vis,0,sizeof(vis));
        while(!qu.empty())
          qu.pop();
        A.a=0;A.b=0;
        qu.push(A);
        vis[0][0]=1;
        while(true)
        {
            A=qu.front();
            qu.pop();
            if(A.b==c)
              break;
            B.a=a;B.b=A.b;solve(1);
            B.a=A.a;B.b=b;solve(2);
            B.a=0;B.b=A.b;solve(3);
            B.a=A.a;B.b=0;solve(4);
            k=min(b-A.b,A.a);
            B.a=A.a-k;B.b=A.b+k;solve(5);
            k=min(a-A.a,A.b);
            B.a=A.a+k;B.b=A.b-k;solve(6);
        }
        print(A.a,A.b);
        printf("success\n");
    }

http://www.allenlipeng47.com/blog/index.php/2015/05/24/water-jug-problem/

Assume we have 2 jugs. Jug1 can contains 3 galons water, jug2 can contains 5 galons water. We can pour water into jug1 and jug2, empty 2 jugs, or we can pour water between 2 jugs. The question is how can we get a 4 galons water by pouring water between these 2 jugs.

Assume (x, y) is one of state of 2 jugs, which jug1 has x galons of water, jug2 has y galons of water. A possible movement is like this: (0, 5) -> (3, 2) -> (0, 2) -> (2, 0) -> (2, 5) -> (3, 4)

It turns out it is an AI problem. It has many states. Each state can transit to another state. And we find the goal state.

The transistion of a state can be described as below:
(x, y) -> (a, y) if x < a, fill first jug
(x, y) -> (x, b) if b < y, fill second jug
(x, y) -> (0, y) if x > 0, empty first jug
(x, y) -> (x, 0) if y > 0, empty second jug
(x, y) -> (a, y – (a – x)) if x + y > a, pour water from second jug to first jug
(x, y) -> (x – (b – y), b) if x + y > b, pour water from first jug to second jug
(x, y) -> (x + y, 0) if x + y <= a, pour water from second jug to first jug
(x, y) -> (0, x + y) if x + y <= b, pour water from first jug to second jug

During the search, we find if x or y becomes the goal volume we want. Below my code is a DFS implementation. It is a basic solution for water jug. The result may not be optimized.

    public static void waterJug(int a, int b, int target){
        /** Eliminate unproper input. */
        if(a <= 0 || b <= 0 || target > b){
            System.out.println("no solution for " + a + ", " + b + ", " + target);
            return;
        }
        BigInteger bigA = new BigInteger(String.valueOf(a));
        BigInteger bigB = new BigInteger(String.valueOf(b));
        int gcd = bigA.gcd(bigB).intValue();
        if(target % gcd != 0){
            System.out.println("no solution for " + a + ", " + b + ", " + target);
            return;
        }
        if(a > b){
            System.out.println("b is supposed to greater than a.");
            return;
        }
        HashSet stateSpace = new HashSet();   //stores all the states.
        WjState firstState = new WjState(0, 0);
        Stack stateStack = new Stack();
        stateStack.add(firstState);
        WjState curState = firstState;
        /** DFS to find target result. Result is not guaranteed to be optimized **/
        while(stateStack.size() > 0 && curState.x != target && curState.y != target){
            curState = stateStack.peek();
            WjState nextState = new WjState(0, 0, curState.step + 1, curState);
            if(curState.x < a && !stateSpace.contains(nextState.setPos(a, curState.y))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.y < b && !stateSpace.contains(nextState.setPos(curState.x, b))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x > 0 && !stateSpace.contains(nextState.setPos(0, curState.y))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.y > 0 && !stateSpace.contains(nextState.setPos(curState.x, 0))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y > a && !stateSpace.contains(nextState.setPos(a, curState.y - a + curState.x))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y > b && !stateSpace.contains(nextState.setPos(curState.x - b + curState.y, b))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y <=a && !stateSpace.contains(nextState.setPos(curState.x + curState.y, 0))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else if(curState.x + curState.y <=b && !stateSpace.contains(nextState.setPos(0, curState.x + curState.y))){
                stateSpace.add(nextState);
                stateStack.add(nextState);
            }
            else{
                stateStack.pop();
            }
        }// while
        /** Output result */
        StringBuffer output = new StringBuffer();
        while(curState != null){
            output.insert(0, " -> " + curState);
            curState = curState.pre;
        }
        output.delete(0, 4);
        System.out.println(output);
    }


    public static class WjState{
        int x, y;
        int step;   //How many steps is needed in order to reach the state
        WjState pre;    //to define the state before it.

        public boolean posEquals(WjState state){
            if(this.x==state.x&&this.y==state.y){
                return true;
            }
            return false;
        }

        public WjState(int x, int y){
            this.x = x;
            this.y = y;
        }

        public WjState(int x, int y, int step, WjState pre){
            this.x = x;
            this.y = y;
            this.step = step;
            this.pre = pre;
        }

        public WjState setPos(int x, int y){
            this.x = x;
            this.y = y;
            return this;
        }

        public int hashCode() {
            int hash = 1 ;
            hash = hash * 31 + x;
            hash = hash * 31 + y;
            return hash;
        }

        public String toString(){
            return "(" + this.x + ", " + this.y + ")";
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            WjState wjState = (WjState) o;
            if (x != wjState.x) return false;
            return y == wjState.y;
        }
    }

    public static void main(String[] args) {
        waterJug(3, 5, 4);
    }

Read full article from Uva 571 Jugs () | Winterfell30's Blog