Số Đặc Biệt (SDB)
Đề bài
Bài 2. Số đặc biệt
Ta xem: chiều dài của một số tự nhiên là số chữ số của số đó và độ cao của một số tự nhiên là tổng các chữ số của số đó.
Yêu cầu: Cho số tự nhiên $A$, có chiều dài $N$. Hãy tìm số tự nhiên $B$ sát sau $A$ có cùng chiều dài, cùng độ cao với $A$ (có nghĩa là $B$ lớn hơn $A$, có cùng chiều dài, cùng độ cao với $A$ và không có số nào thỏa mãn giữa hai số $A$ và $B$).
Dữ liệu vào: từ tệp văn bản SDB.INP
- Dòng đầu tiên: ghi số tự nhiên $N$ – là chiều dài của số tự nhiên $A$.
- Dòng thứ hai: ghi số tự nhiên $A$.
Kết quả: ghi ra tệp SDB.OUT số $B$ tìm được. Nếu không tìm được số $B$ thì ghi ra $-1$.
Ràng buộc:
- 20% test đầu tiên ứng với $N \le 8$.
- 30% test tiếp theo ứng với $N \le 10^4$.
- 40% test tiếp theo ứng với $N \le 10^5$.
- 10% test tiếp theo ứng với $N \le 10^6$.
(Trên hệ thống chấm online thì đọc dữ liệu từ bàn phím và in ra màn hình như bình thường, không dùng tệp nhé.)
5
2399024089Lời mở đầu
Bài này đọc vào đề là biết ngay phải xử lý chuỗi nhé các bạn, bởi vì đề nói chiều dài số tối đa tới $10^6$ chữ số thì chỉ có dùng chuỗi thôi. Nếu dùng kiểu số thì long long tối đa chỉ lưu được tầm 18–19 chữ số là hết mức rồi 😅. Dù vậy, code vét cạn cho bài này vẫn lấy được 20% điểm đầu tiên, nên mình sẽ đi từ vét cạn rồi mới tới cách tối ưu.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJMình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Yêu cầu của đề: tìm số $B$ đầu tiên thỏa $B \gt A$, $B$ có số chữ số bằng số chữ số của $A$, và tổng các chữ số của $B$ bằng tổng các chữ số của $A$.
$A = 23990$ có 5 chữ số, độ cao $2 + 3 + 9 + 9 + 0 = 23$. Các số $23991, 23992, \dots$ đều có 5 chữ số nhưng độ cao khác $23$. Số đầu tiên lớn hơn $A$ có độ cao $23$ là $24089$ ($2 + 4 + 0 + 8 + 9 = 23$) – đó là đáp án. Còn nếu xét hết các số có 5 chữ số (tới $99999$) mà không có số nào thì in $-1$, ví dụ $A = 900$ hay $A = 999$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn từng số – lấy 20% điểm
Với $A = 23990$ (5 chữ số), ta bắt đầu xét từ $A + 1 = 23991$ cho tới số lớn nhất có 5 chữ số là $99999$. Toàn bộ các số trong đoạn này đều có 5 chữ số, tức là đã thỏa tiêu chí cùng chiều dài với $A$. Giờ ta chỉ cần kiểm tra tiêu chí cùng độ cao (tổng các chữ số bằng nhau): cứ xét lần lượt $23991, 23992, 23993, \dots$, số đầu tiên có tổng chữ số bằng $23$ chính là đáp án ($24089$). Xét hết mà không có thì in $-1$.
Trường hợp xấu nhất với $N \le 8$: $A$ là số nhỏ nhất có 8 chữ số, ta phải xét hết từ $10\,000\,000$ đến $99\,999\,999$, tức khoảng 90 triệu số – vẫn ít hơn ngưỡng cỡ 100 triệu phép tính nên subtask này qua được.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
// freopen("SDB.INP", "r", stdin);
// freopen("SDB.OUT", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
long long n, a;
cin >> n >> a;
long long temp_a = a;
long long sum1 = 0;
while(temp_a != 0){
sum1 += temp_a % 10;
temp_a /= 10;
}
long long sz = pow(10, n);
for(long long i = a + 1; i < sz; ++i){
long long x = i;
long long sum2 = 0;
while(x != 0){
sum2 += x % 10;
x /= 10;
}
if(sum2 == sum1){
cout << i;
return 0;
}
}
cout << -1;
return 0;
}import sys
# sys.stdin = open("SDB.INP", "r")
# sys.stdout = open("SDB.OUT", "w")
input_data = sys.stdin.read().split()
n = int(input_data[0])
a = int(input_data[1])
temp_a = a
sum1 = 0
while temp_a != 0:
sum1 += temp_a % 10
temp_a //= 10
sz = 10 ** n
for i in range(a + 1, sz):
x = i
sum2 = 0
while x != 0:
sum2 += x % 10
x //= 10
if sum2 == sum1:
print(i)
exit(0)
print(-1)SDB.INP và ghi ra SDB.OUT, nên trong code của mình có 2 dòng freopen (Python là sys.stdin = open(...)). Mình để chúng ở dạng comment vì hệ thống chấm online đọc/ghi chuẩn; khi đi thi thật thì các bạn bỏ dấu comment đi nhé.Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ vài biến, $O(1)$.
- Thời gian: xấu nhất phải xét gần $10^N$ số, mỗi số tách $N$ chữ số: $O(10^N \cdot N)$. Chỉ dùng được cho $N \le 8$.
long long (tràn số, và pow(10, n) cũng tràn), chưa kể số vòng lặp là khổng lồ. Theo kinh nghiệm của mình khi nộp: code C++ chỉ được 23/101 test, còn code Python lại được 41/101 test – vì Python xử lý được số lớn nên không bị tràn số như C++, nhờ đó ăn thêm được một số test có đáp án nằm gần $A$.Cách 2Xử lý xâu + mảng đánh dấu – O(N)
Mình làm mẫu trên test ví dụ $23990$ nhé. Ta hiểu nó là một chuỗi, giờ cần tìm một chuỗi lớn hơn nó nhưng tổng các chữ số vẫn bằng nó.
Ý tưởng: đi từ phải qua trái (cuối về đầu) để tìm một vị trí tăng thêm 1 đơn vị; và khi tìm được thì phần đằng sau nó phải giảm đi 1 đơn vị để bù lại, để sau cùng tổng các chữ số vẫn bằng nhau. Đi từ phải qua là vì tăng ở vị trí càng bên phải thì số mới càng nhỏ (càng "sát sau" $A$).
- Từ cuối gặp số 0: tăng thành 1 được, nhưng sau nó không còn số nào để giảm đi 1 ⇒ không xét được.
- Tiếp theo là 9: đã tối đa rồi, không tăng được.
- Tiếp theo là 9: cũng không tăng được.
- Tiếp theo là 3: tăng lên thành 4. Đằng sau nó còn
"990", ta phải giảm đi 1: số 0 không giảm được, số 9 giảm còn 8 ⇒ còn"980". Rồi sắp xếp tăng dần phần đuôi thành"089"cho nhỏ nhất.
Vậy kết quả là "2" + "4" + "089" = "24089" 🎉.
Và phải xét tình huống không có kết quả: không tìm ra được vị trí nào để tăng thêm 1, ví dụ "999" (số nào cũng tối đa hết), hay "900" (tìm ra được vị trí để tăng nhưng sau nó không có chữ số nào để giảm) ⇒ in $-1$.
- $s[i]$ tăng 1, in ra $s[0..i]$.
- Giảm chữ số $Min$ trong đuôi đi 1: $b[Min]{-}{-}$, $b[Min - 1]{+}{+}$.
- In phần đuôi theo thứ tự tăng dần nhờ mảng đếm $b$ (chữ số $j$ in $b[j]$ lần).
Gợi ý thêm: dấu hiệu nhận biết dùng mảng đánh dấu quá rõ ràng – dữ liệu chỉ gồm 10 chữ số từ 0 đến 9. Khi phạm vi dữ liệu nhỏ như vậy thì khả năng áp dụng mảng đánh dấu rất lớn. Nhờ mảng đếm $b$ mà việc "sắp xếp" phần đuôi chỉ tốn $O(N)$ thay vì $O(N \log N)$.
9…9 d 0…0: một dãy số 9, rồi (có thể có) một chữ số $d \lt 9$, rồi toàn số 0 – vì nếu có chữ số nào khác 9 mà phía sau nó còn chữ số khác 0 thì nó đã được chọn trước rồi. Chữ số khác 0 nhỏ nhất $Min$ của đuôi là $d$ (nếu $d \ne 0$), còn không thì là 9. Giảm nó đi 1 rồi sắp tăng dần ta được đuôi dạng 0…0 x 9…9: dồn hết số 9 về cuối – đó đúng là đuôi nhỏ nhất có cùng độ dài và tổng chữ số, đồng thời vẫn nhỏ hơn mọi cách tăng ở vị trí bên trái. Mình cũng đã kiểm lại bằng máy với vài trăm test so với vét cạn – khớp hết.Minh hoạ từng bước
Em nhập số $A$ rồi bấm Tiếp để xem con trỏ đi từ phải qua trái, mảng đếm $b$ và $Min$ thay đổi ra sao:
Đây là code áp dụng đúng theo tư tưởng ở trên, độ phức tạp thời gian $O(N)$ – đây cũng là độ phức tạp tối ưu nhất rồi, vì riêng việc đọc và in chuỗi đã tốn $O(N)$. Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
// freopen("SDB.INP", "r", stdin);
// freopen("SDB.OUT", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string s;
cin >> n >> s;
int Min = 10;
int b[10] = {0};
for(int i = n - 1; i >= 0; --i){
if(s[i] < '9' && Min < 10){
s[i]++;
for(int j = 0; j <= i; ++j){
cout << s[j];
}
b[Min]--;
b[Min - 1]++;
for(int j = 0; j < 10; ++j){
while(b[j]--){
cout << j;
}
}
return 0;
}
int idx = s[i] - 48;
b[idx]++;
if(idx > 0){
Min = min(Min, idx);
}
}
cout << -1;
return 0;
}import sys
# sys.stdin = open("SDB.INP", "r")
# sys.stdout = open("SDB.OUT", "w")
n_s = sys.stdin.read().split()
n = int(n_s[0])
s = list(n_s[1])
Min = 10
b = [0] * 10
for i in range(n - 1, -1, -1):
if s[i] < '9' and Min < 10:
s[i] = chr(ord(s[i]) + 1)
for j in range(i + 1):
print(s[j], end='')
b[Min] -= 1
b[Min - 1] += 1
for j in range(10):
print(str(j) * b[j], end='')
sys.exit(0)
idx = int(s[i])
b[idx] += 1
if idx > 0:
Min = min(Min, idx)
print(-1)s[i] - 48là đổi ký tự chữ số sang số (mã ASCII của'0'là 48).- Kiểm tra điều kiện tăng trước, rồi mới đưa $s[i]$ vào mảng đếm $b$ – vì $b$ chỉ chứa phần đuôi sau vị trí $i$.
- $Min$ chỉ cập nhật với chữ số khác 0, vì chữ số 0 không giảm được nữa.
while(b[j]--)in chữ số $j$ đúng $b[j]$ lần (sau vòng này $b[j]$ thành $-1$, nhưng tareturnluôn nên không sao).
Đánh giá độ phức tạp của cách làm này:
- Không gian: chuỗi $s$ dài $N$ và mảng đếm 10 phần tử: $O(N)$.
- Thời gian: duyệt chuỗi một lần từ phải qua trái, in tối đa $N$ ký tự, cộng 10 lượt cho mảng đếm: $O(N)$.
print(..., end='') – nếu hệ thống chấm Python chặt thời gian thì các bạn gom chuỗi lại rồi in một lần bằng ''.join(...) là nhanh hơn nhiều).- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét