// include
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cmath>
#include <string>
#include <utility>
#include <deque>

using namespace std;

// 数値を文字列に変換する
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

const int Width      = 10; // 幅
const int Target     = 4; // 目的の値
const int PitcherNum = 3; // ピッチャーの数
const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値

// 終了条件を満たすか調べる
bool check(int *Pitchers)
{
    REP(i, PitcherNum)
        if (Pitchers[i] == Target) return true;
    return false;
}

// 現在の状態を保持する構造体
struct Status
{
    int p[3];
    int cnt;
    string ret;
};

// 評価関数
int Eval(Status state)
{
    int ret = 0;
    ret -= state.cnt;
    for (auto n : state.p)
    {
        if (n % Target == 0) ret += 10;
        ret -= abs(Target - n);
    }
    return ret;
}

// pairの比較(ソート用)
bool comp(pair<int, Status> lhs,  pair<int, Status> rhs)
{
    return lhs.first > rhs.first;
}

// 最良優先探索で解く
Status SolveBestFirstSearch()
{
    bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）

    // 配列の初期化
    REP(i, PitcherMax[0]+1)
        REP(j, PitcherMax[1]+1)
            REP(k, PitcherMax[2]+1)
                flag[i][j][k] = false;

    // 探索用のdeque
    deque<pair<int, Status>> nexts;

    pair<int, Status> state;
    state.second.p[0] = PitcherMax[0];
    state.second.p[1] = 0;
    state.second.p[2] = 0;
    state.second.cnt = 0;
    state.second.ret = toString(state.second.p[0]) + " " + toString(state.second.p[1]) + " " + toString(state.second.p[2]) + "\n";
    state.first = Eval(state.second);

    // 初期状態をdequeに追加
    nexts.push_front(state);

    while (!nexts.empty()) // dequeが空になるまでループ
    {
        state = nexts.front(); nexts.pop_front(); // dequeの先頭から要素を一つ取り出す
        if (check(state.second.p)) break; // 終了条件を満たしていれば終わる
        if (flag[state.second.p[0]][state.second.p[1]][state.second.p[2]]) continue; // 訪れたことがあるならスキップ
        else flag[state.second.p[0]][state.second.p[1]][state.second.p[2]] = true; // 訪れたことがないなら、フラグを立てる

        pair<int, Status> newState; // 次の状態
        REP (i, PitcherNum)
        {
            REP (j, PitcherNum)
            {
                if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)

                // 中身を移す処理
                newState.second.p[i] = max(state.second.p[i] - (PitcherMax[j] - state.second.p[j]), 0);
                newState.second.p[j] = min(state.second.p[j] + state.second.p[i], PitcherMax[j]);
                newState.second.p[3 - i - j] = state.second.p[3 - i - j];

                // 移動した回数を1増やす
                newState.second.cnt = state.second.cnt + 1;

                // ピッチャーの状態遷移をメモする
                newState.second.ret = state.second.ret + toString(newState.second.p[0]) + " " + toString(newState.second.p[1]) + " " + toString(newState.second.p[2]) + "\n";

                // ピッチャーの中身が移動していない場合はスキップする
                if (newState.second.p[i] == state.second.p[i]) continue;

                // 評価値を計算
                newState.first = Eval(newState.second);

                // dequeに状態を追加
                nexts.push_back(newState);
            }
        }

        // 評価値順にソート
        sort(nexts.begin(), nexts.end(), comp);

        // 幅より大きければ評価値が小さい枝を削除
        while (nexts.size() > Width) nexts.pop_back();
    }

    if (check(state.second.p)) return state.second;
    else
    {
        state.second.cnt = -1;
        state.second.ret = "目的の値になりませんでした";
        return state.second;
    }
}

int main()
{
    Status result = SolveBestFirstSearch();

    cout << "目的の値: " << Target << endl;
    cout << "移動回数: " << result.cnt << endl;
    cout << "ピッチャーの状態遷移:" << endl;
    cout << result.ret << endl;

    return 0;
}