题目链接:http://poj.org/problem?id=3414
Time Limit: 1000MS Memory Limit: 65536K

Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;
  2. DROP(i)      empty the pot i to the drain;
  3. POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

Problem solving report:

Description: 给你A，B两个杯子，及他们的最大容量，三种操作方法，让你判断最少用多少此方法可以让任意一个被子里装有C升水。并打印操作方法。
Problem solving: 这里很容易想到广搜，设初始状态为(i，j)，一共就只有六种变化，A杯倒满，B杯倒满，A杯倒出完，B杯倒出完，A到给B，B到给A，任意一种状态i或者j达到C就停止。注意要打印操作方法，用一个string存的操作顺序。这一题和HDU里面的非常可乐非常的相似，初始状态我们可以令A、B瓶为空，C瓶装无穷的水，这样就转化成三个瓶子之间的倒水问题。

Accepted Code:

#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 150;
int v[3], k;
bool vis[MAXN][MAXN];
string str_[][3] = {{"", "4", "2"}, {"5", "", "3"}, {"0", "1", ""}};
string str[10] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
struct cup {
    string str;
    int v[3], t;
    cup(string str_, int *v_, int t_) {
        t = t_;
        str = str_;
        memcpy(v, v_, 3 * sizeof(int));
    }
};
void pour(cup &p, int a, int b) {//从a倒b
    int cnt = p.v[a] + p.v[b];
    p.v[b] = min(cnt, v[b]);
    p.v[a] = cnt - p.v[b];
}
void BFS() {
    queue <cup> Q;
    vis[0][0] = true;
    int v_[3] = {0, 0, v[2]};
    Q.push(cup("", v_, 0));
    while (!Q.empty()) {
        cup p = Q.front();
        Q.pop();
        if (!(p.v[0] != k && p.v[1] != k)) {//有一个瓶子符合
            printf("%d\n", p.t);
            for (int i = 0; i < p.str.length(); i++)
                printf("%s\n", str[p.str[i] - '0'].c_str());
            return ;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j) {
                    cup q = p;
                    pour(q, i, j);//从i倒j
                    q.str = p.str + str_[i][j];//记录路径
                    if (!vis[q.v[0]][q.v[1]]) {//该状态没有出现过
                        Q.push(cup(q.str, q.v, q.t + 1));
                        vis[q.v[0]][q.v[1]] = true;
                    }
                }
            }
        }
    }
    printf("impossible\n");
}
int main() {
    while (~scanf("%d%d%d", &v[0], &v[1], &k)) {
        memset(vis, false, sizeof(vis));
        v[2] = MAXN << 1;
        BFS();
    }
    return 0;
}