Giả sử chúng ta có một chuỗi số S với n chữ số. Xét S đại diện cho một đồng hồ số và toàn bộ chuỗi hiển thị một số nguyên từ 0 đến 10^n - 1. Nếu có số chữ số ít hơn, nó sẽ hiển thị các số 0 ở đầu. Làm theo các phép toán:
Giảm số trên đồng hồ đi 1, hoặc
Hoán đổi hai chữ số
Chúng ta muốn đồng hồ sẽ hiển thị 0 với số phép toán tối thiểu. Chúng ta phải đếm số phép toán cần thiết để làm điều đó.
Ví dụ, nếu đầu vào là S = "1000", thì đầu ra sẽ là 2, vì ta có thể hoán đổi 1 đầu tiên với 0 cuối, chuỗi sẽ thành "0001" rồi giảm đi 1 để được "0000".
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
n := kích thước của S x := chữ số tại vị trí S[n - 1] for khởi tạo i := 0, khi i <= n - 2, cập nhật (tăng i lên 1), do: if S[i] không bằng '0', thì: x := x + (chữ số tại vị trí S[i]) + 1 return x
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(string S) { int n = S.size(); int x = S[n - 1] - '0'; for (int i = 0; i <= n - 2; i++) if (S[i] != '0') x = x + S[i] + 1 - '0'; return x; } int main() { string S = "1000"; cout << solve(S) << endl; }Đầu vào
"1000"
Đầu ra
2