Mật Khẩu (PASSWORD) (HSG 12 THPT Lê Quý Đôn Hà Tĩnh 2021-2022)

Nguồn: Đề thi HSG lớp 12 đợt 3 – THPT Lê Quý Đôn (Hà Tĩnh) 2021-2022 Độ khó: Dễ Tham lam Xử lý chữ số Tư duy

Đề bài

BÀI 1. MẬT KHẨU (tên file: PASSWORD.*, dữ liệu vào PASSWORD.INP, kết quả PASSWORD.OUT – 7 điểm)

Sau một thời gian không sử dụng Email, Bigw đã quên mật khẩu đăng nhập. Bigw chỉ nhớ rằng mật khẩu là một số nguyên lớn nhất có $N$ chữ số và tổng các chữ số của nó đúng bằng $S$.

Yêu cầu: Hãy giúp Bigw tìm lại mật khẩu.

Dữ liệu vào: đọc từ file văn bản PASSWORD.INP ghi hai số nguyên dương $N$ và $S$ $(1 \le N \le 10^4;\ 0 \le S \le 10^6)$ trên cùng một dòng và cách nhau một dấu cách.

Kết quả ra: Ghi ra file văn bản PASSWORD.OUT một số duy nhất là mật khẩu cần tìm. Nếu không tìm được mật khẩu thì ghi ra số $-1$.

(Khi chạy thử / 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 file nhé.)

Đề thi học sinh giỏi lớp 12 đợt 3, năm học 2021 – 2022, Trường THPT Lê Quý Đôn – Sở GD&ĐT Hà Tĩnh. Thời gian làm cả đề: 180 phút.

Ví dụ 1 – PASSWORD.INP

5 12

Ví dụ 1 – PASSWORD.OUT

93000

Ví dụ 2 – PASSWORD.INP

3 29

Ví dụ 2 – PASSWORD.OUT

-1

Lời mở đầu

Trong quá trình đi comment dạo mình thấy bài tập này cũng hay nên chia sẻ đề lên đây để anh em cùng xem và thử sức nhé 💪. Bài này là bài 1 trong đề thi HSG lớp 12 của trường THPT Lê Quý Đôn (Hà Tĩnh), rất đơn giản để nhìn ra được tư tưởng, nhưng sẽ có anh em hiện thực code phức tạp – bài viết này mình sẽ chỉ cách code ngắn gọn nhất.

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é:

Link nộp bài

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 OJ

Giải thích ví dụ:

• $N = 5$, $S = 12$: cần số có 5 chữ số, tổng chữ số là 12, và lớn nhất. Ví dụ 12900, 39000, 84000... đều có tổng 12 nhưng 93000 là lớn nhất: chữ số đầu đã là 9 (lớn nhất có thể), chữ số thứ hai chỉ còn được $12 - 9 = 3$, các chữ số sau phải là 0.
• $N = 3$, $S = 29$: số có 3 chữ số lớn nhất là 999 nhưng tổng chữ số cũng chỉ đạt tối đa $9 \times 3 = 27 \lt 29$ ⇒ không có số nào thỏa mãn, in $-1$.

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ừ số lớn nhất đi xuống (chỉ N nhỏ)Cách 2Tham lam: chữ số càng bên trái càng lớn càng tốt

Cách 1Vét cạn từ số lớn nhất đi xuống – O(10^N · N)

Cách "làm theo đề" ai cũng nghĩ ra: duyệt các số có $N$ chữ số từ lớn nhất ($\underbrace{99\ldots9}_{N}$) giảm dần về nhỏ nhất ($10^{N-1}$), số nào có tổng chữ số bằng $S$ thì đó chính là số lớn nhất cần tìm – in ra và dừng luôn. Duyệt hết mà không gặp thì in $-1$. Riêng $N = 1$ thì số nhỏ nhất có 1 chữ số là 0 (nên với $N = 1, S = 0$ đáp án là 0).

Chỉ dùng được khi N rất nhỏ

Đề cho $N \le 10^4$, tức là đáp án có thể dài tới 10 nghìn chữ số! Kiểu long long chỉ chứa được khoảng 18 chữ số, còn số lượng số phải duyệt là $9 \cdot 10^{N-1}$ – với $N = 10$ đã là 9 tỉ số. Cách này chỉ để hiểu đề và làm code đối chiếu (mình dùng nó để kiểm tra cách 2), đi thi thì chỉ ăn được vài test nhỏ thôi nha.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;
int TongChuSo(long long x) {
    int tong = 0;
    while (x != 0) {
        tong += x % 10;
        x /= 10;
    }
    return tong;
}
int main() {
    int n, s;
    cin >> n >> s;
    long long end = 1;
    for (int i = 1; i <= n; i++) {
        end *= 10;
    }
    long long start = end / 10;
    if (n == 1) start = 0;
    for (long long x = end - 1; x >= start; x--) {
        if (TongChuSo(x) == s) {
            cout << x;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

def tong_chu_so(x):
    tong = 0
    while x != 0:
        tong += x % 10
        x //= 10
    return tong


n, s = map(int, input().split())
end = 10 ** n
start = 0 if n == 1 else end // 10
ans = -1
for x in range(end - 1, start - 1, -1):
    if tong_chu_so(x) == s:
        ans = x
        break
print(ans)

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: tối đa $9 \cdot 10^{N-1}$ số, mỗi số tách $N$ chữ số ⇒ $O(10^N \cdot N)$. Chạy tốt khi $N \le 7$.

Không gian$O(1)$

Thời gian$O(10^N \cdot N)$

Cách 2Tham lam từng chữ số từ trái qua phải – O(N)

Giả sử số có độ dài $N$ thì ta hiểu rằng sẽ có $N$ chữ số được đánh từ trái qua phải. Để số kết quả là số lớn nhất thì hãy cho từng chữ số là chữ số lớn nhất có thể, tính từ trái qua phải. Bởi vì hai số cùng $N$ chữ số thì số nào có chữ số đầu tiên (khác nhau) lớn hơn sẽ lớn hơn – nên ưu tiên chữ số bên trái lớn trước đã.

Như ví dụ mẫu $N = 5$ và tổng là 12 thì ta hiểu số sẽ có dạng $\overline{abcde}$:

• $a$ sẽ nhận số 9 là chữ số lớn nhất có thể, lúc này tổng còn $12 - 9 = 3$. Vậy số giờ có dạng $\overline{9bcde}$.
• Tiếp đến xét chữ số $b$: lúc này tổng chỉ còn 3 nên chữ số lớn nhất có thể của $b$ lúc này chỉ là 3. Vậy số có dạng $\overline{93cde}$.
• Vì tổng còn 0 nên các chữ số $c, d, e$ còn lại lần lượt sẽ là 0. Kết quả ta có: 93000.

Còn như ví dụ tiếp theo $N = 3$, tổng $= 29$ thì rõ ràng ta thấy số có 3 chữ số lớn nhất khi các chữ số đều là 9, thì tổng các chữ số tối đa chỉ là $9 \times 3 = 27$ thôi, vì thế tổng 29 đã vượt quá mức tối đa có thể nên kết quả in ra $-1$ không thể có số nào thỏa mãn.

Đáp án luôn có dạng 99...9 r 00...0

Tham lam như trên thì kết quả luôn gồm: $\lfloor S / 9 \rfloor$ chữ số 9, tiếp theo là chữ số $S \bmod 9$ (nếu khác 0), còn lại toàn chữ số 0 cho đủ $N$ chữ số. Điều kiện vô nghiệm: $S \gt 9N$.

Minh hoạ điền từng chữ số

Các bạn nhập $N$, $S$ rồi bấm Tiếp để xem từng chữ số được điền (xanh: chữ số 9, cam: phần dư $S \bmod 9$, xám: chữ số 0):

N (1..14) S (0..200)

Ví dụ nhanh:

Tư tưởng dễ dàng nhìn ra như vậy nhưng sẽ có anh em hiện thực code phức tạp, anh em lưu ý mình làm cách nào cũng được miễn sau cùng mình xuất ra nội dung kết quả đúng như đề bài cần nha. Vì vậy nên chúng ta chẳng cần phải tạo biến lưu trữ kết quả rồi tính toán cập nhật trên biến đó làm chi cả, mình xuất trực tiếp ra đáp án cần luôn:

1. Nếu $9N \lt S$ ⇒ in $-1$.
2. Ngược lại: in sz = S / 9 chữ số 9; nếu S % 9 != 0 thì in thêm chữ số S % 9 và tăng sz lên 1 (đã dùng thêm 1 ô); cuối cùng in N - sz chữ số 0 cho đủ $N$ chữ số.

Trường hợp S = 0

Đề cho $0 \le S$, nên có thể gặp $S = 0$. Khi đó mọi chữ số đều phải là 0: với $N = 1$ đáp án là số 0, còn với $N \ge 2$ thì "000..." không phải là số có $N$ chữ số (chữ số đầu bằng 0) ⇒ không có mật khẩu, in $-1$. Code gốc của mình (soạn trên điện thoại) chưa xét chỗ này nên sẽ in ra $N$ chữ số 0; trong code dưới đây mình đã bổ sung điều kiện (s == 0 && n > 1) cho chắc ăn nhé.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;
int main() {
    int n, s;
    cin >> n >> s;
    if (9 * n < s || (s == 0 && n > 1)) {
        cout << -1;
    }
    else {
        int sz = s / 9;
        for (int i = 1; i <= sz; i++) {
            cout << 9;
        }
        if (s % 9 != 0) {
            cout << s % 9;
            sz++;
        }
        for (int i = n - sz; i >= 1; i--) {
            cout << 0;
        }
    }
    return 0;
}

n, s = map(int, input().split())
if 9 * n < s or (s == 0 and n > 1):
    print(-1)
else:
    sz = s // 9
    res = '9' * sz
    if s % 9 != 0:
        res += str(s % 9)
        sz += 1
    res += '0' * (n - sz)
    print(res)

Khung chạy tay (để dễ theo dõi, giới hạn $N \le 30$):

C++▶ Chạy tay từng dòng codeCách 2: in thẳng S/9 chữ số 9, chữ số S%9 (nếu khác 0), rồi các chữ số 0 cho đủ N chữ số.

Dữ liệu vào (stdin) – sửa thoải mái5 12

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3int main() {

4 int n, s;

5 cin >> n >> s;

6 if (9 * n < s || (s == 0 && n > 1)) {

7 cout << -1;

8 }

9 else {

10 int sz = s / 9;

11 for (int i = 1; i <= sz; i++) {

12 cout << 9;

13 }

14 if (s % 9 != 0) {

15 cout << s % 9;

16 sz++;

17 }

18 for (int i = n - sz; i >= 1; i--) {

19 cout << 0;

20 }

21 }

22 return 0;

23}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: không lưu gì cả, in thẳng ra – $O(1)$.
• Thời gian: in đúng $N$ chữ số ⇒ $O(N)$, với $N = 10^4$ là tức thì.

Không gian$O(1)$

Thời gian$O(N)$

Lưu ý về giới hạn

$S \le 10^6$ nhưng $9N \le 9 \cdot 10^4$, nên khi $S$ lớn thì luôn rơi vào trường hợp $-1$. Phép nhân 9 * n tối đa $9 \cdot 10^4$ nên dùng int thoải mái, không lo tràn số.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với mọi cặp $1 \le N \le 5$, $0 \le S \le 48$ (245 bộ), so với code vét cạn duyệt toàn bộ số có $N$ chữ số – khớp hết, cả 2 test của đề đều đúng. Với $N = 10^4$, cách 2 (C++) chạy dưới 0.01 giây, bản Python khoảng 0.02 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇