Số Không Giảm
Đề bài
SỐ KHÔNG GIẢM
Một số gọi là số không giảm nếu các chữ số từ trái qua phải tạo thành dãy không giảm (tức là không có chữ số nào phía sau nhỏ hơn chữ số ngay trước nó). Viết chương trình liệt kê các số không giảm có $N$ chữ số $(1 \lt N \lt 7)$.
Input:
- Dòng đầu ghi số bộ test.
- Mỗi bộ test ghi số $N$.
Output:
- Với mỗi bộ test, ghi ra lần lượt các số không giảm có $N$ chữ số, các số cách nhau một khoảng trống.
- Hết một bộ test thì xuống dòng.
Giới hạn thời gian: 1s. Giới hạn bộ nhớ: 65536 Kb.
1
211 12 13 14 15 16 17 18 19 22 23 24 25 26 27 28 29 33 34 35 36 37 38 39 44 45 46 47 48 49 55 56 57 58 59 66 67 68 69 77 78 79 88 89 99Ghi chú: kết quả của một test được viết trên một dòng (ở đề gốc, bảng ví dụ chia thành nhiều dòng chỉ vì kích thước màn hình).
Lời mở đầu
Bài này là bài làm của một em học viên chưa được AC, em ấy không biết sửa làm sao cho đúng. Mình vừa sửa lỗi vừa góp ý cách làm tốt hơn cho em ấy, thấy cũng hay nên tổng hợp lại thành bài viết để anh em cùng tham khảo. Anh em cũng thử sức suy nghĩ bài này trước khi đọc tiếp nhé 💪.
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 OJGiải thích ví dụ: với $N = 2$ ta cần mọi số có 2 chữ số $\overline{ab}$ mà $a \le b$. Chữ số đầu $a$ không thể là 0 (vì là số có 2 chữ số), mà $b \ge a$ nên mọi chữ số đều từ 1 đến 9. Do đó dãy bắt đầu từ 11, 12, ..., 19, rồi 22, ..., 29, rồi 33, ... và kết thúc ở 99 – tổng cộng 45 số. Các số như 10, 20, 21, 31, 32... bị loại vì chữ số sau nhỏ hơn chữ số trước.
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 các số có đúng N chữ số – O(9·10^(N−1)·N)
Bài làm ban đầu của em học viên
Đây là bài làm của em ấy (chưa được AC):
#include <stdio.h>
int soKhongGiam(long j){
int next=j%10;
int total=0;
while(j>0){
int last=j%10;
if(last<=next){
next=0;
next+=last;
total++;
}
j/=10;
}
return total;
}
int soChuSo(long j){
int count=0;
while(j>0){
count++;
j/=10;
}
return count;
}
int main () {
int a;
scanf("%d",&a);
for(int i=1;i<=a;i++){
int N;
scanf("%d",&N);
for(long j=10;j<=999999;j++){
if(soChuSo(j)==N && soKhongGiam(j)==soChuSo(j)){
printf("%ld ",j);
}
}
printf("\n");
}
return 0;
}Ý tưởng của em ấy: duyệt mọi số $j$ từ 10 đến 999999, số nào có đúng $N$ chữ số và "không giảm" thì in ra. Để kiểm tra không giảm, hàm soKhongGiam đi từ chữ số cuối lên, dùng biến total đếm số lần thằng đứng sau $\ge$ thằng đứng trước; nếu cuối cùng total bằng số lượng chữ số thì toàn bộ các chữ số đều không giảm.
Tư tưởng này nó đúng nhưng mà tệ lắm, vì nó luôn phải "vét cạn" trong mọi tình huống. Có 2 chỗ lãng phí lớn:
- Hàm kiểm tra không dừng sớm. Ví dụ với số 54321, ngay lập tức ta thấy chữ số cuối cùng là 1 không thỏa $\ge$ chữ số trên nó là 2, lẽ ra ta kết thúc được ngay lúc này. Nhưng không, code của em vẫn xét tiếp cặp (2, 3), (3, 4), (4, 5) để sau cùng return
total(lúc này là 0) rồi thấy 0 khác số lượng chữ số (là 5) ⇒ không in ra. Mình thêm 2 dòngelse break;vào để gặp cặp sai là thoát luôn. - Vòng for lúc nào cũng xét từ 10 đến 999999 kể cả khi $N$ chỉ là 2. Lẽ ra xét hết 99 là đủ rồi, đâu nhất thiết phải xét thêm từ 100 đến 999999 rồi gọi hàm đếm chữ số để thấy nó khác $N$. Mình chỉ cần xét từ
pow(10, N-1)đến< pow(10, N). Ví dụ $N = 3$ thìpow(10, 2) = 100,pow(10, 3) = 1000, tức là xét từ 100 đến 999 – đúng các số có 3 chữ số.
Khi chỉ xét các số có đúng $N$ chữ số thì cũng không cần hàm soChuSo nữa: chỉ cần kiểm tra soKhongGiam(j) == N. Bởi vì khi nó bằng $N$ nghĩa là vòng lặp chạy đến cuối, mọi cặp đều thỏa số sau $\ge$ số trước; còn nếu khác $N$ thì chắc chắn đã bị break từ sớm. Sửa lại những chỗ đó là code của em được AC (0.94s).
soKhongGiam ban đầu của em ấy chạy thử với mọi số từ 10 đến 999999 thì kết quả kiểm tra vẫn đúng hết. Vậy chỗ chưa qua của bài làm ban đầu nhiều khả năng là do chạy quá chậm: mỗi bộ test đều phải duyệt gần 1 triệu số, mỗi số lại gọi hàm đếm chữ số tới 2 lần và hàm kiểm tra không dừng sớm.Code gọn hơn của mình
Thực ra tư tưởng thì vẫn như nhau như hướng mình đã góp ý ở trên. Tuy nhiên cách thể hiện code của mình gọn hơn xíu: hàm KiemTraLaSoKhongGiam so sánh từng cặp chữ số từ dưới đi lên (vd: 12345 thì so sánh (5, 4), (4, 3), (3, 2), (2, 1)), nếu tại cặp nào mà số sau < số trước (theo đúng thì phải $\ge$) thì ngay lập tức return 0 kết thúc hàm luôn; còn nếu xét đủ hết các cặp thì kết thúc vòng lặp và return 1 xác nhận số này thỏa mãn. Ở hàm main tạo 2 biến start = pow(10, n-1) và end = pow(10, n), duyệt từ start đến < end, số nào thỏa thì in ra.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <stdio.h>
#include <math.h>
int KiemTraLaSoKhongGiam(long long x)
{
long long ChuSoCuoi = x % 10;
x /= 10;
while (x != 0)
{
if (ChuSoCuoi < x % 10)
return 0;
ChuSoCuoi = x % 10;
x /= 10;
}
return 1;
}
int main()
{
long long t;
scanf("%lld", &t);
while (t--)
{
long long n;
scanf("%lld", &n);
long long start = pow(10, n - 1);
long long end = pow(10, n);
for (; start < end; start++)
{
if (KiemTraLaSoKhongGiam(start) == 1)
printf("%lld ", start);
}
printf("\n");
}
return 0;
}def kiem_tra_la_so_khong_giam(x):
chu_so_cuoi = x % 10
x //= 10
while x != 0:
if chu_so_cuoi < x % 10:
return False
chu_so_cuoi = x % 10
x //= 10
return True
t = int(input())
for _ in range(t):
n = int(input())
start = 10 ** (n - 1)
end = 10 ** n
res = []
for x in range(start, end):
if kiem_tra_la_so_khong_giam(x):
res.append(str(x))
print(' '.join(res))Khung chạy tay (để dễ theo dõi, mình giới hạn $N = 2$ – 90 số từ 10 đến 99):
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(1)$.
- Thời gian: mỗi bộ test duyệt $9 \cdot 10^{N-1}$ số, mỗi số kiểm tra tối đa $N$ chữ số ⇒ $O(9 \cdot 10^{N-1} \cdot N)$. Với $N = 6$ là 900000 số.
Cách 2Sinh kế tiếp kiểu "đồng hồ" bằng mảng – O(số lượng kết quả · N)
Ý tưởng chạy vẫn AC, tuy nhiên đây cũng chưa phải là ý tưởng tốt nhất 🙂. Ý tưởng tốt hơn là ta nhận thấy rõ quy luật của dãy số không giảm này. Ví dụ nhé: giả sử $N = 3$, tức là xét trong phạm vi các số có 3 chữ số; các chữ số từ trái qua phải mình ký hiệu là $a$, $b$, $c$ đi hen. Các bạn sẽ nhận ra điều gì?
- Đầu tiên $a$, $b$, $c$ đều là 1 hết, tức là 111.
- Sau đó tăng biến $c$ liên tục lên 1 đơn vị, tức là $c$ sẽ lần lượt là 2, 3, ..., 9; ứng với mỗi lần đó là in ra 112, 113, ..., 119.
- Rồi khi $c$ đã là 9, nếu cộng tiếp nữa lên 10 thì nó sẽ kích hoạt tăng biến trước nó (là biến $b$) lên 1 đơn vị, tức là $b$ đang là 1 thì giờ thành 2, và $c$ sẽ bằng biến $b$ đó, tức là cũng là 2 ⇒ ta có 122.
- Rồi lặp lại quy trình tăng $c$ lên 1 đơn vị, cứ thế đến khi nào nó là 10 thì lại tăng $b$ lên 1 rồi reset $c = b$. Cứ thế đến khi $b$ tăng lên đến 10 thì lại tăng $a$ lên 1 và reset lại $b = a$, $c = b$.
- Cứ vậy đến khi nào $a = 10$ thì dừng, nghĩa là số cuối cùng là 999.
Như thế thì cách này đúng chất chỉ xét qua đúng 165 số thỏa mãn với trường hợp $N = 3$, trong khi cách 1 phải xét đủ từ 100 đến 999 tức là cả 900 số. Càng lên $N$ lớn thì chênh lệch càng nhiều:
| $N$ | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| Số không giảm (cách 2 duyệt) | 45 | 165 | 495 | 1287 | 3003 |
| Số có $N$ chữ số (cách 1 duyệt) | 90 | 900 | 9000 | 90000 | 900000 |
Cài đặt thì gọn nhất là dùng mảng a[1..N] lưu $N$ chữ số (thay cho các biến $a$, $b$, $c$...). Để sinh số kế tiếp: từ phải sang trái tìm chữ số đầu tiên $a_k$ còn tăng được (tức là $a_k \ne 9$ – các chữ số bằng 9 phía sau chính là những "bánh xe" đã chạm 10); tăng $a_k$ lên 1, rồi reset mọi chữ số phía sau về bằng $a_k$. Nếu không còn chữ số nào tăng được ($k = 0$, tức là số $99..9$) thì dừng.
Minh hoạ "đồng hồ" số không giảm
Các bạn nhập $N$ rồi bấm Tiếp để xem từng số được sinh ra (vàng: chữ số vừa tăng, xanh: các chữ số được reset theo nó):
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <stdio.h>
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
int a[10];
for (int i = 1; i <= n; i++)
a[i] = 1;
while (true)
{
for (int i = 1; i <= n; i++)
printf("%d", a[i]);
printf(" ");
int k = n;
while (k >= 1 && a[k] == 9)
k--;
if (k == 0)
break;
a[k]++;
for (int i = k + 1; i <= n; i++)
a[i] = a[k];
}
printf("\n");
}
return 0;
}t = int(input())
for _ in range(t):
n = int(input())
a = [0] + [1] * n # dùng a[1..n] cho giống bản C++
res = []
while True:
res.append(''.join(map(str, a[1:])))
k = n
while k >= 1 and a[k] == 9:
k -= 1
if k == 0:
break
a[k] += 1
for i in range(k + 1, n + 1):
a[i] = a[k]
print(' '.join(res))Khung chạy tay (giới hạn $N \le 3$ để số bước không quá nhiều):
Đánh giá độ phức tạp của cách làm này:
- Không gian: mảng $N$ phần tử – $O(N)$.
- Thời gian: số lượng số không giảm có $N$ chữ số chính là số cách chọn $N$ chữ số từ 1 đến 9 có lặp (sắp xếp tăng dần), bằng $C_{N+8}^{8}$; mỗi số in ra mất $O(N)$ ⇒ $O(C_{N+8}^{8} \cdot N)$ – với $N = 6$ chỉ có 3003 số. Đây là mức tốt nhất có thể, vì đằng nào cũng phải in ra từng ấy số.
combinations_with_replacement) – khớp hết, số lượng đúng 45, 165, 495, 1287, 3003; thêm 100 bộ test ngẫu nhiên nhiều $N$ cũng khớp. Với 100 bộ test $N = 6$: cách 1 (C++) chạy khoảng 0.39 giây, cách 2 (C++) khoảng 0.09 giây. Ở dòng for trong code của mình, mình viết for (; start < end; start++) thay cho for (start; ...) để trình biên dịch khỏi cảnh báo – ý nghĩa y hệt.- 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