#include <iostream>
#include <functional>
#include <string>
#include <map>
#include <vector>
using namespace std;
const int start = 5, fin = 38; // Начальное и конечное числа
int main()
{
    // Прямой ход расчета
    int branchCount = 0; // Счётчик просмотренных веток дерева
    // function<int(int, int, string)> calc = [&calc, &branchCount](int x, int fin, string way) {
    //     branchCount++;
    //     if(x<fin)
    //         return calc(x + 4, fin, way + " +4") + calc(x * 2, fin, way + " *2");
    //     else
    //     if(x==fin)
    //     {
    //         cout<<way<<endl;
    //         return 1;
    //     }
    //     return 0;
    // };
    // cout << "Function#1" << endl;
    // cout << "From " << start << " to " << fin << endl;
    // cout << "Allowed operations: +4, *2" << endl;
    // cout << "Variants:" << endl
    //      << calc(start, fin, "") << endl;
    // cout << "branchCount:" << branchCount << endl;
    // function<int(int, int, string)> reverseCalc = [&reverseCalc, &branchCount](int x, int fin, string way) {
    //     branchCount++;
    //     if (x > fin)
    //         if ( x % 2 == 0)
    //             return reverseCalc(x - 4, fin, way + " -4") + reverseCalc(x / 2, fin, way + " /2");
    //         else
    //             return reverseCalc(x - 4, fin, way + " -4");
    //     else if (x == fin)
    //     {
    //         cout << way << endl;
    //         return 1;
    //     }
    //     return 0;
    // };
    // branchCount = 0;
    // cout << endl << "Function#2" << endl;
    // cout << "From " << fin << " to " << start << endl;
    // cout << "Allowed operations: -4, /2" << endl;
    // cout << "Variants:" << endl
    //      << reverseCalc(fin, start, "") << endl;
    // cout << "branchCount:" << branchCount << endl;

    // function<int(int, int, string, bool)> Restrcalc = [&Restrcalc, &branchCount](int x, int fin, string way, bool restrictionCondition) {
    //     branchCount++;
    //     if (x == 34)
    //         restrictionCondition = true;
    //     if (x > 34 && restrictionCondition == false)
    //         return 0;
    //     if (x < fin)
    //         return Restrcalc(x + 4, fin, way + " +4", restrictionCondition) + Restrcalc(x * 2, fin, way + " *2", restrictionCondition);
    //     else if (x == fin && restrictionCondition)
    //     {
    //         cout << way << endl;
    //         return 1;
    //     }
    //     return 0;
    // };

    // branchCount = 0;
    // cout <<  endl << "Function#3" << endl;
    // cout << "From " << fin << " to " << start << " passing throught 34" << endl;
    // cout << "Allowed operations: -4, /2" << endl;
    // cout << "Variants:" << endl
    //      << Restrcalc(start, fin, "", false) << endl;
    // cout << "branchCount:" << branchCount << endl;

    // function<int(int, int, string, bool)> revRestrcalc = [&revRestrcalc, &branchCount](int x, int fin, string way, bool restrictionCondition) {
    //     branchCount++;
    //     if (x == 34)
    //         restrictionCondition = true;
    //     if (x < 34 && restrictionCondition == false)
    //         return 0;
    //     if (x > fin)
    //         if (x % 2 == 0)
    //             return revRestrcalc(x - 4, fin, way + " -4", restrictionCondition) + revRestrcalc(x / 2, fin, way + " /2", restrictionCondition);
    //         else
    //             return revRestrcalc(x - 4, fin, way + " -4", restrictionCondition);
    //     else if (x == fin && restrictionCondition)
    //     {
    //         cout << way << endl;
    //         return 1;
    //     }
    //     return 0;
    // };

    // branchCount = 0;
    // cout << endl << "Function#4" << endl;
    // cout << "From " << fin << " to " << start << " passing throught 34" << endl;
    // cout << "Allowed operations: -4, /2" << endl;
    // cout << "Variants:" << endl
    //      << revRestrcalc(fin, start, "", false) << endl;
    // cout << "branchCount:" << branchCount << endl;
    branchCount = 0;
    map<int, vector<string>> phase;
    function<int(int, int, string)> calc = [&calc, &branchCount, &phase](int x, int fin, string way) {
        branchCount++;
        if(x<fin)
            return calc(x + 4, fin, way + " +4") + calc(x * 2, fin, way + " *2");
        else
        if(x==fin)
        {
            cout<<way<<endl;
            return 1;
        }
        return 0;
    };
    auto result = phaseCalc(start, fin, "", {});
    cout << "Branch count: " << branchCount << endl;
    cout << "Result len: " << result.size() << endl;
    for (auto s : result)
        cout << s << endl;
}