Hướng dẫn giải của Bài 1 (đề An Giang 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
Xâu S có 4 hoặc 5 ký tự: hai ký tự cuối là năm, phần còn lại là ngày và tháng (ngày 1 hoặc 2 ký tự, tháng là phần còn lại). Cần tìm một cách cắt phần đầu thành ngày/tháng sao cho ngày hợp lệ với tháng đó trong năm tương ứng.
Năm thuộc thế kỷ 21 (2001–2100), nên hai chữ số cuối yy ứng với năm 2000 + yy, riêng yy = 00 là năm 2100 (không nhuận). Năm nhuận khi yy chia hết cho 4 và yy khác 0.
Sub 1: Vét cạn các cách cắt và các giá trị ngày, tháng — ~O(1)~
Thử lần lượt cách cắt ngày 1 ký tự rồi 2 ký tự; với mỗi cách, thử mọi ngày d (1..31) và tháng m (1..12), kiểm tra chữ số có khớp với phần đầu của S (có thể có số 0 đứng đầu) và ngày có nằm trong số ngày của tháng đó không.
Kết quả chấm: đạt 14/14 test.
#include <bits/stdc++.h>
using namespace std;
// Số ngày của tháng m trong năm 20yy, thế kỷ 21 là 2001-2100 nên yy = 00 ứng với năm 2100 (không nhuận)
int soNgay(int m, int yy) {
if (m == 2) return (yy != 0 && yy % 4 == 0) ? 29 : 28;
if (m == 4 || m == 6 || m == 9 || m == 11) return 30;
return 31;
}
// Chuyển số x thành xâu có đúng w chữ số (thêm số 0 đứng đầu nếu cần)
string pad(int x, int w) {
string s = to_string(x);
while ((int)s.size() < w) s = "0" + s;
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BAI01.INP", "r")) {
freopen("BAI01.INP", "r", stdin);
freopen("BAI01.OUT", "w", stdout);
}
string s;
cin >> s;
int L = s.size();
int yy = stoi(s.substr(L - 2));
string nam = s.substr(L - 2);
string prefix = s.substr(0, L - 2); // ngày + tháng
int k = prefix.size();
// Vét cạn: thử ngày ngắn (1 ký tự) trước, rồi ngày 2 ký tự; với mỗi cách, thử mọi d và m
for (int c = 1; c <= 2 && c < k; c++) {
string sd = prefix.substr(0, c), sm = prefix.substr(c);
for (int d = 1; d <= 31; d++)
for (int m = 1; m <= 12; m++) {
if (pad(d, c) != sd || pad(m, k - c) != sm) continue;
if (d <= soNgay(m, yy)) {
cout << sd << "/" << sm << "/" << nam << "\n";
return 0;
}
}
}
cout << "KHONG TAO DUOC\n";
return 0;
}
Sub 2: Cắt trực tiếp rồi kiểm tra — ~O(1)~
Cắt trực tiếp phần đầu thành ngày và tháng theo đúng thứ tự ưu tiên (ngày 1 ký tự trước), đổi sang số rồi kiểm tra tháng trong [1, 12] và ngày trong [1, số ngày của tháng]. Khi hợp lệ thì in phần ngày, tháng, năm đúng như trong xâu (giữ số 0 đứng đầu, ví dụ 3/02/19).
Bẫy: năm 00 phải coi là 2100 (không nhuận), nên 29/2/00 là không hợp lệ.
Kết quả chấm: đạt 14/14 test.
#include <bits/stdc++.h>
using namespace std;
// Số ngày của tháng m trong năm 20yy, thế kỷ 21 là 2001-2100 nên yy = 00 ứng với năm 2100 (không nhuận)
int soNgay(int m, int yy) {
if (m == 2) return (yy != 0 && yy % 4 == 0) ? 29 : 28;
if (m == 4 || m == 6 || m == 9 || m == 11) return 30;
return 31;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BAI01.INP", "r")) {
freopen("BAI01.INP", "r", stdin);
freopen("BAI01.OUT", "w", stdout);
}
string s;
cin >> s;
int L = s.size();
int yy = stoi(s.substr(L - 2)); // 2 ký tự cuối: năm (thế kỷ 21)
string nam = s.substr(L - 2);
string prefix = s.substr(0, L - 2); // phần đầu: ngày + tháng
int k = prefix.size();
// Thử ngày 1 ký tự trước, rồi ngày 2 ký tự; tháng là phần còn lại (có thể có số 0 đứng đầu)
for (int c = 1; c <= 2 && c < k; c++) {
string sd = prefix.substr(0, c), sm = prefix.substr(c);
int d = stoi(sd), m = stoi(sm);
if (m < 1 || m > 12) continue;
if (d < 1 || d > soNgay(m, yy)) continue;
cout << sd << "/" << sm << "/" << nam << "\n";
return 0;
}
cout << "KHONG TAO DUOC\n";
return 0;
}
Bình luận