TỔNG QUAN ĐỀ THI
| Bài | Tên bài | Tệp chương trình | Tệp dữ liệu | Tệp kết quả | Bộ nhớ (MB) | Thời gian (giây) | Điểm |
|---|---|---|---|---|---|---|---|
| 1 | Nén xâu | enco.* | enco.inp | enco.out | 1024 | 1 | 3,0 |
| 2 | Vận chuyển hàng hóa | carg.* | carg.inp | carg.out | 1024 | 1 | 3,0 |
| 3 | Chai và dụng cụ mở | open.* | open.inp | open.out | 1024 | 1 | 2,5 |
| 4 | Chia phần | part.* | part.inp | part.out | 1024 | 1 | 1,5 |
Ghi chú: Dấu * được thay thế bởi cpp hoặc py tương ứng với ngôn ngữ C++ hoặc Python.
Bài 1. Nén xâu (3,0 điểm)
Cho một xâu gồm các chữ cái tiếng Anh thường. Hãy nén xâu này bằng cách thay thế mỗi đoạn gồm các ký tự giống nhau liên tiếp bằng:
- Số lượng ký tự trong đoạn, theo sau là ký tự đó, nếu số lượng ký tự trong đoạn lớn hơn 1;
- Chính ký tự đó, nếu số lượng ký tự trong đoạn bằng 1.
Dữ liệu: Vào từ tệp enco.inp. Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)) là độ dài xâu ban đầu. Dòng thứ hai chứa xâu gồm \(n\) chữ cái tiếng Anh thường.
Kết quả: Ghi ra tệp enco.out một dòng duy nhất chứa xâu sau khi nén.
Ví dụ:
| enco.inp | enco.out |
|---|---|
| 12 aaaabbcddddd | 4a2bc5d |
Subtask / Chấm điểm:
- 30% số điểm: Xâu không có 2 ký tự giống nhau đứng cạnh nhau.
- 30% số điểm: Mỗi đoạn ký tự giống nhau có độ dài không quá 2.
- 20% số điểm: \(n \le 1000\).
- 20% số điểm: Không có ràng buộc bổ sung.
Bài 2. Vận chuyển hàng hóa (3,0 điểm)
Cần xếp \(n\) kiện hàng lên các xe đẩy. Khối lượng các kiện hàng được ghi bằng số nguyên (kg) và chia làm 3 loại:
- Hàng nặng: khối lượng từ 100 kg trở lên.
- Hàng trung bình: khối lượng từ 50 đến 99 kg.
- Hàng nhẹ: khối lượng không quá 49 kg.
Quy tắc chở của mỗi xe đẩy:
- Một kiện hàng bất kỳ;
- Hoặc hai kiện hàng nhẹ;
- Hoặc một kiện hàng nhẹ và một kiện hàng trung bình.
Hãy xác định số xe đẩy ít nhất cần thiết để xếp tất cả các kiện hàng.
Dữ liệu: Vào từ tệp carg.inp. Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\)). \(n\) dòng tiếp theo, mỗi dòng chứa khối lượng của một kiện hàng (từ 1 đến 150 kg).
Kết quả: Ghi ra tệp carg.out số xe đẩy ít nhất.
Ví dụ:
| carg.inp | carg.out |
|---|---|
| 4 50 40 80 120 | 3 |
Giải thích ví dụ: Có 1 kiện nặng (120), 2 kiện trung bình (50, 80) và 1 kiện nhẹ (40). Xe 1 chở 120, Xe 2 chở 80, Xe 3 chở 50 và 40. Tổng cộng cần 3 xe.
Bài 3. Chai và dụng cụ mở (2,5 điểm)
Có \(n\) đồ vật, mỗi đồ vật thuộc một trong ba loại được mô tả bởi cặp số nguyên \((t_i, x_i)\):
- \(t_i = 0\): Chai nắp bật. Nếu lấy sẽ nhận được niềm vui là \(x_i\).
- \(t_i = 1\): Chai cần dụng cụ mở. Nếu lấy và dùng dụng cụ mở, nhận được niềm vui là \(x_i\).
- \(t_i = 2\): Dụng cụ mở chai. Có thể dùng để mở tối đa \(x_i\) chai.
Tìm tổng niềm vui tối đa nhận được khi chọn \(m\) trong số \(n\) đồ vật.
Dữ liệu: Vào từ tệp open.inp. Dòng 1 chứa \(n, m\) (\(1 \le m \le n \le 2 \times 10^5\)). \(n\) dòng tiếp theo chứa \(t_i, x_i\) (\(0 \le t_i \le 2; 1 \le x_i \le 10^9\)).
Kết quả: Ghi ra tệp open.out tổng niềm vui lớn nhất.
Ví dụ:
| open.inp | open.out |
|---|---|
| 8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100 | 27 |
Bài 4. Chia phần (1,5 điểm)
An có \(n\) gói kẹo có số lượng \(a_1, a_2, \dots, a_n\). Tổng số kẹo là \(S = a_1 + a_2 + \dots + a_n\). An muốn chia kẹo cho em trai mình là Bình theo quy tắc:
An tạo một hoán vị chỉ số \(i_1, i_2, \dots, i_n\), sau đó đưa lần lượt các gói kẹo cho Bình cho đến khi tổng số kẹo Bình nhận được lớn hơn hoặc bằng \(\frac{S}{2}\). An giữ các gói kẹo còn lại.
Hãy giúp An tìm một hoán vị sao cho độ chênh lệch về số lượng gói kẹo mà hai người nhận được là nhỏ nhất.
Dữ liệu: Vào từ tệp part.inp. Dòng 1 chứa \(n\) (\(1 \le n \le 2 \times 10^5\)). Dòng 2 chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).
Kết quả: Ghi ra tệp part.out hoán vị của các chỉ số gói kẹo từ 1 đến \(n\).
Ví dụ:
| part.inp | part.out |
|---|---|
| 9 5 6 6 3 1 1 4 4 3 | 1 4 7 8 5 9 2 3 6 |