BOJ. Match The Numbers (2494)

Problem

Dial operation and dynamic programming

The dials are numbered from left to right. A positive turn at dial i rotates dial i and every dial to its right (below it in the problem’s description). A negative turn rotates only dial i. A turn count is signed: positive means left, negative means right.

Process dials from left to right. Let dp[i][carry] be the minimum number of turns used through dial i, where carry is the total left rotation modulo 10 from earlier dials. This is exactly the rotation already applied to the current dial by earlier left turns. Its current digit is (source[i] + carry) mod 10. Let left be the smallest nonnegative rotation that changes that digit to the target digit.

There are two choices. Turn left by left: this costs left and changes the carry to (carry + left) mod 10, affecting later dials. Or, when left is nonzero, turn right by left - 10: this costs 10 - left and preserves the carry. When left is zero, the only useful choice is no turn; a full ten-step rotation cannot improve a solution. Store the previous carry and signed turn for each chosen state. After finding the least cost among the final carries, follow those predecessors backward and print one signed turn for every dial.

There are 10 carry states per dial and at most two transitions per state, so the time and memory complexities are both O(N · 10).

C++17

#include <array>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

    int n;
    string source, target;
    cin >> n >> source >> target;

    constexpr int INF = 1'000'000'000;
    vector<array<int, 10>> dp(n + 1);
    vector<array<int, 10>> previousCarry(n + 1);
    vector<array<int, 10>> chosenTurn(n + 1);
    for (auto& row : dp) row.fill(INF);
    dp[0][0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int carry = 0; carry < 10; ++carry) {
            if (dp[i][carry] == INF) continue;

            const int current = (source[i] - '0' + carry) % 10;
            const int left = (target[i] - '0' - current + 10) % 10;

            const int nextCarry = (carry + left) % 10;
            const int leftCost = dp[i][carry] + left;
            if (leftCost < dp[i + 1][nextCarry]) {
                dp[i + 1][nextCarry] = leftCost;
                previousCarry[i + 1][nextCarry] = carry;
                chosenTurn[i + 1][nextCarry] = left;
            }

            if (left != 0) {
                const int rightCost = dp[i][carry] + 10 - left;
                if (rightCost < dp[i + 1][carry]) {
                    dp[i + 1][carry] = rightCost;
                    previousCarry[i + 1][carry] = carry;
                    chosenTurn[i + 1][carry] = left - 10;
                }
            }
        }
    }

    int carry = 0;
    for (int state = 1; state < 10; ++state) {
        if (dp[n][state] < dp[n][carry]) carry = state;
    }
    const int bestCost = dp[n][carry];

    vector<int> turns(n);
    for (int i = n; i > 0; --i) {
        turns[i - 1] = chosenTurn[i][carry];
        carry = previousCarry[i][carry];
    }

    cout << bestCost << '\n';
    for (int i = 0; i < n; ++i) {
        cout << i + 1 << ' ' << turns[i] << '\n';
    }
    return 0;
}