p396.in1
======================
6
RULURL

=================
p396.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int inf = (int)1e9 + 42;

int n;
string s;

void read() {
    cin >> n;
    cin >> s;
}

void solve() {
    // The problem fundamentally isn't hard - we can use dynamic programming
    // that tracks the position of the two legs as part of the state, if they
    // pressed the buttons, and where in the beat are we currently at. The main
    // part is all the details about the transitions. One easy to miss detail is
    // that we could make some moves even during a 'N' character.

    map<char, int> char_to_idx = {{'L', 0}, {'U', 1}, {'R', 2}, {'D', 3}};
    vector<char> idx_to_char = {'L', 'U', 'R', 'D'};

    vector<vector<vector<vector<int>>>> dp(
        n + 1, vector<vector<vector<int>>>(
                   4, vector<vector<int>>(4, vector<int>(4, inf))
               )
    );

    struct State {
        int left, right, last_pressed;
    };
    vector<vector<vector<vector<State>>>> parent(
        n + 1, vector<vector<vector<State>>>(
                   4, vector<vector<State>>(4, vector<State>(4, {-1, -1, -1}))
               )
    );

    dp[0][0][2][2] = 0;

    for(int i = 0; i < n; i++) {
        char req_char = s[i];
        int req = (req_char == 'N') ? -1 : char_to_idx[req_char];

        for(int left = 0; left < 4; left++) {
            for(int right = 0; right < 4; right++) {
                if(left == right) {
                    continue;
                }

                for(int last = 0; last < 4; last++) {
                    if(dp[i][left][right][last] == inf) {
                        continue;
                    }

                    int cur_cost = dp[i][left][right][last];

                    auto update = [&](int cost, int new_left, int new_right,
                                      int new_last) {
                        int new_cost = cur_cost + cost;
                        if(new_cost <
                           dp[i + 1][new_left][new_right][new_last]) {
                            dp[i + 1][new_left][new_right][new_last] = new_cost;
                            parent[i + 1][new_left][new_right][new_last] = {
                                left, right, last
                            };
                        }
                    };

                    if(req == -1) {
                        update(0, left, right, 2);
                    }
                    if(req == -1 || left == req) {
                        update(1, left, right, 0);
                    }
                    if(req == -1 || right == req) {
                        update(1, left, right, 1);
                    }

                    for(int new_pos = 0; new_pos < 4; new_pos++) {
                        if(new_pos == right) {
                            continue;
                        }
                        if(new_pos == 2 && right == 0) {
                            continue;
                        }
                        if(req != -1 && new_pos != req) {
                            continue;
                        }
                        update(
                            (last == 0 || last == 3) ? 9 : 3, new_pos, right, 0
                        );
                    }

                    for(int new_pos = 0; new_pos < 4; new_pos++) {
                        if(new_pos == left) {
                            continue;
                        }
                        if(left == 2 && new_pos == 0) {
                            continue;
                        }
                        if(req != -1 && new_pos != req) {
                            continue;
                        }
                        update(
                            (last == 1 || last == 3) ? 9 : 3, left, new_pos, 1
                        );
                    }

                    for(int new_left = 0; new_left < 4; new_left++) {
                        for(int new_right = 0; new_right < 4; new_right++) {
                            if(new_left == new_right) {
                                continue;
                            }
                            if(new_left == 2 && new_right == 0) {
                                continue;
                            }
                            if(req != -1 && new_left != req &&
                               new_right != req) {
                                continue;
                            }
                            update(10, new_left, new_right, 3);
                        }
                    }
                }
            }
        }
    }

    int best_cost = inf;
    int best_left = -1, best_right = -1, best_last = -1;
    for(int left = 0; left < 4; left++) {
        for(int right = 0; right < 4; right++) {
            for(int last = 0; last < 4; last++) {
                if(dp[n][left][right][last] < best_cost) {
                    best_cost = dp[n][left][right][last];
                    best_left = left;
                    best_right = right;
                    best_last = last;
                }
            }
        }
    }

    cout << best_cost << '\n';

    vector<pair<int, int>> path;
    int cur_left = best_left, cur_right = best_right, cur_last = best_last;
    for(int i = n; i > 0; i--) {
        path.push_back({cur_left, cur_right});
        State prev = parent[i][cur_left][cur_right][cur_last];
        cur_left = prev.left;
        cur_right = prev.right;
        cur_last = prev.last_pressed;
    }

    reverse(path.begin(), path.end());

    for(auto [left, right]: path) {
        cout << idx_to_char[left] << idx_to_char[right] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p396.ans2
======================
25
LR
LU
RU
DL
DL
DR
LR
LR
LR

=================
p396.in2
======================
9
LURLDRLNL

=================
statement.txt
======================
396. Dance it up!
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Dance Dance Revolution is a game machine which forces a player to dance. The goal of the game is to step the dance-floor buttons in appropriate time. There are four buttons on the floor: LEFT, UP, RIGHT and DOWN.

Petya is a big DDR fun and spends all his spare time dancing on it. But he has a problem: he doesn't have enough of stamina. Therefore he asks you to write a program which can compute the optimal sequence of actions for a song in order to minimize the energy required to dance it.

The song for the DDR machine is divided into several equal time intervals (beats). For each beat it shows the buttons to be pressed. It is allowed to press non-required buttons (there is no penalty for doing this), but all required buttons should be pressed. For now, Petya is not a very good dancer and you can assume that each beat requires at most one button pressed.

The initial player position is "left leg on the LEFT button and right leg on the RIGHT button". Each beat a player is allowed to follow one of these patterns:



Not to change legs position. Not to press buttons. This action costs no energy.
Not to change legs position. Press the button on which one of the legs is. This action costs 1 point of energy.
Move the leg, which didn't press a button at the previous beat, to a vacant button and press it. Another leg doesn't change position. This action costs 3 points of energy.
Move the leg, which pressed a button at the previous beat, to a vacant button and press it. Another leg doesn't change position. This action costs 9 points of energy.
Jump with both legs to any two different buttons and press both of them. This action costs 10 points of energy.



After testing a Prove-Of-Concept version of the program, Vasya realized that if program instructs him to move into position "left leg on RIGHT button and right leg on LEFT button" he can't see monitor with further instructions and fails immediately. So, this position is illegal.

Input
The first line of the input file contains integer number N — length of the song in beats (1≤ N≤ 1000). The second line consists of exactly N characters and contains instructions for each beat. Characters 'L', 'U', 'R' or 'D' mean that the required button for a beat is LEFT, UP, RIGHT or DOWN correspondingly. Character 'N' means that there are no required buttons at this beat.

Output
In the first line output the amount of energy required for stepping the song. After that, output exactly N lines with two characters in each. Each line should contain the optimal legs position (the first character for the left leg, the second character — for the second) for the corresponding beat. Use 'L', 'U', 'R' and 'D' characters for LEFT, UP, RIGHT and DOWN buttons correspondingly. If there are several solutions you can output any of them.

Example(s)
sample input
sample output
6
RULURL
14
LR
UR
UL
UL
UR
LR

sample input
sample output
9
LURLDRLNL
25
LR
LU
RU
DL
DL
DR
LR
LR
LR

=================
p396.ans1
======================
14
LR
UR
UL
UL
UR
LR

=================
