Chương trình C++ tìm số phép toán tối thiểu để biến số thành 0

Cho chuỗi số S độ dài n (đồng hồ số hiển thị 0 đến 10^n-1, có leading zeros). Hai phép toán:

1. Giảm số trên đồng hồ đi 1.
2. Hoán đổi hai chữ số bất kỳ.

Mục tiêu: biến đồng hồ thành toàn số 0 với ít phép toán nhất.

Quan sát

• Chữ số cuối cùng (hàng đơn vị) chỉ có thể giảm xuống 0 bằng phép trừ, cần S[n-1] lần.
• Mỗi chữ số khác 0 ở vị trí i (từ 0 đến n-2) có thể hoán đổi về hàng đơn vị (1 phép), sau đó giảm (giá trị chữ số lần), tổng cộng digit + 1 phép.
• Chữ số 0 không cần làm gì.

Tổng phép toán = S[n-1] + Σ (S[i] + 1) cho mọi i < n-1 với S[i] != '0'.

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
  int n = S.size();
  int x = S[n - 1] - '0'; // chữ số cuối
  for (int i = 0; i <= n - 2; i++)
    if (S[i] != '0')
      x = x + (S[i] - '0') + 1;
  return x;
}

int main() {
  string S = "1000";
  cout << solve(S) << endl; // Output: 2
  return 0;
}

Với "1000": chữ số cuối = 0, chữ số đầu = 1 -> 1+1 = 2 phép (hoán đổi 1 về cuối, trừ 1).