
Đặt vấn đề
Đề bài

Vậy là kì thi HSG khốc liệt đã kết thúc, Tuấn mạnh dạn rủ crush đi Aeon chơi và bất ngờ thay, cô ấy đồng ý!
Tuấn vui sướng đến sớm, đứng ngay trước cửa CGV từ ngày , tháng , năm và bắt đầu đếm từng giây chờ người thương đến.
Nhưng một tiếng… rồi một ngày… rồi một tuần… Cô ấy vẫn chưa tới. Tuấn vẫn kiên nhẫn, mỗi ngày đánh dấu thêm một gạch trên tường…..
Nhiệm vụ
Sau ngày chờ đợi (vẫn chưa thấy bóng dáng cô ấy đâu), hãy xác định ngày Tuấn nhận ra sự thật phũ phàng - tức là ngày thứ kể từ khi bắt đầu đợi.
Input
Một dòng gồm bốn số nguyên .
Trong đó:
- số lượng test cases ( )
- số ngày Tuấn đã chờ ở Aeon ( )
- ngày, tháng, năm Tuấn bắt đầu chờ. ( )
Output
In ra thứ, ngày, tháng, năm hiện tại, tức là ngày Tuấn kết thúc ngày chờ đợi (và có lẽ… quay về nhà :c).
Ghi chú
Thứ được in ra bằng tiếng Anh, viết hoa chữ cái đầu: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday
Ngày tháng năm ngăn được cách bởi dấu ‘/’
Sử dụng lịch quốc tế (lịch Gregorian).
Subtasks
Subtask | Giới hạn | Điểm |
|---|---|---|
1 | , , | 10 |
2 | , , | 20 |
3 | , , | 30 |
4 | , , | 40 |
Ý tưởng
Subtask 1
Ta có thể dễ dàng AC subtask 1 thông qua vòng lặp cơ bản và xử lý trường hợp năm nhuận với độ phức tạp tổng thể là .
Subtask 2
Nhận thấy có thể lên tới nên việc giải bằng vòng lặp hoàn toàn gãy cánh. Ta cần công thức hóa bằng cách chuyển ngày tháng năm thành một số nguyên đại diện cho số ngày trôi qua ngày kể từ mốc kết hợp với ánh xạ. Kết quả là bài toán có thể được tối ưu xuống độ phức tạp
Subtask 3
Với thì chắc chắn ta cần phải tìm được một giải pháp chạy trong thông qua việc tối ưu rất rất nhiều. Mà để đạt được độ phức tạp tưởng như không thể này thì ta cần phải tìm ra tính chất đặc biệt nằm trong lịch Gregorian. Nhận thấy lịch Gregorian tuần hoàn chu kỳ trong 400 năm, ta có thể giải quyết subtask 3 với độ phức tạp chỉ: .
Subtask 4
Tuy nhiên, với thì mọi chuyện không còn đơn giản hơn nữa… Lúc này, ta cần khai thác thêm các biến đổi và tính chất toán học để tối ưu. Cụ thể phải phân tích như thế nào và vì sao lại cần làm thế, mình sẽ giải thích chi tiết trong blog hôm nay nhé:)
Tổng quát về lịch thế giới
Độ dài trung bình của một năm chí tuyến được đo lường 365.2422 ngày. Nhiều các loại lịch khác như lịch Julius (trước 10/1582) đã cố gắng đơn giản hóa việc xử lý phần lẻ bằng cách làm tròn thành 365.25 ngày theo quy tắc:
năm nào chia hết cho 4 thì có năm nhuận.
Tuy nhiên, việc làm tròn này tạo ra sai số 0,0078 ngày/năm so với độ dài năm chí tuyến, tương đương khoảng 1 ngày lệch sau mỗi 128 năm.
Điều đó có nghĩa là theo thời gian, ngày xuân phân và hạ chí dần trôi khỏi mốc thiên văn thực tế, dẫn đến một số mùa màng “đến sớm” hơn lịch ghi nhận.
Lịch Gregorian (10/1582)
Nhằm khắc phục việc bị dư 0,0078 ngày mỗi năm, Giáo hoàng Gregory XIII đã ban hành lịch Gregorian vào tháng 10 năm 1582 với quy tắc như sau:
Năm chia hết cho 4 là năm nhuận.
Năm chia hết cho 100 không là năm nhuận.
Năm chia hết cho 400 là năm nhuận.
Qua đó, độ dài một năm theo lịch Gregorian quy ước 365.2425 ngày, tức là lớn hơn độ dài trung bình của một năm chí tuyến ngày/năm. Tức xấp xỉ chỉ 26 giây mỗi năm và tương đương 1 ngày sau khoảng 3300 năm.
Tính toán số ngày trôi qua kể từ 1/1/0
Tính chất đặc biệt của Lịch Gregorian
Ta thực hiện phép biến đổi như sau:
Tham số hóa nó thì ta có số ngày trong y năm là:
(Với là hàm đếm số ngày trôi qua kể từ và y là số năm đã qua)
Nếu xét trong không gian rời rạc, tức là chỉ đếm số ngày thực tế, ta được hàm tương ứng:
(Với là hàm rời rạc của )
Qua công thức trên thì ta có nhận xét như sau: Cứ mỗi bốn năm, sẽ được cộng thêm 1 ngày nhuận, nhưng việc này sẽ bị hủy bỏ sau mỗi thế kỷ . Song, mỗi sẽ cộng lại 1 ngày nhuận. (nguyên tắc bao hàm - loại trừ.)
Nhờ đó, ta nhận thấy lịch Gregorian lặp lại chính xác sau mỗi 400 năm và tuần hoàn theo chu kỳ này. Nên ta chỉ cần xét và tối ưu trong khung 400 năm đầu tiên là đủ.
Vấn đề sai số
Vì hàm nằm trong không gian rời rạc nên chắc chắn sẽ có sai số so với hàm gốc (vì hàm này luôn trả về giá trị nguyên với ).
Sai số này được biểu diễn bằng hàm sau:
Ta có nhận xét như sau:
Do tồn tại sai số này, việc tìm năm sau khi biết tổng số ngày kể từ 1/1/0 rất khó khăn và không thể chính xác tuyệt đối, dù vẫn cho xấp xỉ cực kỳ gần với thực tế.
Tính toán năm từ tổng số ngày trôi qua
Cho là số ngày trôi qua kể từ 1/1/0, ta có thể tính số năm y dựa vào công thức sau:
Công thức trên đúng với độ chính xác cao trong hầu hết các trường hợp, ngoại trừ khi nằm gần mốc chuyển giao năm (tức là khi xấp xỉ một giá trị nào đó - tổng số ngày tính đến hết năm thứ ). Tại những mốc này, sai số do sự xuất hiện hoặc biến mất của ngày nhuận trở nên rõ rệt, khiến phép chia xấp xỉ không còn chính xác.
Ví dụ: Giả sử ta có ngày và muốn tìm năm tương ứng.
Nếu lấy phần nguyên thì ta sẽ cho rằng năm, ta kiểm tra lại như sau:
Thực tế, năm lịch Gregorian mới chính xác là 36524 ngày (do năm thế kỷ không phải năm nhuận).
Đây chính là trường hợp D nằm trong khoảng sai số so với ranh giới của năm thứ 100, nếu dùng công thức để đảo ngược ngày thành năm, ta sẽ thu được kết quả sai lệch một năm.
Cách khắc phục sai số từ ngày
Vì làm việc trong C++ nên trước hết cần phải đưa công thức về dạng tính toán hoàn toàn bằng số nguyên, nhằm tránh sai số khi thao tác với dấu phẩy động (floating-point numbers):
Nhận thấy thường khi bị lệch năm thì y thực của chúng ta sẽ ở dạng … Để né hiện tượng này thì ta cần bù thêm một hằng số sao cho , mục đích là để khi floor thì giá trị bằng hoặc . Lựa chọn chính xác và an toàn nhất đó là sử dụng sai số cực đại mà ta tìm thấy ở
Vậy công thức chuyển ngày thành năm của chúng ta trở thành:
Vì giá trị bằng hoặc nên khi ta cần tìm lại năm chính xác thì cần phải có bước lùi năm. Điều này có thể thực hiện dễ dàng thông qua việc so sánh với .
Tính toán tháng từ tổng số ngày trôi qua
Vì độ dài các tháng không đồng nhất, đặc biệt là tháng 2 có độ dài thay đổi tùy theo năm nhuận, nên việc xác định số ngày kể từ đầu năm trở nên phức tạp nếu chỉ dựa vào bảng tra thông thường.
Để khắc phục điều này, ta định nghĩa lại điểm bắt đầu của năm là ngày 1 tháng 3 của năm 0 (thay vì ngày 1 tháng 1), sao cho tháng 1 và tháng 2 của năm kế tiếp được xem như phần cuối của năm hiện tại.
month_index | Tháng | Số ngày trong tháng | day_index |
|---|---|---|---|
0 | 3 | 31 | 0 |
1 | 4 | 30 | 31 |
2 | 5 | 31 | 61 |
3 | 6 | 30 | 92 |
4 | 7 | 31 | 122 |
5 | 8 | 31 | 153 |
6 | 9 | 30 | 184 |
7 | 10 | 31 | 214 |
8 | 11 | 30 | 245 |
9 | 12 | 31 | 275 |
10 | 1 | 31 | 306 |
11 | 2 | 28 hoặc 29 | 337 |
Định nghĩa:
month_index là chỉ số tháng bắt đầu từ tháng 3.
day_index là chỉ số ngày thể hiện số ngày đã trôi qua kể từ tháng 3.
Việc đánh số tháng bắt đầu từ tháng 3 mang lại một ưu điểm nổi bật đó là ngày nhuận luôn được thêm vào cuối năm (month_index=11), nhờ đó, vị trí bắt đầu của các tháng còn lại không bị thay đổi giữa năm thường và năm nhuận.
Nhờ đặc tính này, ta có thể ánh xạ giữa chỉ số tháng và vị trí ngày mà không cần phải lo đến việc xử lý ngoại lệ riêng cho năm nhuận.
Ta có tổng số ngày từ tháng 3 đến tháng 12 là 306 ngày. Tức cứ sau mỗi 10 bước, ta đã dịch chuyển đúng 306 ngày. Nói cách khác, “trung bình” cứ mỗi 1 bước tăng thì số ngày dời đi khoảng ngày.
Ta muốn một công thức nào đó có thể cho kết quả nguyên chính xác bằng “tổng số ngày đã trôi qua kể từ đầu tháng 3 của năm đó” khi là một số nguyên 0, 1, 2, … Cụ thể
Với (tháng 3)
Với (tháng 4)
Với (tháng 5)
…
Với (tháng 1)
Qua đó, ta có thể tính số ngày kể từ đầu năm (ngày 1 tháng 3 được coi là ngày 0) của ngày mùng 1 của tháng đó bằng phần nguyên của hàm:
Ngược lại, cho trước hệ số ngày day_index tính từ đầu năm (bắt đầu từ month_index = 0), ta muốn tìm chỉ số tháng month_index, ta có:
Vì month_index là số nguyên nên để luôn trả về kết quả đúng thì ta sẽ lấy vế phải, điều này cho ta:
Tháng 1 và tháng 2 ( và ) sẽ được xem như là năm trước theo thuật toán
Trong lịch Gregorian, ngày 1 tháng 3 của năm 0 thực chất rơi vào thứ Tư (có thể kiểm tra sử dụng thuật toán Zeller’s Congruence).
Mã giải (C++)
#define ll long long
struct date {
ll d, m, y; // Lưu ngày, tháng, năm
date() : d(0), m(0), y(0) {}
date(ll a, ll b, ll c) : d(a), m(b), y(c) {} // Constructor
friend ostream& operator << (ostream& out, const date& x) { // in nhanh
return out << x.d << ' ' << x.m << ' ' << x.y;
}
};
ll gregorian(ll y) {
return y * 365 + y / 4 - y / 100 + y / 400; // (1)
}
ll reversedGregorian(ll D) {
return (10000 * D + 14775) / 3652425; // (6)
}
int getDayIndex(int month_index) {
return (306 * month_index + 5) / 10; // (7)
}
int getMonthIndex(int day_index) {
return (10 * day_index + 5) / 306; // (8)
}
// Chuyển đổi lịch sang tổng số ngày tính từ 1/3/0
ll toDays(date x) {
// Chuyển tháng hiện tại (1-12) sang month_index (0-11), với tháng 3 là 0
int month_index = (x.m + 9) % 12;
// Tháng 1 và tháng 2 (month_index = 10 hoặc 11) theo thuật toán sẽ là của năm trước
int adjusted_y = x.y - month_index / 10;
// Tổng số ngày = số ngày kể từ 1/1/0 đến 1/1/adjusted_y
// + số ngày kể từ tháng 3 đến month_index
// + số ngày trong tháng hiện tại - 1 (vì ngày đầu tiên trong tháng là 1 nhưng trong tính toán là 0)
return gregorian(adjusted_y) + getDayIndex(month_index) + (x.d - 1);
}
// Chuyển đổi tổng số ngày từ 1/1/0 đến 1/1/y sang lịch
date toDate(ll D) {
ll yyyy = reversedGregorian(D);
ll day_index = D - gregorian(yyyy);
// Nếu day_index < 0, tức là chúng ta đang ở năm trước, cần giảm y đi 1 và tính lại day_index.
if(day_index < 0) yyyy--, day_index = D - gregorian(yyyy);
int month_index = getMonthIndex(day_index);
int mm = (month_index + 2) % 12 + 1;
int dd = day_index - getDayIndex(month_index) + 1;
yyyy += month_index / 10;
return { dd, mm, yyyy };
}Độ phức tạp của các thao tác tính toán trên tổng thể chỉ mất , do đó rất hiệu quả và đấm AC được bài toán đặt vấn đề orz
Ứng dụng
In ra sự khác biệt giữa hai (d, m, y)
date lich1(d1, m1, y1);
date lich2(d2, m2, y2);
cout << abs(toDays(lich1) - toDays(lich2));(d, m, y) sau khi tăng / giảm x ngày
date lich(d, m, y);
cout << toDate(toDays(lich) + x); // toDate(toDays(lich) - x);Kiểm tra ngày hợp lý
date lich(d, m, y);
date check = toDate(toDays(lich));
cout << ((d == check.d && m == check.m && y == check.y) ? "ok" : "no");In ra thứ của ngày
string day[7] = { "Wednesday", "Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday" };
date lich(d, m, y);
cout << day[(toDays(lich)) % 7]; // ngày 1 tháng 3 năm 0 là thứ 4Tips xử lý DDMMYYYY
// xuất nhanh DDMMYYYY
printf("%02lld/%02lld/%04lld\n", d, m, y);// (d,m,y) -> DDMMYYYY string
char buf[20];
sprintf(buf, "%02lld%02lld%04lld", date.d, date.m, date.y);
string s = buf;Tính chất thú vị: Nếu một ngày (DD/MM/YYYY) được xếp thành ab/cd/YYYY, để nó là một ngày palindrome thì ngày đó phải có dạng ab/cd/dcba (a b c d d c b a) 🧐
Bài tập rèn luyện
https://www.spoj.com/problems/CODEIT03
https://www.spoj.com/problems/NXTDAY
https://www.spoj.com/problems/MOZSATDOW
https://www.spoj.com/SHORTEN/problems/GREGCAL/
https://www.spoj.com/problems/TEASTER/
https://www.hackerrank.com/contests/iiti-league-contest-2/challenges/days-shift/problem
https://codeforces.com/contest/304/problem/B
https://marisaoj.com/problem/531
https://onlinejudge.org/external/8/p893.pdf
https://lqdoj.edu.vn/problem/semester
https://oj.vnoi.info/problem/coci1920_r6_datum