Hướng dẫn giải của [200 đề thầy Đức] Bài 59: Nhầm chữ số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Hai số $A, B$ được chép sai: mỗi chữ số $5$ có thể bị chép thành $6$ và ngược lại, độc lập ở từng vị trí. Cần tìm tổng nhỏ nhất và lớn nhất có thể nhận được.
Sub 1: Vét cạn mọi cách chép — ~O(2^k)~ với $k$ là số chữ số $5$ hoặc $6$ (không quá 6 chữ số mỗi số)
Liệt kê mọi cách chép có thể của $A$ và của $B$ (mỗi chữ số 5 hoặc 6 có hai lựa chọn), rồi thử mọi cặp để lấy tổng nhỏ nhất và lớn nhất. Vì $A, B \le 10^5$ nên mỗi số có tối đa 6 chữ số, số cách chép tối đa $2^6 \cdot 2^6$. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
// Liệt kê mọi cách đọc sai của một số: mỗi chữ số 5 hoặc 6 có thể bị chép thành chữ kia.
void variants(const string &s, int pos, string cur, vector<long long> &out) {
if (pos == (int)s.size()) {
out.push_back(stoll(cur));
return;
}
char c = s[pos];
if (c == '5' || c == '6') {
variants(s, pos + 1, cur + '5', out); // chép thành 5
variants(s, pos + 1, cur + '6', out); // chép thành 6
} else {
variants(s, pos + 1, cur + c, out); // chữ số khác giữ nguyên
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
cin >> a >> b;
vector<long long> va, vb;
variants(a, 0, "", va);
variants(b, 0, "", vb);
// Vét cạn mọi cặp cách chép (tối đa 2^6 x 2^6 cặp), lấy tổng nhỏ nhất và lớn nhất.
long long mn = LLONG_MAX, mx = LLONG_MIN;
for (long long x : va)
for (long long y : vb) {
mn = min(mn, x + y);
mx = max(mx, x + y);
}
cout << mn << " " << mx << "\n";
return 0;
}
Sub 2: Đổi cả nhóm chữ số — ~O(log A + log B)~
Nhận xét: đổi một chữ số $6$ thành $5$ luôn làm số nhỏ đi đúng $10^k$ (với $k$ là vị trí của chữ số đó), còn đổi $5$ thành $6$ làm số lớn lên đúng $10^k$. Các vị trí độc lập nhau nên:
- Tổng nhỏ nhất: đổi mọi chữ số $6$ thành $5$ ở cả hai số.
- Tổng lớn nhất: đổi mọi chữ số $5$ thành $6$ ở cả hai số.
Ví dụ $11$ và $56$: tổng nhỏ nhất $11 + 55 = 66$, lớn nhất $11 + 66 = 77$. Ví dụ $16796$ và $58786$: nhỏ nhất $15795 + 58785 = 74580$, lớn nhất $16796 + 68786 = 85582$.
Bẫy cần chú ý: đề cho phép chép sai nhiều chữ số, không chỉ một chữ số. Tổng tối đa khoảng $2 \cdot 10^5$ nên int đủ, nhưng dùng long long cho chắc.
#include <bits/stdc++.h>
using namespace std;
// Đổi mọi chữ số 6 thành 5 (hoặc mọi chữ số 5 thành 6) trong số s, rồi đọc thành số nguyên.
long long replaceDigit(const string &s, char from, char to) {
string t = s;
for (char &c : t)
if (c == from) c = to;
return stoll(t);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string a, b;
cin >> a >> b;
// Mỗi chữ số 6 đổi thành 5 làm số nhỏ đi, nên đổi hết 6 -> 5 cho tổng nhỏ nhất.
// Mỗi chữ số 5 đổi thành 6 làm số lớn lên, nên đổi hết 5 -> 6 cho tổng lớn nhất.
// Các chữ số ở các vị trí khác nhau độc lập nhau nên làm như vậy là tối ưu.
long long mn = replaceDigit(a, '6', '5') + replaceDigit(b, '6', '5');
long long mx = replaceDigit(a, '5', '6') + replaceDigit(b, '5', '6');
cout << mn << " " << mx << "\n";
return 0;
}
Bình luận