Đề bài
Cho một số N không có số 0 dẫn đầu. Nhiệm vụ là tìm số lần di chuyển tối thiểu để làm cho N chia hết cho 25. Tại mỗi lần di chuyển, có thể hoán đổi bất kỳ hai chữ số liền kề nào và đảm bảo rằng tại bất kỳ thời điểm nào số không được chứa số 0 dẫn đầu. Nếu không thể làm cho N chia hết cho 25 thì in -1.
Nếu N = 5071 thì cần 4 lần di chuyển để làm cho nó chia hết cho 25:
5071 → 5701 → 7501 → 7510 → 7150
Thuật toán
1. Duyệt qua tất cả các cặp chữ số trong số. Giả sử chữ số đầu tiên trong cặp ở vị trí 'i' và chữ số thứ hai ở vị trí 'j'. 2. Đặt các chữ số này vào hai vị trí cuối cùng của số 3. Nếu số có số 0 dẫn đầu. Tìm chữ số khác 0 bên trái nhất và di chuyển nó đến vị trí đầu tiên. 4. Nếu số hiện tại chia hết cho 25 thì cập nhật câu trả lời với số lần hoán đổi
Ví dụ
#include <iostream> #include <algorithm> #include <string> #include <climits> using namespace std; int requiredMoves(long long n){ string str = to_string(n); int ans = INT_MAX; int len = str.size(); for (int i = 0; i < len; ++i) { for (int j = 0; j < len; ++j) { if (i == j) continue; string temp = str; int cnt = 0; for (int k = i; k < len - 1; ++k) { swap(temp[k], temp[k + 1]); ++cnt; } for (int k = j - (j > i); k < len - 2; ++k) { swap(temp[k], temp[k + 1]); ++cnt; } int pos = -1; for (int k = 0; k < len; ++k) { if (temp[k] != '0') { pos = k; break; } } for (int k = pos; k > 0; --k) { swap(temp[k], temp[k - 1]); ++cnt; } long long num = atoll(temp.c_str()); if (num % 25 == 0) ans = min(ans, cnt); } } if (ans == INT_MAX) return -1; return ans; } int main(){ int n = 5071; cout << "Minimum required moves: " << requiredMoves(n) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum required moves: 4