Mini contest 4: Đề 2
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Tham lam (2), Quy hoạch động (4): LCS, đường đi trên lưới
- Chủ đề
- mini contestôn tập
- Trạng thái
Họ và tên: ................................................
Thời gian làm bài 120 phút. Ngày làm bài: ........................
| Thông tin | Nội dung |
|---|---|
| Thời gian làm bài | 120 phút (tính cả thời gian kiểm tra lại bài) |
| Số bài và tổng điểm | 4 bài, mỗi bài 25 điểm, tổng 100 điểm |
| Giới hạn mỗi test | Thời gian 1 giây, bộ nhớ 256 MB |
| Nhập, xuất dữ liệu | Đọc từ bàn phím (cin), in ra màn hình (cout) |
| Bài | Tên bài | Điểm tối đa | Điểm đạt được |
|---|---|---|---|
| 1 | Chèo thuyền qua sông | 25 | |
| 2 | Chuỗi ngày vàng | 25 | |
| 3 | Dải hạt chung | 25 | |
| 4 | Chia kẹo công bằng | 25 | |
| Tổng điểm | 100 |
Lưu ý khi làm bài
Đọc kỹ cả đề, đặc biệt là phần giới hạn, rồi làm bài dễ trước, bài khó sau. Em có thể làm các bài theo thứ tự tùy ý.
Chạy thử mọi ví dụ mẫu trước khi coi là xong một bài, và tự nghĩ thêm một vài test của riêng mình (n nhỏ nhất, các số bằng nhau, số âm, trường hợp không có cách nào...).
Ở những bài có nhiều nhóm chấm điểm, nếu chưa nghĩ ra cách làm nhanh, em vẫn nên làm cách đơn giản để lấy điểm của nhóm nhỏ.
Chọn công cụ theo bài: tham lam (sắp xếp rồi chọn dần, hai con trỏ), quy hoạch động (mảng dp, công thức truy hồi). Với bài quy hoạch động, hãy viết rõ dp[i] hoặc dp[i][j] nghĩa là gì, ô nhỏ nhất bằng bao nhiêu và công thức tính từ những ô nào. Chú ý kiểu dữ liệu: khi kết quả có thể vượt quá khoảng 2 tỷ thì dùng long long, và cẩn thận khi giá trị có thể âm.
Dành khoảng 10 phút cuối để đọc lại code và kiểm tra các trường hợp đặc biệt. Gợi ý phân bổ thời gian: Bài 1 khoảng 20 phút, Bài 2 khoảng 25 phút, Bài 3 khoảng 30 phút, Bài 4 khoảng 35 phút.
Đề bài
Bài 1. Chèo thuyền qua sông
Thỏ phải đưa n bạn qua sông, bạn thứ i nặng a[i] ki-lô-gam. Mỗi chiếc thuyền chở được tối đa hai bạn và tổng khối lượng trên thuyền không được vượt quá L. Biết mỗi bạn đều nặng không quá L nên bạn nào cũng có thể đi thuyền một mình. Hỏi cần ít nhất bao nhiêu chuyến thuyền để đưa tất cả các bạn qua sông?
| Đầu vào | Dòng 1: hai số nguyên n, L (1 ≤ n ≤ 105; 1 ≤ L ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ L). | |
|---|---|---|
| Đầu ra | Số chuyến thuyền ít nhất. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 10. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | 4 10 9 5 5 1 | 2 Giải thích: chuyến 1 chở bạn nặng 9 và bạn nặng 1 (tổng 10), chuyến 2 chở hai bạn nặng 5 (tổng 10). |
| 2 | 2 8 3 6 | 2 Giải thích: hai bạn đi cùng nhau nặng 3 + 6 = 9 > 8 nên mỗi bạn phải đi một chuyến. |
| 3 | 1 5 5 | 1 Giải thích: chỉ có một bạn nên cần một chuyến. |
Bài 2. Chuỗi ngày vàng
Gấu Po ghi lại điểm may mắn của n ngày liên tiếp, ngày thứ i có điểm a[i] (có thể âm vì hôm đó xui xẻo). Gấu Po muốn chọn một đoạn gồm ít nhất một ngày liên tiếp nhau sao cho tổng điểm may mắn của đoạn đó lớn nhất. Hãy cho biết tổng lớn nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất của một đoạn ngày liên tiếp (có thể âm, có thể lớn hơn 2.109). | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 2000. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | 9 -2 1 -3 4 -1 2 1 -5 4 | 6 Giải thích: đoạn 4, -1, 2, 1 có tổng 6 là lớn nhất. |
| 2 | 3 -3 -1 -2 | -1 Giải thích: đoạn phải có ít nhất một ngày, nên chọn đúng ngày có điểm -1. |
| 3 | 1 5 | 5 Giải thích: chỉ có một ngày. |
Bài 3. Dải hạt chung
Hổ có hai dải hạt cườm, mỗi hạt có một màu được ký hiệu bằng một chữ cái in hoa. Dải thứ nhất là xâu s, dải thứ hai là xâu t. Hổ muốn tìm một dải hạt mới sao cho nó có thể có được từ cả hai dải ban đầu bằng cách gỡ bớt một số hạt (có thể không gỡ hạt nào) mà không đổi thứ tự các hạt còn lại. Hãy cho biết dải hạt mới dài nhất có bao nhiêu hạt.
| Đầu vào | Dòng 1: xâu s gồm các chữ cái in hoa (1 ≤ độ dài ≤ 1000). Dòng 2: xâu t gồm các chữ cái in hoa (1 ≤ độ dài ≤ 1000). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của dải hạt mới (bằng 0 nếu hai dải không có hạt nào cùng màu). | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): độ dài mỗi xâu ≤ 10. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | ABCBDAB BDCABA | 4 Giải thích: dải BCBA (hoặc BDAB, BCAB) có thể gỡ ra từ cả hai xâu và dài 4, không có dải nào dài 5. |
| 2 | ABC DEF | 0 Giải thích: hai dải không có hạt nào cùng màu. |
| 3 | AAAA AA | 2 Giải thích: xâu AA gỡ được từ cả hai dải. |
Bài 4. Chia kẹo công bằng
Gấu Po có n gói kẹo, gói thứ i có a[i] viên. Gấu Po muốn chia tất cả các gói cho hai bạn Thỏ và Hổ (mỗi gói đưa trọn cho một bạn, không được mở gói). Gấu Po muốn sự chênh lệch giữa số kẹo hai bạn nhận được là nhỏ nhất có thể. Hãy cho biết độ chênh lệch nhỏ nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 100). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 100). | |
|---|---|---|
| Đầu ra | Độ chênh lệch nhỏ nhất về số kẹo giữa hai bạn. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 20. Nhóm 2 (15 điểm): không có ràng buộc gì thêm. Chương trình cần chạy trong 1 giây. | |
| Test | Input | Output |
| 1 | 4 1 6 5 11 | 1 Giải thích: Thỏ nhận hai gói 6 và 5 (11 viên), Hổ nhận hai gói 1 và 11 (12 viên), chênh lệch là 1. |
| 2 | 3 2 2 2 | 2 Giải thích: một bạn nhận hai gói (4 viên), bạn còn lại nhận một gói (2 viên), chênh lệch là 2. |
| 3 | 1 7 | 7 Giải thích: chỉ có một gói nên một bạn nhận 7 viên, bạn kia không nhận gì. |