Hướng dẫn giải của [2627 KS3] Câu 1: Hạn trả sách
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
Cho t phiếu mượn (ngày, tháng, năm mượn, thời hạn k ngày), tính ngày hạn trả và thứ trong tuần. Năm nhuận theo lịch Gregorian, 01/01/1900 là Thứ Hai, k có thể lên tới 10^9.
Sub 1: Mô phỏng từng ngày — ~O(k · t)~
Xuất phát từ ngày mượn, cộng từng ngày một k lần: tăng ngày, nếu vượt số ngày của tháng thì sang tháng mới, nếu vượt tháng 12 thì sang năm mới. Thứ trong tuần cũng tăng 1 mỗi bước. Đúng nhưng với k lên tới 10^9 thì quá chậm.
Kết quả chấm: 12/20 (SUB ok 12/20, TLE 8, WA 0)
#include <bits/stdc++.h>
using namespace std;
// Nam nhuan: chia het cho 4 nhung khong chia het cho 100, hoac chia het cho 400
bool nhuan(long long y) { return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }
int soNgay(int m, long long y) {
if (m == 2) return nhuan(y) ? 29 : 28;
if (m == 4 || m == 6 || m == 9 || m == 11) return 30;
return 31;
}
// So ngay tu 01/01/1900 (la Thu Hai) den ngay d/m/y
long long demNgay(long long d, int m, long long y) {
long long D = 0;
for (long long yy = 1900; yy < y; yy++) D += nhuan(yy) ? 366 : 365;
for (int mm = 1; mm < m; mm++) D += soNgay(mm, y);
return D + d - 1;
}
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 t;
cin >> t;
while (t--) {
long long d, m, y, k;
cin >> d >> m >> y >> k;
long long thu = demNgay(d, m, y) % 7; // 0 la Thu Hai
// Vet can: cong tung ngay mot, k lan
for (long long i = 0; i < k; i++) {
d++;
thu = (thu + 1) % 7;
if (d > soNgay((int)m, y)) {
d = 1; m++;
if (m > 12) { m = 1; y++; }
}
}
cout << d << " " << m << " " << y << " " << thu + 2 << "\n";
}
return 0;
}
Sub 2: Đếm ngày từ 01/01/1900 rồi đổi ngược — ~O(t · (400 + 12))~
Đổi ngày mượn thành số ngày D kể từ 01/01/1900 (Thứ Hai là D mod 7 = 0). Hạn trả là D + k, rồi đổi ngược thành ngày/tháng/năm. Chu kỳ 400 năm có đúng 146097 ngày nên đưa D về trong một chu kỳ rồi duyệt tối đa 400 năm và 12 tháng. Mã thứ = (D mod 7) + 2. Dùng long long vì D có thể lớn.
Kết quả chấm: 20/20 (PASS 20/20)
#include <bits/stdc++.h>
using namespace std;
bool nhuan(long long y) { return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }
int soNgay(int m, long long y) {
if (m == 2) return nhuan(y) ? 29 : 28;
if (m == 4 || m == 6 || m == 9 || m == 11) return 30;
return 31;
}
// So ngay tu 01/01/1900 (la Thu Hai) den ngay d/m/y
long long demNgay(long long d, int m, long long y) {
long long D = 0;
for (long long yy = 1900; yy < y; yy++) D += nhuan(yy) ? 366 : 365;
for (int mm = 1; mm < m; mm++) D += soNgay(mm, y);
return D + d - 1;
}
// Tu so ngay D (tinh tu 01/01/1900) suy ra ngay/thang/nam.
// Chu ky 400 nam co dung 146097 ngay nen dua D ve trong mot chu ky roi cong dan.
void chuyenNgay(long long D, long long &d, int &m, long long &y) {
y = 1900 + 400 * (D / 146097);
long long rem = D % 146097;
while (rem >= (nhuan(y) ? 366 : 365)) { rem -= nhuan(y) ? 366 : 365; y++; }
m = 1;
while (rem >= soNgay(m, y)) { rem -= soNgay(m, y); m++; }
d = rem + 1;
}
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 t;
cin >> t;
while (t--) {
long long d, m, y, k;
cin >> d >> m >> y >> k;
long long D = demNgay(d, (int)m, y) + k; // so ngay cua han tra
long long nd, ny;
int nm;
chuyenNgay(D, nd, nm, ny);
// D mod 7 = 0 la Thu Hai, nen ma thu = D mod 7 + 2
cout << nd << " " << nm << " " << ny << " " << (D % 7) + 2 << "\n";
}
return 0;
}
Bình luận