Program

#include <bits/stdc++.h>

using namespace std;

int cost(int current, map<int, int> &next) {

    if (current <= 0)
        return INT_MAX;

    if (current == 1)
        return 0;

    if (current == 4) {
        next[4] = 1;
        return 1;
    }

    if (current % 2 == 0) {
        int rec = cost(current/2, next);
        if (rec == INT_MAX)
            return rec;
        next[current] = current/2;
        return rec+1;
    }

    else {
        int rec = cost((current-3)/2, next);
        next[current] = current-3;
        next[current-3] = (current-3)/2;
        if (rec == INT_MAX)
            return rec;
        return rec + 2;
    }

}

int main() {

    int target;
    cin >> target;

    map<int, int> next;

    int steps = cost(target, next);

    if (steps == INT_MAX) {
        cout << 0 << endl;
        return 0;
    }

    steps += 1;

    cout << steps << endl;

    vector<string> outputs;

    int current = target;
    while (current != 1) {
        int m = next[current];
        if (abs(m - current) == 3) {
            outputs.push_back("ADD");
        }
        else {
            outputs.push_back("MUL");
        }
        current = m;
    }

    for (int i = (int) outputs.size()-1; i >= 0; i--) {
        cout << outputs[i] << endl;
    }

    cout << "END" << endl;
    return 0;

}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: ACCEPTED

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER