Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Việt Nam Sơn
ZaloĐăng ký họcNhắn Zalo cho thầy

Xóa chữ số

Xóa chữ số
Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Trung bình Tham lam Tuyển sinh 10 TP.HCM 2017

Đề bài

XOACHUSO – Xóa chữ số (Kỳ thi tuyển sinh 10 THPT chuyên TP. Hồ Chí Minh, năm học 2017 – 2018, môn Tin học)

Cho trước một số nguyên dương $N$. Gọi $L$ là số chữ số của $N$.

Yêu cầu: Xóa đi $K$ chữ số của $N$ để nhận được phần còn lại là số lớn nhất. Thứ tự các chữ số vẫn giữ nguyên.

Input:

  • Dòng thứ nhất ghi số nguyên dương $N$ $(L \le 255)$.
  • Dòng thứ hai ghi số nguyên dương $K$ $(K < L)$.

Output: số lớn nhất tìm được sau khi xóa $K$ chữ số của $N$.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.

Ví dụ – input
58673
2
Ví dụ – output
873
Lưu ý: trên CLUE OJ dữ liệu đọc từ bàn phím và in ra màn hình; đề gốc có yêu cầu file XOACHUSO.INP/XOACHUSO.OUT thì cứ kệ nó. Ví dụ: xoá 2 chữ số của $58673$ – xoá chữ số $5$ và $6$ còn lại $873$, đó là số lớn nhất.

Lời mở đầu

$N$ có tới 255 chữ số nên không thể lưu trong long long – ta phải xử lý $N$ như một xâu ký tự. Bài này là ví dụ đẹp cho kỹ thuật tham lam: chữ số càng đứng trước thì càng "đáng giá", nên ta cố gắng làm cho các chữ số đầu tiên lớn nhất có thể. Mình đi từ cách vét cạn, tới tham lam "xoá từng chữ số", rồi tới cài đặt gọn bằng ngăn xếp.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngtham lamCách 1vét cạnCách 2xoá K lầnCách 3ngăn xếpTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, đề không chia subtask nhưng độ dài $N$ chia làm 3 mức rõ ràng:

TestSố chữ số L của NK (số chữ số xoá)Độ dài kết quả
1–1091 … 81 … 8
11–20183 … 162 … 15
21–1002551 … 2541 … 254
  • 80 test (21–100) có $N$ dài đúng 255 chữ số – không kiểu số nguyên nào chứa nổi, bắt buộc dùng string.
  • $K$ trải từ 1 tới $L - 1$; có test chỉ giữ lại đúng 1 chữ số (kết quả là chữ số lớn nhất của $N$).
  • Kết quả trong bộ test không bao giờ bắt đầu bằng chữ số 0, nên không phải lo chuyện bỏ số 0 ở đầu.

Kết quả chạy thật (giới hạn 1 giây):

MứcĐiều kiệnTestCách 1
(vét cạn)		Cách 2
(xoá K lần)		Cách 3
(ngăn xếp)
Mức 1$L = 9$ (vừa int)1–1010/1010/1010/10
Mức 2$L = 18$ (vừa long long)11–2010/1010/1010/10
Mức 3$L = 255$21–1002/8080/8080/80

Ý tưởngTham lam: chữ số đứng trước càng lớn càng tốt

Sau khi xoá, mọi kết quả đều có cùng $L - K$ chữ số. Hai số cùng độ dài thì so sánh từ trái sang phải: số nào có chữ số đầu tiên khác nhau lớn hơn thì lớn hơn. Vì vậy chữ số đầu quan trọng hơn tất cả các chữ số sau cộng lại.

Nhận xét tham lam
Nếu có hai chữ số kề nhau $N_i < N_{i+1}$, thì xoá $N_i$ sẽ đưa $N_{i+1}$ (lớn hơn) lên đúng vị trí đó → số mới lớn hơn. Vậy mỗi lần xoá, ta xoá chữ số đầu tiên nhỏ hơn chữ số đứng ngay sau nó. Nếu dãy đã không tăng (ví dụ $9\,7\,7\,3$) thì xoá chữ số cuối cùng.

Cài đặt nhanh hơn bằng ngăn xếp: đọc lần lượt từng chữ số $c$; chừng nào còn lượt xoá và chữ số ở đỉnh ngăn xếp nhỏ hơn $c$ thì xoá đỉnh (vì để $c$ lên trước sẽ tốt hơn); sau đó đẩy $c$ vào. Cuối cùng nếu còn lượt xoá thì cắt bớt ở cuối. Ngăn xếp luôn là một dãy không tăng – các chữ số lớn được đẩy lên đầu.

Em nhập $N$, $K$ rồi bấm Tiếp để xem ngăn xếp hoạt động (ô vàng là chữ số đang xét, ô đỏ là chữ số bị xoá):

Ví dụ nhanh:

Cách 1Vét cạn mọi cách giữ/xoá – $L$ nhỏ

Với mỗi chữ số ta có 2 lựa chọn: giữ hoặc xoá. Dùng đệ quy (quay lui) thử hết các cách xoá đúng $K$ chữ số, mỗi cách cho một xâu kết quả dài $L - K$; lấy xâu lớn nhất. Vì các xâu cùng độ dài nên so sánh xâu cur > best cũng chính là so sánh số.

C++▶ Chạy tay từng dòng codeCách 1: quay lui thử giữ/xoá từng chữ số, lấy xâu lớn nhất.
Dữ liệu mẫu:
  1. Hàm thu(i, xoa): đang xét chữ số $N_i$, đã xoá xoa chữ số; cur chứa các chữ số đã giữ.
  2. Nhánh "giữ": push_back rồi gọi đệ quy, quay về thì pop_back để trả lại trạng thái (quay lui).
  3. Nhánh "xoá" chỉ được đi khi xoa < K. Khi xét hết $L$ chữ số, chỉ nhận cách nào xoá đủ $K$ chữ số.
Không gian$O(L)$
Thời gian$O(\binom{L}{K} \cdot L)$

Số cách chọn là $\binom{L}{K}$: với $L = 18$ tối đa $48\,620$ cách – rất nhanh; với $L = 255$ thì là con số khổng lồ. Bản Python mình dùng itertools.combinations cho gọn.

Kết quả chạy thật: Bản C++ đúng 22/100 test, quá thời gian ở test 21–38, 40–56, 58–100; test đúng chạy lâu nhất 0.05s. Bản Python đúng 22/100 test, quá thời gian ở test 21–56, 58–99; test đúng chạy lâu nhất 0.06s. Cách này ăn trọn mức 1 và 2 (test 1–20), và còn "ăn may" thêm test 39, 57 vì ở đó $K \le 2$ nên số cách chọn chỉ cỡ $\binom{255}{2} = 32\,385$.

Cách 2Tham lam: xoá lần lượt K chữ số – $O(K \cdot L)$

Làm đúng nhận xét tham lam: lặp $K$ lần, mỗi lần tìm chữ số đầu tiên nhỏ hơn chữ số đứng sau và xoá nó (không có thì xoá chữ số cuối).

C++▶ Chạy tay từng dòng codeCách 2: K lần, mỗi lần xoá chữ số đầu tiên nhỏ hơn chữ số đứng sau.
Dữ liệu mẫu:
  1. Vòng while dừng ở vị trí i đầu tiên có N[i] < N[i + 1]; nếu đi tới chữ số cuối thì i là chữ số cuối.
  2. N.erase(i, 1) xoá 1 ký tự ở vị trí i.
  3. Vì sao xoá như vậy là tối ưu? Xét đoạn đầu không tăng $N_0 \ge N_1 \ge \ldots \ge N_i < N_{i+1}$: xoá chữ số nào trước $i$ đều làm chữ số ở vị trí đó nhỏ đi hoặc giữ nguyên, còn xoá $N_i$ làm vị trí $i$ tăng lên – nên đây là lựa chọn tốt nhất cho 1 lần xoá, và lặp lại $K$ lần vẫn đúng.
Không gian$O(L)$
Thời gian$O(K \cdot L)$

Với $L = 255$ chỉ cỡ $255^2 \approx 65\,000$ phép so sánh – quá nhẹ.

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.01s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.04s.

Cách 3Tham lam + ngăn xếp – $O(L)$

Cách 2 mỗi lần xoá lại đi từ đầu xâu. Dùng ngăn xếp thì chỉ cần đi một lượt: chữ số nào bị "đè" bởi chữ số lớn hơn đứng sau thì bị xoá ngay.

C++▶ Chạy tay từng dòng codeCách 3: ngăn xếp không tăng, mỗi chữ số vào/ra tối đa 1 lần – O(L).
Dữ liệu mẫu:
  1. st là một string dùng như ngăn xếp: back() là đỉnh, pop_back() lấy ra, push_back() đẩy vào.
  2. Vòng while xoá đỉnh khi còn lượt (K > 0) và đỉnh nhỏ hơn c – đúng là "xoá chữ số nhỏ hơn chữ số đứng sau nó".
  3. Duyệt xong mà vẫn còn $K$ lượt xoá thì ngăn xếp là dãy không tăng, ta bỏ $K$ chữ số cuối bằng resize.
  4. Mỗi chữ số được đẩy vào 1 lần, lấy ra tối đa 1 lần nên tổng thời gian $O(L)$.
Không gian$O(L)$
Thời gian$O(L)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.01s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.03s.

Tổng kếtKết quả chạy thật trên bộ test

CáchNgôn ngữĐúngLâu nhấtGhi chú
1. Vét cạn mọi cách giữ/xoáC++22/100> 1sQuá thời gian test 21–38, 40–56, 58–100
Python22/100> 1sQuá thời gian test 21–56, 58–99
2. Tham lam: xoá K lầnC++100/1000.01sFull điểm
Python100/1000.04sFull điểm
3. Tham lam + ngăn xếpC++100/1000.01sFull điểm
Python100/1000.03sFull điểm
Ghi chú của mình: với $L \le 255$ thì cả cách 2 và cách 3 đều chạy tức thì; cách 3 vẫn đáng học vì khi $L$ lên tới $10^6$ chỉ có nó chạy kịp. Một cách nhìn khác theo kiểu cửa sổ: chữ số thứ nhất của kết quả là chữ số lớn nhất (lấy vị trí xuất hiện sớm nhất) trong $K + 1$ chữ số đầu; chữ số tiếp theo chọn trong cửa sổ ngay sau vị trí vừa chọn... – cũng cho cùng đáp án.
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 😇

Nhận xét

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)