Đồng hồ báo thức
Đề bài
Mùa hè đến là lúc học sinh được nghỉ học, là khoảng thời gian tuyệt vời để vui chơi thỏa thích cùng nhau. Thế nhưng Huy – một học sinh lớp 10 chuyên Toán lại muốn tận dụng những ngày hè rảnh rỗi để "tu luyện" nhằm đạt kết quả cao trong kỳ thi VMO sắp tới. Cậu ta đặt ra một thời gian biểu cho mình và sử dụng đồng hồ báo thức để thực hiện một cách hợp lý. Sau một hồi lục lọi quanh nhà, cậu đã tìm được một chiếc đồng hồ báo thức hiển thị bằng đèn LED mà ba cậu mua cho từ năm ngoái. Không may, do ít sử dụng mà chiếc đồng hồ đã bị hỏng về phần hiển thị giờ. Nó hỏng đến nỗi cậu không thể đọc được thời gian trên đồng hồ mà chỉ đếm được số vạch LED mà nó hiển thị. Vì vậy, để xác định thời gian, cậu phải tìm một thời điểm mà đồng hồ hiện thị có số vạch LED bằng số vạch mà cậu đếm được. Do bận ôn thi, cậu không có thời gian suy nghĩ. Đây chính là lúc các NTU Coder giúp Huy đấy!
Input
- Số nguyên $n$ ($0 \le n \le 30$) là số vạch LED mà Huy đếm được.
Output
- In ra 5 kí tự theo định dạng hh:mm là thời điểm mà đồng hồ hiển thị có số vạch LED bằng $n$, trong đó hh là giờ và mm là phút ($0 \le hh < 24$, $0 \le mm < 60$).
- Nếu có nhiều kết quả in ra kết quả có thời gian nhỏ nhất.
- Nếu không tìm được in ra Impossible.
2300:02Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTrước tiên: ngưỡng an toàn để không bị TLE
Trước khi đi vào vấn đề chính của bài thì mình muốn các bạn phải đảm bảo biết qua điều này để về sau các bạn xem mới hiểu.
Với các hệ thống web chấm bài giới hạn thời gian chạy của bài tối đa chỉ được 1 giây thì các bạn sẽ rất dễ bị rơi vào lỗi Time Limit Exceeded (TLE: chạy quá giới hạn thời gian cho phép). Thì như mình đã nói rất nhiều lần là với các hệ thống web chấm bài hiện nay nếu không muốn bị TLE thì tối đa số phép toán trên toàn bài của các bạn chỉ nên ở ngưỡng $(3 \div 5) \times 10^7$ là ngưỡng an toàn với phần lớn hệ thống chấm bài, hoặc với một số hệ thống chấm server mạnh hơn thì có thể nâng ngưỡng lên $10^8$ nhưng cũng hên xui nhé.
Và thực ra ta không phải đếm chi tiết từng số phép toán trên toàn bài mà ta dựa theo số lần vòng lặp chạy, bởi bên trong vòng lặp là nó xử lý lặp đi lặp lại nhiều phép toán nên cứ canh theo đó. Các bạn cứ hiểu là tối đa toàn bài chỉ nên lặp $(3 \div 5) \times 10^7$ lần là an toàn, hoặc tệ nhất là $10^8$ (lúc này thì hên xui nhé), còn vượt ngưỡng này là khả năng TLE rất cao nhe.
- An toàn: khoảng $(3 \div 5) \times 10^7$ lần lặp.
- Hên xui: khoảng $10^8$ lần lặp.
- Vượt ngưỡng trên: khả năng TLE rất cao.
Ngưỡng này là với ngôn ngữ C/C++ thôi nhé, chứ nếu với những ngôn ngữ khác như Python, C# hay Java nó chạy chậm hơn C/C++ thì ngưỡng đó phải thấp hơn, hoặc người ra đề sẽ chủ động đưa ra giới hạn, ví dụ nộp với C/C++ thì thời gian chạy tối đa 1 giây, các ngôn ngữ khác thì 2 giây. Nếu đề cho thời gian 2 giây thì các bạn cứ tỷ lệ thuận nhân 2 lên với ngưỡng, 3 giây thì nhân 3, nếu 100 ms tức là 1/10 giây thì các bạn chia 10 cho ngưỡng đó nhé, cứ thế thôi.
Rồi thì như bài này đưa ra thời gian chạy giới hạn là 1 giây nên cứ như ở trên mình đã nói nhé. Giờ ta đi phân tích cách giải quyết cho bài này.
2 kinh nghiệm trước khi bắt tay vào code
- Ước lượng trước, cài đặt sau. Với công thức về ngưỡng giới hạn thời gian để không bị TLE như mình nói ở trên, thì khi các bạn có ý tưởng để giải quyết thì khoan hãy đi cài đặt mà hãy thử đánh giá độ phức tạp của cách làm đó, tính thử xem số lần lặp cả thảy của cách làm đó là bao nhiêu? Có bị vượt ngưỡng không? Nếu nhắm ổn thì từ đó hãy đi cài đặt, còn nếu thấy không ổn thì thôi đừng mất công cài đặt nhé vì cài đặt cũng sẽ không AC (Accepted) được đâu. Trừ khi là đúng test nào có điểm test đó mà bạn không thể nghĩ ra cách nào tốt hơn thì mới đành phải đi cài đặt để ráng vét được điểm nào hay điểm đó thôi.
- Thử cách cơ bản nhất trước. Đứng trước mọi bài đầu tiên hãy nhìn theo cách làm cơ bản nhất của nó, cách mà có thể gọi là vét cạn hay duyệt trâu đấy 🤪. Thử nhẩm độ phức tạp của nó rồi ước tính xem có AC được không? Nếu có thể được thì cài đặt đúng theo nó để nhanh gọn code xong vấn đề, vì ngoài việc giải quyết thành công thì nếu đang trong cuộc thi có tính thời gian thì yếu tố giải càng nhanh sẽ là một lợi thế. Vì thế ta không nên mất thời gian và nặng đầu suy nghĩ ra các cách tối ưu hơn làm gì, trong khi đó cách dễ nhất và nhanh nhất để code cũng AC được, tội gì phải nặng đầu suy nghĩ cách tối ưu thì cũng vẫn AC thôi (nếu cài đặt đúng nhé) nhưng có thể mất thêm của mình thời gian mà còn chưa chắc, lỡ xui cài đặt sai chỗ nào là toang. Còn tất nhiên nếu ngữ cảnh không bị áp lực thời gian thì càng suy nghĩ ra những cách tối ưu đó là điều tốt giúp rèn luyện tư duy.
Ý tưởng: vét cạn mọi khung giờ
Quay lại bài này, thì nếu là mình mà đang trong cuộc thi có tính thời gian, thì mình sẽ làm theo cách cơ bản nhất để nhìn ra đó là vét cạn: xét tất cả mọi khung giờ có thể từ 00:00 đến 23:59 và với từng khung giờ tính xem khung giờ đó tổng cộng có bao nhiêu vạch LED, nếu bằng $n$ thì in ra kết quả khung giờ đó và kết thúc chương trình. Nếu khác $n$ thì xét qua khung giờ tiếp theo (ví dụ hiện tại đang là 00:00 thì xét tiếp qua 00:01, hiện tại đang là 01:59 thì xét tiếp qua 02:00), và nếu xét đến tận cùng tức là khung giờ 23:59 mà vẫn không tìm được số vạch LED bằng $n$ thì kết thúc lúc này in ra Impossible. Vì ta xét tăng dần từ 00:00 nên khung giờ đầu tiên tìm được chắc chắn là thời gian nhỏ nhất như đề yêu cầu.
Ta hãy thử nhẩm xem cách làm ở trên cần xét qua cả thảy bao nhiêu trường hợp? Từ 00:00 đến 23:59 nghĩa là mỗi giờ xét 60 trường hợp phút từ 0 đến 59 và ta đi xét tổng cộng 24 trường hợp giờ như vậy từ 0 đến 23. Như thế số lần xét cả thảy sẽ là:
Rồi mỗi trường hợp cần đếm xem có bao nhiêu vạch LED thì cái đó đơn giản xét điều kiện thôi chứ không cần lặp gì cả. Như thế cả thảy chỉ cần lặp qua 1440 trường hợp, và với giới hạn 1 giây đề cho thì ngưỡng giới hạn là 30 triệu đến 50 triệu hay cao lắm là 100 triệu nếu không muốn bị TLE. Ở đây ta vét cạn mà cũng chỉ tầm 1 nghìn rưỡi thì quá nhỏ so với giới hạn nên yên tâm cách làm này sẽ không bị TLE, ta có thể đi cài đặt theo cách này.
Duyệt khung giờ gọn gàng với 2 biến h, m
Vậy nếu đã nhìn ra tư tưởng này rồi nhưng nếu không xử lý khéo thì nhiều bạn cũng sẽ code phức tạp lắm và có thể bị sai. Ví dụ bạn nào mà đi tạo đủ 4 biến h1, h2, m1, m2 ứng với h1h2:m1m2 (ví dụ 01:23 nghĩa là h1 = 0, h2 = 1, m1 = 2, m2 = 3) rồi xử lý trên cả 4 biến này thì cũng được đó, nhưng lúc này xử lý quy luật nó theo mình thấy thì sẽ rườm rà lắm đây. Nào là khởi tạo tất cả ban đầu là 0, rồi m2 tăng lên mỗi lần 1 đơn vị, nếu m2 là 10 thì reset lại thành 0 rồi tăng m1 lên 1 đơn vị, nếu m1 là 6 thì reset m1 về 0 và tăng h2 lên 1 đơn vị, rồi nếu h1 đang là 0 hay 1 và h2 cứ tăng lên đến 10 thì reset h2 về 0 rồi tăng h1 lên 1 đơn vị, nếu h1 đang là 2 và h2 cứ tăng lên đến 4 thì khi đó kết thúc. Nói chung khá rườm rà khi phải quản lý đồng thời cả 4 biến như vậy. Ở trên mình chỉ mới phân tích bằng lời còn thấy rườm rà, nếu mà cài đặt code còn rối cỡ nào nữa 🤪
Theo mình để đơn giản chỉ cần tạo 2 biến h, m với h là giờ và m là phút. Ban đầu 2 biến h, m khởi tạo tất cả là 0. Điều kiện vòng lặp là h < 24, rồi cứ thế bên trong vòng lặp ta cho m++ rồi xét nếu m bằng 60 thì reset m về 0 và cho h++. Rồi khi nào mà h++ lên thành 24 thì vi phạm điều kiện vòng lặp nên vòng lặp sẽ dừng lại.
Với mỗi giá trị h, m hợp lệ trong vòng lặp ta có thể đi tính ra được khung giờ đó sẽ có số vạch LED là bao nhiêu? Giả sử h hay m đang là 15 chẳng hạn thì việc tách ra được số 1 và số 5 quá đơn giản, cứ / 10 và % 10 là lấy được thôi (15 / 10 = 1, 15 % 10 = 5). Hay nếu là 7 chẳng hạn thì 7 / 10 = 0, 7 % 10 = 7.
Đếm vạch LED bằng mảng 10 phần tử
Còn việc đi tính ra số vạch LED của từng chữ số tương ứng, ví dụ 1 hay 5 thì 1 là có 2 vạch LED, 5 là có 5 vạch LED. Chỗ này nếu bạn nào mà đi xét 10 cái if else thì rất dài dòng, thậm chí bạn nào mà không chia hàm ra mà code hết trong hàm main thì 10 cái if else đó bị lặp lại 4 lần thành ra cả bài có thể đến 40 cái if else (gọi là if else đến chết đấy 🤣). Nhìn rất phức tạp.
Trong khi đó sẽ rất gọn nếu ngay từ đầu ta tạo ra mảng a có 10 phần tử với index từ 0 đến 9 cũng trùng khớp với chữ số từ 0 đến 9, và như thế a[i] chính là số lượng vạch LED của chữ số $i$:
int a[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};Như thế khi với khung thời gian h:m ta muốn biết được có bao nhiêu vạch LED thì chỉ đơn giản là:
Rất đơn giản không cần xét if else gì cả. Các bạn thấy hay chưa? Dùng cái mảng 10 phần tử là đơn giản hoá vấn đề ngay. Ví dụ với test của đề $n = 23$, khung giờ đầu tiên có đúng 23 vạch LED là 00:02:
Em nhập số vạch LED $n$ đếm được rồi bấm Tiếp để xem cách vét cạn dò từ 00:00 trở đi. Để đỡ phải bấm 1440 lần, các giờ (hoặc khối 10 phút) chắc chắn không có đáp án sẽ được bỏ qua trong 1 bước:
In đúng định dạng hh:mm
Rồi giả sử khi xác định được khung giờ h:m là đáp án thì ta phải in ra theo đúng định dạng hh:mm, nghĩa là luôn đảm bảo đủ 2 chữ số cho h và m. Giả sử h đang là 5, m đang là 7 thì phải in ra: 05:07, tức là nếu không đủ 2 chữ số thì in ra thêm số 0 đằng trước cho đủ. Còn nếu đủ 2 chữ số thì cứ in ra thôi, ví dụ h = 13, m = 50 thì in ra: 13:50.
Thì chỗ này nếu bạn nào không biết thì cũng phải code if else để xét. Nhưng nếu bạn nào rành code bên C thì sẽ biết câu lệnh printf có hỗ trợ cho ta xuất ra với định dạng %02d, nghĩa là in ra giá trị số đó có đủ 2 chữ số, nếu không đủ thì in ra các số 0 bù thêm vào đằng trước. Vấn đề giờ đây được giải quyết rất đơn giản:
// Theo kiểu C:
printf("%02d:%02d", h, m);
// Theo kiểu C++:
cout << setw(2) << setfill('0') << h << ":" << setw(2) << setfill('0') << m;Source code
Source code để các bạn tham khảo hiểu rõ hơn ý tưởng xử lý mình mô tả ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int a[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int h = 0, m = 0;
while(h < 24){
if(a[h / 10] + a[h % 10] + a[m / 10] + a[m % 10] == n){
printf("%02d:%02d", h, m);
// cout << setw(2) << setfill('0') << h << ":" << setw(2) << setfill('0') << m;
return 0;
}
m++;
if(m == 60){
m = 0;
h++;
}
}
cout << "Impossible";
return 0;
}n = int(input())
a = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
h, m = 0, 0
while h < 24:
if a[h // 10] + a[h % 10] + a[m // 10] + a[m % 10] == n:
print(f"{h:02d}:{m:02d}")
exit()
m += 1
if m == 60:
m = 0
h += 1
print("Impossible")Đánh giá độ phức tạp
- Độ phức tạp không gian (Space Complexity): có thể xem là độ phức tạp hằng số $O(1)$, vì mảng 10 phần tử cũng chỉ là hằng số cố định thôi chẳng bao nhiêu cả.
- Độ phức tạp thời gian (Time Complexity): $O(H \times M)$ với $H$ tối đa 24, $M$ tối đa 60. Trong trường hợp xấu nhất khi phải lặp đến tận cùng và kết luận Impossible thì số lần lặp cũng chỉ là $24 \times 60 = 1440$, cũng rất nhanh gọn để ra đáp án, không sợ bị TLE.
Nhận xét
Đăng nhận xét