Hướng dẫn giải của Phiếu giảm giá (đề Hòa Bình 2021)
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
Mỗi số x có 4 chữ số tạo ra hai tổng 2 chữ số: s1 = x1 + x2 (hai chữ số đầu) và s2 = x3 + x4 (hai chữ số cuối). Màn hình hiển thị số lớn hơn trước, mỗi tổng viết đủ 2 chữ số. Cần tìm số x nhỏ nhất có 4 chữ số (chữ số đầu khác 0) sao cho màn hình hiển thị đúng n, hoặc in 0 nếu không có.
Sub 1: Vét cạn — ~O(9000)~
Thử lần lượt mọi x từ 1000 đến 9999, tính chuỗi hiển thị theo đúng quy tắc (tổng lớn hơn viết trước, mỗi tổng 2 chữ số) và so với n. Gặp x đầu tiên khớp thì in ra.
Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Tra ve chuoi hien thi khi nhap x (4 chu so): cong 2 chu so dau, 2 chu so cuoi,
// viet so lon hon truoc, moi so viet du 2 chu so.
string display(int x) {
int s1 = x / 1000 + (x / 100) % 10; // tong 2 chu so dau
int s2 = (x / 10) % 10 + x % 10; // tong 2 chu so cuoi
if (s1 < s2) swap(s1, s2);
char buf[8];
sprintf(buf, "%02d%02d", s1, s2);
return string(buf);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
string n;
cin >> n;
// Vet can: thu lan luot cac so x co 4 chu so (chu so dau khac 0) tu nho den lon
for (int x = 1000; x <= 9999; x++) {
if (display(x) == n) {
cout << x << "\n";
return 0;
}
}
cout << 0 << "\n";
return 0;
}
Sub 2: Ghép hai tổng — ~O(1)~
Tách n thành hai nhóm 2 chữ số A = n / 100 và B = n % 100. Đề yêu cầu số lớn hơn viết trước nên cần A ≥ B, và hai tổng nằm trong [0, 18]. Hai tổng có thể là (A, B) hoặc (B, A). Với mỗi cặp tổng, số nhỏ nhất có 2 chữ số x1 x2 với x1 + x2 = s là x1 = max(1, s - 9), và tương tự cho cặp chữ số sau. Lấy giá trị nhỏ nhất trong các ứng viên.
Đạt 20/20 test. Chú ý trường hợp tổng bằng 0: VD n = 1800 thì x = 9900 (9 + 9 = 18, 0 + 0 = 00).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int n;
cin >> n;
// Hai nhom 2 chu so: A = chu so hien thi truoc (lon hon), B = sau (nho hon)
int A = n / 100, B = n % 100;
if (A < B || A > 18 || B > 18) { // moi tong 2 chu so nam trong [0, 18]
cout << 0 << "\n";
return 0;
}
// Hai tong (s1, s2) co the la (A, B) hoac (B, A); moi tong s can 2 chu so (x1 x2) voi x1 >= 1
int best = -1;
int sums[2][2] = {{A, B}, {B, A}};
for (auto &p : sums) {
int sf = p[0], sb = p[1];
if (sf < 1) continue; // x1 >= 1 nen tong phai >= 1
// So nho nhat co 2 chu so (x1 x2) voi x1 + x2 = sf: x1 = max(1, sf - 9)
int x1 = max(1, sf - 9), x2 = sf - x1;
// So nho nhat co 2 chu so (x3 x4) voi x3 + x4 = sb: x3 = max(0, sb - 9)
int x3 = max(0, sb - 9), x4 = sb - x3;
int cand = (x1 * 10 + x2) * 100 + x3 * 10 + x4;
if (best < 0 || cand < best) best = cand;
}
cout << (best < 0 ? 0 : best) << "\n";
return 0;
}
Bình luận