Sách Cũ
Đề bài
Trong một cuốn sách cổ có ghi lại rất nhiều các con số bí ẩn mà chúng có mối liên hệ với 30. Sau một thời gian nghiên cứu, các chuyên gia đã tìm được cách giải mã các số đó: hoán vị các chữ số của số bí ẩn đó để thu được một số là bội số lớn nhất của 30.
Yêu cầu: hãy viết chương trình giúp các chuyên gia giải mã các con số bí ẩn đó.
Dữ liệu nhập: gồm một số nguyên dương $N$ duy nhất.
Kết quả: in ra một số duy nhất là kết quả tìm được. Nếu không giải mã được hãy in $-1$.
Ràng buộc
- 50% test: $1 \le N \le 10^9$.
- 50% test: $N$ có tối đa $2 \cdot 10^7$ chữ số.
1002210012498567-1100-1Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 🥰. Chúc các bạn học tốt và gặt hái nhiều thành công.
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 CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
50%Tư tưởng vét cạn: thử mọi hoán vị
Một tư tưởng vét cạn cho bài này là xét qua tất cả các hoán vị có thể có, với mỗi hoán vị ta kiểm tra xem nó có chia hết cho 30 không (nói 30 là bội số nghĩa là số đó chia hết cho 30, vì các bội số của 30 là 30, 60, 90, 120, 150… cứ lấy 30 nhân lần lượt 1, 2, 3, 4…). Nếu thoả mãn thì so sánh với Max, lớn hơn thì cập nhật lại. Sau cùng Max chính là kết quả.
Ví dụ với $N = 1002$, liệt kê hết các hoán vị khác nhau và kiểm tra:
| Hoán vị | Tổng chữ số (chia hết 3?) | Chữ số cuối (= 0?) | Kết luận |
|---|---|---|---|
| 2100 | 3 ✔ | 0 ✔ | ✔ bội của 30 ← lớn nhất |
| 2010 | 3 ✔ | 0 ✔ | ✔ bội của 30 |
| 2001 | 3 ✔ | 1 ✘ | ✘ |
| 1200 | 3 ✔ | 0 ✔ | ✔ bội của 30 |
| 1020 | 3 ✔ | 0 ✔ | ✔ bội của 30 |
| 1002 | 3 ✔ | 2 ✘ | ✘ |
| 0210 | 3 ✔ | 0 ✔ | ✔ bội của 30 |
| 0201 | 3 ✔ | 1 ✘ | ✘ |
| 0120 | 3 ✔ | 0 ✔ | ✔ bội của 30 |
| 0102 | 3 ✔ | 2 ✘ | ✘ |
| 0021 | 3 ✔ | 1 ✘ | ✘ |
| 0012 | 3 ✔ | 2 ✘ | ✘ |
Nếu làm theo tư tưởng này, với $N$ là độ dài thì cả thảy sẽ có $N \cdot N!$ thao tác. Trong 50% test đầu, độ dài tối đa 9 chữ số thì $9 \cdot 9! = 3\,265\,920$, vẫn ổn vì chưa vượt ngưỡng tiêu chuẩn 1 giây là khoảng $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$. Tuy nhiên với 50% test cuối, độ dài có thể lên tới hàng chục triệu chữ số thì $N!$ là con số cực kỳ cực kỳ lớn, không thể xét hết nổi. Nên cách này rất tệ, bạn nào không nghĩ ra cách tối ưu hơn thì mới làm theo để ráng vớt vát 50% điểm.
Để liệt kê hoán vị, bạn có thể tự viết theo bài liệt kê các hoán vị từ 1 đến $N$: ví dụ số 385 có 3 chữ số, liệt kê các hoán vị của {1, 2, 3} là {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}; vị trí 1 ứng với chữ số 3, vị trí 2 ứng với 8, vị trí 3 ứng với 5, ta có 6 số 385, 358, 835, 853, 538, 583. Hoặc trong C++ có sẵn hàm next_permutation để liệt kê các hoán vị.
Toán họcKhi nào một số chia hết cho 30?
Ta cần vận dụng kiến thức toán học và tư tưởng tham lam là giải quyết gọn bài này. Đem phân tích 30 thành tích các thừa số nguyên tố: $30 = 2 \cdot 3 \cdot 5$. Gom nhóm $2 \cdot 5 = 10$ thì $30 = 10 \cdot 3$.
② Chia hết cho 3: tổng các chữ số phải chia hết cho 3.
Chỉ cần không thoả 1 trong 2 điều kiện thì số đó không phải bội của 30. Các bạn cứ thử lấy 30 nhân với nhiều số khác nhau ghi ra giấy là sẽ thấy ngay quy luật này. Một điều rất hay: hoán vị các chữ số không làm thay đổi tổng các chữ số, nên điều kiện ② chỉ cần kiểm tra 1 lần cho số ban đầu!
Tham lamSố lớn nhất: xếp chữ số giảm dần
Tham lam nghĩa là ở mỗi bước ta chọn cách tốt nhất trong các lựa chọn hiện tại, rồi cứ thế đi tiếp theo hướng tốt nhất. Không có công thức từng bước cụ thể như các thuật toán khác, miễn tư tưởng luôn chọn theo hướng tốt nhất. Đọc đề thấy "sau cùng đáp án phải lớn nhất/nhỏ nhất" là thấy mùi tham lam ngay 😄.
Một số muốn lớn nhất thì đưa các chữ số lớn nhất về đầu, các chữ số nhỏ nhất về cuối, tức là sắp xếp các chữ số giảm dần. Ví dụ có đủ 10 chữ số 0 đến 9 thì số lớn nhất là 9876543210. Và thật trùng hợp: xếp giảm dần thì chữ số 0 (nếu có) tự động nằm ở cuối cùng, đúng điều kiện ①!
Vì số có thể dài tới hàng chục triệu chữ số, kiểu số nguyên lớn nhất của C/C++ (8 byte) cũng chỉ chứa khoảng 19, 20 chữ số, nên bắt buộc dùng chuỗi để lưu. Nhờ chuỗi mà ta truy xuất được từng chữ số qua chỉ số index, rất tiện.
100%Mảng đánh dấu (đếm chữ số) – O(N)
Hợp lý nhất là dùng kỹ thuật mảng đánh dấu để thống kê tần suất xuất hiện của từng chữ số. Tạo mảng $a$ có 10 phần tử, index 0 đến 9 trùng khớp với các chữ số 0 đến 9: a[i] là số lần xuất hiện của chữ số $i$, ban đầu tất cả bằng 0. Xét từng ký tự s[i], đổi sang số bằng cách trừ 48 (ký tự '0' có mã ASCII 48, '1' là 49…, nên '1' − 48 = 1), rồi a[x]++, đồng thời cộng dồn vào sum.
Sau cùng: nếu a[0] == 0 (không có chữ số 0) hoặc sum không chia hết cho 3 thì in $-1$. Ngược lại in ra a[i] lần chữ số $i$ với $i$ chạy từ 9 về 0, như thế chữ số cuối cùng chắc chắn là 0.
Em tự chạy thử từng bước dưới đây nhé, gõ số bất kỳ (tối đa 40 chữ số) vào ô N:
Mỗi lần truy xuất mảng đánh dấu chỉ tốn $O(1)$. Nếu dùng map thì mỗi lần tìm tốn $O(\log N)$ do map cài đặt bằng cây đỏ đen, rất có khả năng vẫn TLE. Còn unordered_map (bảng băm) tốt nhất là $O(1)$ nhưng khi hàm băm không tốt có thể tới $O(N)$, rất nguy hiểm. Tối ưu nhất vẫn là mảng đánh dấu.
Source code cho tư tưởng trình bày ở trên để các bạn tham khảo:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
int a[10] = {0}, sum = 0;
for(int i = 0; i < (int)s.length(); ++i){
int x = s[i] - 48;
a[x]++;
sum += x;
}
if(a[0] == 0 || sum % 3 != 0){
cout << -1;
}
else{
for(int i = 9; i >= 0; --i){
while(a[i]--){
cout << i;
}
}
}
return 0;
}s = input().strip()
a = [0] * 10
total = 0
for ch in s:
x = ord(ch) - 48
a[x] += 1
total += x
if a[0] == 0 or total % 3 != 0:
print(-1)
else:
print(''.join(str(i) * a[i] for i in range(9, -1, -1)))Giải thích một số chỗ trong code
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 kinh nghiệm trong các bài cần nhập xuất nhiều, như bài này chuỗi đầu vào rất dài và bước cuối có thể phải xuất ra từng ấy ký tự, ta hãy nên để 2 dòng này vào để 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é. Các bạn có thể thử cùng đoạn code như trên nhưng bỏ đi 2 dòng đó, bảo đảm sẽ bị TLE với thời gian chạy gần 1100 ms, trong khi thêm 2 dòng đó vào thì chỉ còn tầm 900 ms và AC.while(a[i]--){ cout << i; }nghĩa là xuất ra đủa[i]lần giá trị $i$. Viết đầy đủ sẽ hiểu là: liên tục giảma[i]đến khi về 0 thì dừng, mỗi lần lặp in ra chữ số $i$. Ban đầua[i]là 3 thì vòng lặp lặp đủ 3 lần.
Không gian $O(1)$ vì mảng $a$ chỉ có 10 phần tử, xem như không đáng kể. Thời gian là $O(N)$ cho bước xét từng ký tự cộng $O(N)$ cho bước xuất đáp án, tổng $O(2N)$, theo quy tắc BigO nhân hằng số thì vẫn là $O(N)$. Trường hợp xấu nhất lặp cả thảy $2 \cdot 10^7$ lần, cũng tiệm cận ngưỡng 1 giây, nên không ngạc nhiên khi chạy lên tới 900 ms, thậm chí nộp nhiều lần có lúc bị TLE nếu máy chấm đang bận.
Nhanh gấp 3Tối ưu cách xuất: gom chuỗi theo từng chữ số
Trong bảng chấm bài này có những code Accepted chỉ tầm 250 – 300 ms, trong khi phần lớn ở ngưỡng 900 ms như code trên. Vậy có cách làm khác tối ưu hơn? Theo mình là không, $O(N)$ là tối ưu nhất rồi. Muốn nhanh hơn thì phải xem lại cách cài đặt có chỗ nào rườm rà.
Vấn đề nằm ở chỗ: chuỗi dài $10^7$ thì lệnh cout << bị gọi tới $10^7$ lần. Có cách nào giảm số lần gọi không? Đây là mấu chốt!
a[2] = "2222222222", sau cùng chỉ cần 1 lệnh cout << a[2] thay vì 10 lệnh. Cả bài chỉ còn đúng 10 lệnh xuất!#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s, a[10];
cin >> s;
int sum = 0;
for(int i = 0; i < (int)s.length(); ++i){
int x = s[i] - 48;
a[x].push_back(s[i]);
sum += x;
}
if(a[0] == "" || sum % 3 != 0){
cout << -1;
}
else{
for(int i = 9; i >= 0; --i){
cout << a[i];
}
}
return 0;
}import sys
s = sys.stdin.readline().strip()
cnt = [s.count(str(d)) for d in range(10)] # đếm từng chữ số (chạy bằng C bên trong nên rất nhanh)
total = sum(d * cnt[d] for d in range(10))
if cnt[0] == 0 or total % 3 != 0:
print(-1)
else:
sys.stdout.write(''.join(str(d) * cnt[d] for d in range(9, -1, -1)) + '\n')Mảng $a$ giờ là mảng string. Gặp ký tự nào thì push_back thêm vào cuối chuỗi tương ứng, thêm vào cuối nên chỉ $O(1)$. Sau cùng nếu a[0] vẫn là chuỗi rỗng (không có số 0 nào) hoặc sum không chia hết cho 3 thì in $-1$, ngược lại xuất a[9] về a[0].
Độ phức tạp tổng quát vẫn là $O(N)$, nhưng khúc sau chỉ cần lặp 10 lần thay vì thêm $N$ lần, và cout không bị gọi quá nhiều. Nhờ vậy thời gian chạy dưới 300 ms, nhanh gấp cả 3 lần cách trước đó.
s.count() để đếm từng chữ số rất nhanh và nối chuỗi một lần). Tất cả các bản đã được kiểm tra với 300 số ngẫu nhiên so với cách vét cạn mọi hoán vị; với số dài $2 \cdot 10^7$ chữ số, bản C++ chạy khoảng 0.1 giây trên máy mình, bản Python khoảng 0.4 giây.