// Saarland University: <(OvO)> #include #define sz(a) ((int)(a).size()) #define divceil(a, b) ((a) + (b) - 1) / (b) using namespace std; #ifdef ONPC string to_string(const char* s) { return s; } template string to_string(const T& cont) { string ans = ""; for (bool fst = true; const auto& val: cont) { if (!fst) { ans += ", "; } ans += to_string(val); fst = false; } return ans + "}"; } void debug_print_collection() { cerr << endl; } template void debug_print_collection(First val, Args... args) { cerr << " " << to_string(val); debug_print_collection(args...); } #define debug(...) { cerr << "@@@ [" << #__VA_ARGS__ << "] ="; debug_print_collection(__VA_ARGS__);} #else #define debug(...) ; #define NDEBUG #endif mt19937 rnd(123); typedef long long ll; typedef long double ld; int solve() { int n; if (!(cin >> n)) { return 1; } vector>> a(3, vector>(3)); string A, B; cin >> A >> B; int bal = 0; for (int i = 0; i < n; i++) { if (A[i] == 'M' && B[i] == 'C') { bal++; } else if (A[i] == 'C' && B[i] == 'M') { bal--; } } if (bal > 0) { for (int i = 0; i < n; i++) { if (A[i] == 'C') { A[i] = 'M'; } else if (A[i] == 'M') { A[i] = 'C'; } if (B[i] == 'C') { B[i] = 'M'; } else if (B[i] == 'M') { B[i] = 'C'; } } } auto get_val = [&](char c) { if (c == '-') { return 0; } else if (c == 'M') { return 1; } else { return 2; } }; vector> tp(n); for (int i = 0; i < n; i++) { if (A[i] == B[i]) { continue; } a[get_val(A[i])][get_val(B[i])].push_back(i); tp[i] = make_pair(get_val(A[i]), get_val(B[i])); } vector> seqs; while (sz(a[2][1]) > sz(a[1][2])) { if (!a[0][2].empty() && !a[1][0].empty()) { seqs.push_back({a[0][2].back(), a[2][1].back(), a[1][0].back()}); a[0][2].pop_back(); a[2][1].pop_back(); a[1][0].pop_back(); } else { break; } } while (sz(a[2][1]) > sz(a[1][2])) { if (!a[0][2].empty()) { seqs.push_back({a[0][2].back(), a[2][1].back()}); a[0][2].pop_back(); a[2][1].pop_back(); } else { break; } } while (!a[0][1].empty() && !a[1][0].empty()) { seqs.push_back({a[0][1].back(), a[1][0].back()}); a[0][1].pop_back(); a[1][0].pop_back(); } while (!a[0][2].empty() && !a[2][0].empty()) { seqs.push_back({a[0][2].back(), a[2][0].back()}); a[0][2].pop_back(); a[2][0].pop_back(); } if (!a[1][2].empty() || !a[2][1].empty()) { assert(!seqs.empty()); int x = seqs[0].back(); seqs[0].pop_back(); int t = tp[x].first; if (t == 2) swap(a[1][2], a[2][1]); while (!a[1][2].empty() && !a[2][1].empty()) { seqs[0].push_back(a[1][2].back()); seqs[0].push_back(a[2][1].back()); } if (t == 2) swap(a[1][2], a[2][1]); seqs[0].push_back(x); } for (int xx = 1; xx < 2; xx++) { for (int y = 0; y < 3; y++) { if (xx != y) { assert(a[xx][y].empty()); } } } int cnt = 0; for (auto seq : seqs) { bool fst = true; int lst = seq.back(); for (int xx : seq) { cnt++; //cout << "DRIVE " << xx + 1 << '\n'; if (!fst) { //cout << "DROPOFF\n"; cnt++; } if (xx != lst && tp[xx].second != 0) { //cout << "PICKUP\n"; cnt++; } fst = false; } } cout << cnt << endl; for (auto seq : seqs) { bool fst = true; int lst = seq.back(); for (int xx : seq) { cout << "DRIVE " << xx + 1 << '\n'; if (!fst) { cout << "DROPOFF\n"; } if (xx != lst && tp[xx].second != 0) { cout << "PICKUP\n"; } fst = false; } } return 0; } int32_t main() { #ifdef ONPC assert(freopen("G.txt", "r", stdin)); #endif int TET = 1e9; // cin >> TET; for (int i = 1; i <= TET; i ++) { if (solve()) { break; } #ifdef ONPC cout << "__________________" << endl; #endif } #ifdef ONPC cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; #endif } /* g++ -std=c++20 -Wall -Wextra -Wshadow -D_GLIBCXX_DEBUG -DONPC -O2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -o ex template.cpp && ./ex */