Đồng hồ số
Đề bài
Sắn có thiết bị điện tử mới nhất có màn hình. Các chữ số khác nhau có thể được hiển thị trên đó. Mỗi chữ số được hiển thị trên một chỉ báo bảy phần giống như nó được hiển thị trên hình dưới đây.
Vì vậy, ví dụ, để hiển thị chữ số 3 trên màn hình, 5 phần phải được tô sáng; và đối với chữ số 6, 6 phần phải được tô sáng. Pin của thiết bị mới nhất cho phép làm nổi bật đúng $n$ phần trên màn hình.
Sắn muốn biết số nguyên lớn nhất có thể được hiển thị trên màn hình của thiết bị mới nhất của mình. Nhiệm vụ của bạn là xác định con số này. Lưu ý rằng số này không được chứa các số 0 đứng đầu. Giả sử rằng kích thước của màn hình là đủ để hiển thị bất kỳ số nguyên nào.
Dữ liệu nhập
- Dòng đầu tiên chứa số nguyên $n$ ($2 \le n \le 10^6$) – số phần tối đa có thể được tô sáng trên màn hình.
Kết quả
- In số nguyên tối đa có thể được hiển thị trên màn hình của thiết bị mới nhất của Sắn.
Subtask
- 50% số test đầu tiên có $n \le 10^3$.
- 50% số test còn lại có $n \le 10^6$.
2137Lờ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 CodeforcesTư tưởng tham lam
Rồi thì bài này dùng phương pháp tham lam để xử lý thôi. Kể cả bạn nào có không biết về phương pháp tham lam này thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết. Cho bạn nào không biết thì mình có thể nói nhanh như thế này: tham lam ở đây nghĩa là ta sẽ cố gắng chọn ra cách giải quyết tốt nhất trong tất cả các cách ở hiện tại rồi đi theo cách giải quyết tốt nhất đó; nếu lại đứng trước nhiều lựa chọn cách giải quyết khác nhau nữa thì ta lại cố gắng chọn theo cách giải quyết tốt nhất trong số đó; tóm lại cứ tốt nhất mà triển, vì thế tên gọi nó là tham lam. Quy luật nó là như vậy thôi chứ còn lại không có công thức từng bước cụ thể giải quyết như mấy thuật toán khác. Mà ta có thể giải quyết theo cách bất kỳ, miễn cái tư tưởng mà ta giải quyết luôn là chọn theo hướng tốt nhất trong các lựa chọn thì đó chính là tư tưởng của tham lam. Thì tại sao bài này lại có thể nhìn ra tư tưởng của nó là tham lam? Đọc đề bài là thấy rõ mùi rồi hehe, muốn xử lý theo quy luật gì gì đó để sau cùng đáp án phải là nhỏ nhất/lớn nhất các kiểu, đọc kiểu này phát thấy mùi tham lam ngay. Thì thực ra tham lam chỉ là dạng tư tưởng thôi, còn lại để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác nữa. Mình lấy ví dụ ngay trong chính bài tập này, các bạn cứ tiếp tục xem nhé.
So sánh 2 số: độ dài quan trọng nhất
Thì giả sử giữa 2 số $a$, $b$ muốn so sánh xem số nào lớn hơn, đầu tiên ta phải xét đến yếu tố chiều dài (số lượng chữ số): số nào dài hơn (nhiều chữ số hơn) thì số đó chắc chắn lớn hơn. Trong trường hợp chiều dài 2 số bằng nhau thì lúc đó mới bắt đầu đi xét từng chữ số từ trái qua phải của 2 số so sánh với nhau, nếu tại chữ số nào lớn hơn chữ số kia thì kết luận số đó lớn hơn.
Nói chung trước tiên quan trọng nhất là số lượng chữ số của mỗi số các bạn nhé, chừng nào số lượng chữ số bằng nhau thì ta mới xét đến yếu tố so sánh từng chữ số. Bởi vì ví dụ số 1000 sẽ lớn hơn 999 vì 1000 có 4 chữ số còn 999 chỉ có 3 chữ số. Trong khi đó các chữ số của 1000 chỉ là 0 với 1, còn các chữ số của 999 đều là 9, đều lớn hơn 0, 1 cả, nhưng vì 1000 có chiều dài lớn hơn nên nó là lớn hơn, quy luật này là hiển nhiên.
Thống kê số phần tô sáng của từng chữ số
Vậy ta hãy nhìn lại bài này, hãy thử thống kê số lượng các phần được tô sáng ứng với từng chữ số từ 0 đến 9: chữ số 0 cần 6 phần, 1 cần 2 phần, 2 cần 5 phần, 3 cần 5 phần, 4 cần 4 phần, 5 cần 5 phần, 6 cần 6 phần, 7 cần 3 phần, 8 cần 7 phần, 9 cần 6 phần. Hãy thử sắp xếp các phần tô sáng tăng dần, ta được:
| Số phần tô sáng | Hiển thị | Chữ số |
|---|---|---|
| 2 | 1 | |
| 3 | 7 | |
| 4 | 4 | |
| 5 | 2, 3, 5 | |
| 6 | 0, 6, 9 | |
| 7 | 8 |
Vậy ta thấy số phần tô sáng ít nhất là 2 và ứng với nó là chữ số 1; tiếp theo đó số phần tô sáng lớn hơn là 3 và ứng với nó là chữ số 7.
Lời giải: dồn hết cho chữ số 1, lẻ thì thêm chữ số 7
Vậy nếu đề cho $N$ là số phần tô sáng có thể hiển thị trên màn hình và yêu cầu ta tìm ra số nguyên lớn nhất được ghép từ các chữ số sao cho tổng các phần tô sáng của các chữ số trong số nguyên đó sẽ bằng $N$. Như ta đã phân tích ở trên, để được là số nguyên lớn nhất thì ta hãy cố gắng sao cho nó dài nhất có thể. Như trường hợp trên ta thấy chữ số 1 là cần ít phần tô sáng nhất (chỉ cần 2 phần tô sáng), vậy ta hãy chuyển hết $N$ về toàn bộ các chữ số 1 thì sẽ đảm bảo nó là dài nhất có thể. Cụ thể lúc này số lượng các chữ số 1 sẽ là $N / 2$. Ví dụ $N = 6$ thì ta hiểu sẽ có 3 số 1, tức là đáp án là số 111 là số lớn nhất.
Tuy nhiên ta thấy rằng nếu tính ra số lượng các chữ số 1 sẽ là $N / 2$ thì nếu $N$ là số chẵn thì phép chia 2 lúc nào cũng chia hết, nhưng nếu khi $N$ là số lẻ thì phép chia $N / 2$ lúc nào cũng sẽ bị dư 1 (ví dụ: $N = 5$ thì $5 / 2$ chỉ được 2 do lấy phần nguyên, như thế ta còn dư lại 1). Nói chung phần dư lúc này sẽ là N % 2, và phép chia % 2 thì kết quả hoặc là 0, hoặc là 1:
- Nếu kết quả là 0, tức là $N$ chia hết cho 2, thì đáp án sẽ là $N / 2$ số 1.
- Trong trường hợp kết quả là 1, tức là còn dư ra 1 phần tô sáng, mà ta thấy các chữ số tối thiểu phải là 2 phần tô sáng nên hiện tại dư ra 1 phần tô sáng này sẽ không thể tạo thành được chữ số nào. Giải pháp lúc này là ta sẽ mượn 2 phần tô sáng từ $N$, nghĩa là kết quả phép chia $N / 2$ sẽ bị giảm đi 1, để lúc này số phần tô sáng dư ra là 3, thì 3 phần tô sáng ứng với chữ số 7 nên ta có thể tạo ra được. Nói chung chỗ này là bớt đi 1 chữ số 1, bù vào đó là chữ số 7. Và để tạo thành số là lớn nhất nên ta sẽ ưu tiên đưa số 7 lên hàng đầu.
Ví dụ khi $N = 5$ thì $5 / 2 = 2$ và dư 1, lúc này bỏ đi 1 chữ số 1 nhưng bù vào đó ta có số 7, kết quả sẽ là 71. Ví dụ $N = 7$ thì kết quả là 711. $N = 9$ thì kết quả là 7111. Còn nếu $N$ là số chẵn, ví dụ $N = 8$ thì kết quả sẽ là 1111. Đến đây các bạn đã thấy bài này quá đơn giản rồi hen.
| N | Cách ghép | Màn hình | Kết quả |
|---|---|---|---|
| 2 | 1 × "1" | 1 | |
| 3 | "7" | 7 | |
| 4 | 2 × "1" | 11 | |
| 5 | "7" + 1 × "1" | 71 | |
| 6 | 3 × "1" | 111 | |
| 7 | "7" + 2 × "1" | 711 | |
| 8 | 4 × "1" | 1111 | |
| 9 | "7" + 3 × "1" | 7111 | |
| 10 | 5 × "1" | 11111 |
Em nhập số vạch $n$ rồi bấm Tiếp để xem từng bước "chia" vạch sáng cho các chữ số:
Source code để các bạn tham khảo tư tưởng xử lý ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int sz = n / 2;
if(n % 2 == 0){
while(sz--){
cout << 1;
}
}
else{
cout << 7;
while(--sz){
cout << 1;
}
}
return 0;
}n = int(input())
sz = n // 2
if n % 2 == 0:
print("1" * sz, end="")
else:
print("7" + "1" * (sz - 1), end="")Giải thích một số chỗ trong code ở trên:
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên 1 kinh nghiệm trong các bài mà cần nhập xuất nhiều, như trường hợp bài này ta thấy $N$ tối đa là $10^6$, vậy trong trường hợp xấu nhất ta sẽ cần xuất $N / 2$ lần, tức là xuất cả $5 \times 10^5$ lần, nên đây cũng là số lượng lớn thì ta nên để thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.while(sz--)hiểu là điều kiện vòng lặp so sánh xemszthỏa khác 0 rồi sau đószgiảm đi 1 đơn vị. Cụ thể vòng lặp này sẽ giúp lặp đủszlần. Toán tử--đặt đằng sau hiểu là hậu tố, tức là nó sẽ làm phép--sau cùng.while(--sz)hiểu là giảmszđi 1 đơn vị trước rồi sau đó mới so sánh điều kiện vòng lặp xem kết quảszsau khi trừ xong có thỏa khác 0 không? Cụ thể vòng lặp này sẽ giúp lặpsz - 1lần. Toán tử--đặt đằng trước hiểu là tiền tố, tức là nó sẽ làm phép--trước tiên.
Đánh giá độ phức tạp của cách làm này:
- Độ phức tạp không gian (Space Complexity): $O(1)$.
- Độ phức tạp thời gian (Time Complexity): $O(N / 2) \Leftrightarrow O(\frac{1}{2} \times N)$, thì nhân với hằng số ta có thể bỏ qua, vì vậy về tổng quát ta có thể kết luận độ phức tạp là $O(N)$.
Vậy trong trường hợp xấu nhất khi $N$ tối đa là $10^6$ thì thực tế vòng lặp chỉ chạy $5 \times 10^5$ lần, trong khi đó với thời gian chạy tối đa là 1 giây thì ngưỡng giới hạn là $(3 \div 5) \times 10^7$ hay cao lắm là $10^8$. Vậy nên với số lần chạy này của code hiện tại là ít hơn từ khoảng 60 đến 200 lần, vì vậy ta yên tâm chắc chắn không bị TLE. Và đây là cách tối ưu nhất, vì đáp án có tới $N / 2$ chữ số thì kiểu gì ta cũng phải in ra đủ $N / 2$ chữ số đó.
Cách viết gọn hơn với string
Mình cũng nói luôn, nếu bạn nào không thích phải code dài, vì nếu đang trong thời gian giới hạn thì code nhanh là 1 lợi thế, thì ta có thể code thế này cho gọn hơn được một chút:
Xem code cách viết gọn
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
string s(n / 2, '1');
if(n % 2 != 0){
s.pop_back();
cout << 7;
}
cout << s;
return 0;
}n = int(input())
s = "1" * (n // 2)
if n % 2 != 0:
s = s[:-1]
print("7", end="")
print(s, end="")Như các bạn thấy sẽ chẳng cần vòng lặp gì trong code này cả, vì ban đầu ta khởi tạo chuỗi s có $N / 2$ ký tự và tất cả là ký tự '1'. Bản chất lúc này đây kiểu chuỗi string đã làm bước lặp để tạo ra chuỗi cho ta rồi. Sau đó ta chỉ xét nếu $N$ là số lẻ thì sẽ xóa đi ký tự cuối cùng của chuỗi s (ta chọn xóa cuối để nó chỉ tốn $O(1)$). Sau đó ta xuất ra trước số 7. Rồi thì ra bên ngoài if sẽ xuất nốt chuỗi s. Còn trong trường hợp $N$ là số chẵn thì nó sẽ xuất ra đủ chuỗi s được khởi tạo ban đầu có $N / 2$ ký tự 1. Nói chung về độ phức tạp thì tương đương giữa 2 cách, cách này chỉ gọn hơn một chút xíu về mặt trình bày thôi.
Nhận xét
Đăng nhận xét