Làm việc nhà
Đề bài
Bình hay giúp đỡ ba mẹ làm việc nhà. Để đảm bảo việc học, Bình chỉ có thể sắp xếp được một lượng thời gian $T$ để làm việc nhà. Bình lên danh sách những việc nhà mình có thể làm, đi kèm với thời gian cần để thực hiện xong việc đó. Các việc nhà trên có thể thực hiện theo thứ tự bất kỳ nhưng tại một thời điểm chỉ có thể thực hiện một việc nhất định. Bình đang tìm cách làm sao để có thể thực hiện xong nhiều nhất các việc nhà trong danh sách của mình.
Yêu cầu: Cho các việc nhà và thời gian cần để hoàn thành công việc đó. Bạn hãy viết chương trình cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian $T$.
Dữ liệu: vào từ tập tin văn bản VIECNHA.INP, gồm:
- Dòng đầu tiên chứa một số nguyên $T$ $(0 \le T \le 10^9)$ là giới hạn thời gian.
- Dòng thứ hai chứa một số nguyên $C$ $(0 \le C \le 100)$ là số lượng việc nhà.
- $C$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương cho biết thời gian cần để thực hiện xong một việc nhà trong danh sách. Giả sử thời gian tối đa để thực hiện một việc nhà là $10^9$.
Kết quả: ghi ra tập tin văn bản VIECNHA.OUT một số nguyên cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian $T$.
Ràng buộc: $50\%$ test ứng với $50\%$ số điểm của bài có $0 \le T \le 10^4$ và thời gian tối đa để thực hiện một công việc là $10^4$.
6
3
3
6
32Giải thích ví dụ: $T = 6$, có $3$ việc với thời gian $3, 6, 3$. Làm hai việc mất $3$ phút: tổng $3 + 3 = 6 \le 6$ → làm được $2$ việc. Không thể làm cả $3$ việc vì tổng là $12 > 6$.
VIECNHA.INP và ghi ra VIECNHA.OUT. Các code bên dưới đều có dòng if (fopen("VIECNHA.INP", "r")) { freopen(...); freopen(...); }: có file thì đọc/ghi file, không có file thì đọc bàn phím – nên nộp kiểu nào cũng chạy đúng.Lời mở đầu
Một bài tham lam "kinh điển" của đề HSG lớp 9: muốn làm được nhiều việc nhất trong một khoảng thời gian thì làm các việc nhanh nhất trước. Nghe thì hiển nhiên, nhưng mình sẽ cùng chứng minh vì sao nó đúng, đồng thời đi qua 2 cách "không cần nghĩ" (vét cạn và quy hoạch động) để thấy tham lam gọn và mạnh tới mức nào. Tất cả đều chạy thật trên bộ test của CLUE.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | T | C | Thời gian mỗi việc | Đáp án |
|---|---|---|---|---|
| 1 – 10 | 1.098 … 8.605 | 0 … 11 | 197 … 9.661 | 0 … 3 |
| 11 – 50 | 413 … 9.647 | 14 … 97 | 4 … 9.999 | 1 … 14 |
| 51 – 100 | 583 … 32.700 | 13 … 100 | 6 … 32.758 | 0 … 13 |
- Bộ test có 100 test: test 1–50 thuộc subtask 1 ($T \le 10^4$, mỗi việc $\le 10^4$), test 51–100 thuộc subtask 2. Riêng test 1–10 có ít việc ($C \le 11$).
- Có test $C = 0$ (test 7): không có việc nào → in $0$. Có 5 test đáp án bằng $0$ (việc nhanh nhất cũng lâu hơn $T$).
- Điều lạ: ở subtask 2, đề cho $T$ và thời gian mỗi việc tới $10^9$, nhưng thực tế trong bộ test mọi giá trị đều $\le 32768$ (có lẽ sinh bằng
rand()). Vì vậy có 32 test có $T > 10^4$ – đủ làm "vỡ" mảng quy hoạch động khai báo cho subtask 1.
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 vét cạn | Cách 2 quy hoạch động | Cách 3 tham lam |
|---|---|---|---|---|---|
| 1 (50%) | $T \le 10^4$, mỗi việc $\le 10^4$ | 1 – 50 | 50/50 | 50/50 | 50/50 |
| 2 (50%) | $T \le 10^9$, mỗi việc $\le 10^9$ | 51 – 100 | 50/50 | 18/50 | 50/50 |
Ý tưởngViệc nào nhanh thì làm trước
Ta chỉ quan tâm số lượng việc, không quan tâm việc nào. Vì thế mỗi việc "đáng giá" như nhau, chỉ khác nhau ở thời gian – việc càng nhanh càng "rẻ".
Vì sao đúng? Giả sử có một cách làm được $k$ việc với tổng thời gian $\le T$. Đem $k$ việc đó so với $k$ việc nhanh nhất trong danh sách: việc nhanh thứ nhất của danh sách không lâu hơn việc nhanh thứ nhất trong cách kia, việc nhanh thứ hai không lâu hơn việc nhanh thứ hai… nên tổng thời gian của $k$ việc nhanh nhất cũng $\le T$. Vậy nếu làm được $k$ việc thì $k$ việc nhanh nhất chắc chắn làm được → chỉ cần thử lấy dần các việc nhanh nhất là tìm ra $k$ lớn nhất.
Còn nếu đã đến việc thứ $i$ (theo thứ tự tăng dần) mà không đủ thời gian thì các việc sau càng lâu hơn, không cần thử tiếp – nên break luôn.
Em nhập $T$ và thời gian các việc rồi bấm Tiếp để xem các việc được xếp vào "thanh thời gian" dài $T$:
Cách 1Vét cạn: thử làm hoặc không làm từng việc
Chưa cần ý tưởng gì: mỗi việc có 2 lựa chọn – làm hoặc không làm. Viết hàm đệ quy thu(i, thoiGian, dem) lần lượt quyết định từng việc, khi đã quyết định xong cả $C$ việc thì cập nhật đáp án. Nhánh nào đã vượt quá $T$ thì cắt luôn (vì thời gian chỉ tăng thêm).
- Dòng
if(thoiGian > T) return;là cắt nhánh: nếu thiếu dòng này thì luôn phải đi hết $2^C$ nhánh – với $C = 100$ là con số khổng lồ. - Gọi nhánh "làm việc $i$" trước để sớm gặp các nhánh có nhiều việc.
- Thời gian xấu nhất vẫn là $O(2^C)$: số nhánh sống sót bằng số tập việc có tổng $\le T$.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.312s; bản Python đúng 94/100 test (quá thời gian ở test 21, 39, 43, 53, 56, 87), lâu nhất 0.98s.
Bản C++ qua hết bộ test là nhờ bộ test hiền: $T$ nhỏ so với thời gian các việc nên mỗi tập chỉ chứa được tối đa khoảng 14 việc, nhánh bị cắt rất sớm. Mình thử tự tạo một test xấu: $T = 5 \cdot 10^8$, $C = 100$ việc đều mất $10^7$ (làm được 50 việc) – chương trình chạy hơn 10 giây vẫn chưa xong, vì số tập có tổng $\le T$ lúc này lên tới cỡ $2^{99}$. Đề HSG thật chắc chắn sẽ có những test như vậy.
Cách 2Quy hoạch động cái túi – O(C·T), cho subtask 1
Subtask 1 có $T \le 10^4$ gợi ý ngay bài toán cái túi: gọi dp[t] là số việc nhiều nhất làm được với tổng thời gian $\le t$. Xét thêm một việc mất $x$ phút: hoặc không làm (giữ dp[t]), hoặc làm nó, khi đó còn $t - x$ phút cho các việc trước → dp[t - x] + 1.
- Duyệt $t$ giảm dần từ $T$ về $x$ để
dp[t - x]vẫn là giá trị trước khi xét việc hiện tại – mỗi việc chỉ được dùng một lần (cái túi 0/1). - Mảng
dptoàn cục khởi tạo bằng 0: chưa xét việc nào thì làm được 0 việc. - Mảng chỉ có $10^4 + 5$ phần tử theo đúng subtask 1. Với $T$ tới $10^9$ thì không thể khai báo mảng lớn như vậy (cần 4 GB) – đây là lý do cách này chỉ dành cho subtask 1.
Kết quả chạy thật: bản C++ đúng 68/100 test (lỗi chạy (RE) ở test 52–60, 62, 64, 66–68, 70–72, 74–76, 78–79, 81–82, 84, 87–88, 91, 93, 97–98, 100), test đúng chạy lâu nhất 0.006s; bản Python đúng 100/100 test, lâu nhất 0.34s. Các test lỗi đều là test có $T > 10^4$: chỉ số dp[t] vượt khỏi mảng. Nếu khai báo mảng theo $T$ của từng test thì bộ test này (do $T \le 32768$) vẫn qua được, nhưng với $T = 10^9$ đúng như đề thì không thể.
Cách 3Tham lam: sắp xếp tăng dần – O(C log C)
Cài đặt đúng ý tưởng: sắp xếp, cộng dồn, vượt $T$ thì dừng.
tongdùnglong long: tổng 100 việc, mỗi việc tới $10^9$, có thể vượt quá kiểuint. Ở đây ta kiểm tratong + a[i] > Ttrước khi cộng, nêntongluôn $\le T \le 10^9$, nhưngtong + a[i]vẫn có thể tới $2 \cdot 10^9$ – vượtint.- $C = 0$ thì vòng lặp không chạy, in $0$ – đúng.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.006s; bản Python đúng 100/100 test, lâu nhất 0.03s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn (đệ quy) | C++ | 100/100 | 0.312s | Full điểm |
| Python | 94/100 | 0.977s | Quá thời gian ở test 21, 39, 43, 53, 56, 87 | |
| 2. Quy hoạch động | C++ | 68/100 | 0.006s | Lỗi chạy (RE) ở test 52–60, 62, 64, 66–68, 70–72, 74–76, 78–79, 81–82, 84, 87–88, 91, 93, 97–98, 100 |
| Python | 100/100 | 0.341s | Full điểm | |
| 3. Tham lam | C++ | 100/100 | 0.006s | Full điểm |
| Python | 100/100 | 0.032s | Full điểm |
Nhận xét
Đăng nhận xét