Cho vay tiền
Đề bài
Nhân dịp kỉ niệm 100 năm thành lập, ngân hàng EDU dự định dành không quá $n$ đồng cho sinh viên vay vốn không lãi suất. Có $m$ sinh viên đăng ký vay vốn, các sinh viên được đánh số từ $1$ đến $m$, sinh viên thứ $i$ đăng ký vay $t_i$ đồng $(i = 1, 2, \ldots, m)$. Ngân hàng muốn đáp ứng được cho nhiều sinh viên nhất và đương nhiên nếu sinh viên thứ $i$ được vay vốn thì phải bảo đảm nhận đúng $t_i$ đồng. Trong các cách lựa chọn các sinh viên vay vốn thỏa mãn điều kiện, ngân hàng muốn chọn cách cho vay mà sinh viên vay ít nhất là lớn nhất.
Yêu cầu: cho $t_1, t_2, \ldots, t_m$ và $Q$ giả định $n_1, n_2, \ldots, n_Q$, trong đó $n_k$ là giả định thứ $k$ $(k = 1, 2, \ldots, Q)$: khi ngân hàng dự định dành không quá $n_k$ đồng cho sinh viên vay vốn. Với mỗi giả định này, hãy đưa ra cách cho vay thỏa mãn điều kiện đề bài.
Dữ liệu:
- Dòng đầu chứa hai số nguyên $m, Q$.
- Dòng thứ hai chứa $m$ số nguyên dương $t_1, t_2, \ldots, t_m$ $(t_i \le 10^9)$.
- Dòng thứ ba chứa $Q$ số nguyên dương $n_1, n_2, \ldots, n_Q$ $(n_i \le 10^{18})$.
Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả: gồm $Q$ dòng, mỗi dòng chứa hai số nguyên $s, v$, trong đó $s$ là số lượng sinh viên được vay vốn, $v$ là số tiền mà sinh viên được vay ít nhất tương ứng với giả định trong dữ liệu vào.
Chấm điểm:
- Có $25\%$ số test ứng với $25\%$ số điểm của bài có $m, Q \le 10$;
- Có $25\%$ số test khác ứng với $25\%$ số điểm của bài có $m, Q \le 300$;
- Có $25\%$ số test khác ứng với $25\%$ số điểm của bài có $m, Q \le 6000$;
- Có $25\%$ số test ứng với $25\%$ số điểm còn lại của bài có $m, Q \le 90000$.
5 2
1 3 2 3 5
6 83 1
3 2Giải thích ví dụ: các khoản vay là $1, 3, 2, 3, 5$. Với $n = 6$: cho tối đa 3 sinh viên vay ($1 + 2 + 3 = 6$), và đó là cách duy nhất có 3 người → người vay ít nhất vay $1$. Với $n = 8$: vẫn tối đa 3 người, nhưng chọn được $2 + 3 + 3 = 8$ → người vay ít nhất vay $2$ (tốt hơn chọn $1 + 2 + 3$).
Lời mở đầu
Bài này là sự kết hợp rất đẹp của 3 kỹ thuật trong chương: tham lam (để có nhiều người vay nhất thì ưu tiên người vay ít), cửa sổ trượt (đẩy nhóm $s$ người sang phía các khoản vay lớn hơn) và chặt nhị phân trên mảng cộng dồn (để trả lời $90\,000$ câu hỏi thật nhanh). Mình đi từ vét cạn tập con tới lời giải đầy đủ, cách nào cũng 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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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 | m | Q | $t_i$ lớn nhất | $n_k$ | Số SV vay được ($s$) |
|---|---|---|---|---|---|
| 1 – 25 | 7 | 7 | 20 | 2 … 197 | tới 7 |
| 26 – 50 | 300 | 300 | $\approx 10{,}0 \cdot 10^{8}$ | 1 … $\approx 9{,}9 \cdot 10^{17}$ | tới 300 |
| 51 – 75 | 6.000 | 6.000 | $\approx 10{,}0 \cdot 10^{8}$ | 1 … $\approx 10{,}0 \cdot 10^{17}$ | tới 6.000 |
| 76 – 90 | 90.000 | 90.000 | $\approx 10{,}0 \cdot 10^{8}$ | 1 … $\approx 10{,}0 \cdot 10^{17}$ | tới 90.000 |
| 91 – 100 | 90.000 | 90.000 | $\approx 9{,}6 \cdot 10^{7}$ | 45.000 … 45.000 | tới 45.000 |
- Bộ test có 100 test, chia đúng 4 subtask, mỗi subtask 25 test: test 1–25 có $m = Q = 7$, test 26–50 có $m = Q = 300$, test 51–75 có $m = Q = 6000$, test 76–100 có $m = Q = 90\,000$.
- Các $n_k$ rất lớn (tới gần $10^{18}$) nên tổng tiền phải dùng
long long. Tổng của cả $m$ khoản vay tối đa là $9 \cdot 10^4 \cdot 10^9 = 9 \cdot 10^{13}$ – vẫn vừalong long. - Test 91–100 hơi đặc biệt: mọi $n_k$ đều bằng $45\,000$ và có rất nhiều khoản vay bằng $1$, nên đáp án của cả $90\,000$ câu hỏi đều là
45000 1. - Trong bộ test không có giả định nào mà ngân hàng không cho ai vay được (luôn $s \ge 1$). Đề không nói trường hợp $s = 0$ in gì, trong code mình in
0 0.
Các subtask khớp với bộ test như sau (ô ghi số test đúng – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 C++ | Cách 2 C++ | Cách 3 C++ |
|---|---|---|---|---|---|
| 1 (25%) | $m, Q \le 10$ | 1 – 25 | 25/25 | 25/25 | 25/25 |
| 2 (25%) | $m, Q \le 300$ | 26 – 50 | 0/25 | 25/25 | 25/25 |
| 3 (25%) | $m, Q \le 6000$ | 51 – 75 | 0/25 | 25/25 | 25/25 |
| 4 (25%) | $m, Q \le 90000$ | 76 – 100 | 0/25 | 0/25 | 25/25 |
Ý tưởngHai bước tham lam trên mảng đã sắp xếp
Sắp xếp các khoản vay tăng dần: $t_0 \le t_1 \le \ldots \le t_{m-1}$. Với mỗi giả định $n$:
Bước 1 – nhiều người nhất. Lấy dần các khoản nhỏ nhất $t_0, t_1, t_2, \ldots$ cho tới khi tổng vượt $n$. Gọi $s$ là số khoản lấy được. Không thể có nhiều hơn $s$ người: bất kỳ $s + 1$ khoản nào cũng có tổng $\ge t_0 + \ldots + t_s > n$.
Bước 2 – người vay ít nhất là lớn nhất. Giả sử người vay ít nhất là $t_i$. Khi đó $s - 1$ người còn lại phải vay $\ge t_i$, và để tổng nhỏ nhất (dễ $\le n$ nhất) ta chọn $s$ khoản liên tiếp $t_i, t_{i+1}, \ldots, t_{i+s-1}$ – một "cửa sổ" dài $s$ bắt đầu ở $i$. Cửa sổ càng nằm bên phải thì tổng càng lớn (mảng tăng dần) nhưng $t_i$ cũng càng lớn. Vậy ta trượt cửa sổ sang phải chừng nào tổng còn $\le n$; vị trí xa nhất cho đáp án $v = t_i$.
s và phần tử đầu cửa sổ.Em nhập các khoản vay và số tiền $n$ rồi bấm Tiếp để xem hai bước (ô xanh là các khoản đang được chọn):
Cách 1Thử mọi tập con – subtask 1
Với $m \le 10$ ta thử hết $2^m$ cách chọn sinh viên bằng bitmask: bit $i$ của mask bằng 1 nghĩa là sinh viên $i$ được vay. Cách nào có tổng $\le n$ thì so sánh theo (số người, người vay ít nhất).
for i bên trong được gộp thành 1 bước ở dòng if(mask >> i & 1) để bớt dài.if(tong > n) continue;bỏ qua các cách vượt ngân sách.- Điều kiện cập nhật: nhiều người hơn, hoặc bằng số người mà người vay ít nhất vay nhiều hơn – đúng thứ tự ưu tiên của đề.
- Độ phức tạp $O(Q \cdot 2^m \cdot m)$ – chỉ dùng được khi $m$ rất nhỏ.
Kết quả chạy thật: bản C++ (chạy cả 100 test) đúng 25/100 test (quá thời gian ở test 51–100; sai kết quả ở test 26–50), test đúng chạy lâu nhất 0.005s; bản Python (chỉ chạy test 1–25) đúng 25/25 test, test đúng chạy lâu nhất 0.035s.
Từ subtask 2 ($m = 300$) thì $2^{300}$ tập con là con số không tưởng. Bản C++ còn "chết" sớm hơn: 1 << m với $m \ge 31$ bị tràn số (hành vi không xác định) nên vòng lặp chỉ chạy vài lượt rồi in ra kết quả sai. Bài học: vét cạn tập con bằng bitmask chỉ dùng khi $m$ khoảng 20 trở xuống.
Cách 2Tham lam + trượt cửa sổ – O(m) mỗi câu hỏi
Cài đặt đúng 2 bước của phần ý tưởng. Sắp xếp một lần, mỗi câu hỏi đi một lượt từ trái sang phải.
- Vòng
while(s < m && tong + t[s] <= n)là bước 1: cộng dần các khoản nhỏ nhất. Ra khỏi vòng,tongchính là tổng cửa sổ đầu tiên $t_0..t_{s-1}$. - Vòng trượt: cửa sổ $[i, i + s - 1]$ sang $[i + 1, i + s]$ thì tổng mới là
tong - t[i] + t[i + s](bỏ phần tử trái, thêm phần tử phải). Trượt khi tổng mới vẫn $\le n$. - Mỗi câu hỏi tốn $O(m)$ nên cả bài $O(m \log m + Q \cdot m)$: với subtask 4 là $8{,}1 \cdot 10^9$ phép tính – quá chậm.
Kết quả chạy thật: bản C++ đúng 75/100 test (quá thời gian ở test 76–100), test đúng chạy lâu nhất 0.029s; bản Python đúng 50/100 test (quá thời gian ở test 51–100), test đúng chạy lâu nhất 0.063s.
Toàn bộ 25 test của subtask 4 đều quá thời gian – kể cả test 91–100 có $n_k = 45\,000$ nhỏ: ở đó $s = 45\,000$ nên riêng bước 1 của mỗi câu hỏi đã tốn $45\,000$ phép cộng, nhân với $90\,000$ câu hỏi là $4 \cdot 10^9$. Muốn nhanh hơn, ta phải trả lời mỗi câu hỏi mà không đi từng bước.
Cách 3Mảng cộng dồn + chặt nhị phân – full điểm
Cả hai bước đều là tìm "vị trí xa nhất mà tổng còn $\le n$" trên một dãy tăng dần, nên thay vì đi từng bước ta chặt nhị phân:
- Đặt
pre[i] = t[0] + ... + t[i-1](tăng dần). Bước 1: $s$ lớn nhất cópre[s] <= n→ dùngupper_bound. - Tổng cửa sổ bắt đầu ở $i$ là
pre[i + s] - pre[i], tăng dần theo $i$. Bước 2: chặt nhị phân tìm $i$ lớn nhất trong $[0, m - s]$ có tổng $\le n$.
upper_bound(pre, pre + m + 1, n)trả về vị trí đầu tiên cópre > n, lùi 1 là $s$. Vìpre[0] = 0 <= nnên $s \ge 0$.- Chặt nhị phân "tìm vị trí cuối cùng thoả":
mid = (lo + hi + 1) / 2(làm tròn lên) để không bị lặp vô hạn khilo = mid. - Cửa sổ ở $i = 0$ luôn thoả (đó chính là bước 1), nên kết quả
loluôn hợp lệ.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.069s; bản Python đúng 98/100 test (quá thời gian ở test 77, 83), test đúng chạy lâu nhất 0.970s.
Bản Python của Cách 3 chạy sát nút 1 giây ở các test $m = Q = 90\,000$ (riêng việc sắp xếp, đọc và in $90\,000$ dòng đã tốn khá nhiều thời gian trong Python), nên có test bị quá giới hạn một chút. Với bài này các bạn nên nộp C++, hoặc nộp Python bằng PyPy.
Kết quả của cả 3 cách theo từng subtask với Python:
| Subtask | Điều kiện | Các test | Cách 1 Python | Cách 2 Python | Cách 3 Python |
|---|---|---|---|---|---|
| 1 (25%) | $m, Q \le 10$ | 1 – 25 | 25/25 | 25/25 | 25/25 |
| 2 (25%) | $m, Q \le 300$ | 26 – 50 | – | 25/25 | 25/25 |
| 3 (25%) | $m, Q \le 6000$ | 51 – 75 | – | 0/25 | 25/25 |
| 4 (25%) | $m, Q \le 90000$ | 76 – 100 | – | 0/25 | 23/25 |
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. Thử mọi tập con | C++ | 25/100 | 0.005s | Sai từ test 26 (m = 300: 1 << m bị tràn số) |
| Python | 25/25 | 0.035s | Chỉ chạy test 1–25 (subtask 1); m lớn thì 2m tập con là không thể | |
| 2. Tham lam + trượt cửa sổ | C++ | 75/100 | 0.029s | Không qua test 76–100 |
| Python | 50/100 | 0.063s | Không qua test 51–100 | |
| 3. Cộng dồn + chặt nhị phân | C++ | 100/100 | 0.069s | Full điểm |
| Python | 98/100 | 0.970s | Không qua test 77, 83 |
Nhận xét
Đăng nhận xét