Mini contest 4: Đề 1
- Độ 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ọn tiết mục văn nghệ | 25 | |
| 2 | Hổ leo cầu thang | 25 | |
| 3 | Túi quà của Thỏ | 25 | |
| 4 | Con đường kẹo | 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), 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] nghĩa là gì, ô nhỏ nhất bằng bao nhiêu và công thức tính dp[i] 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ọn tiết mục văn nghệ
Gấu Po tổ chức hội diễn văn nghệ trong rừng. Có n tiết mục đăng ký, tiết mục thứ i bắt đầu vào thời điểm s[i] và kết thúc vào thời điểm e[i]. Sân khấu chỉ có một và mỗi lúc chỉ diễn được một tiết mục. Hai tiết mục không chồng lên nhau nếu tiết mục này kết thúc không muộn hơn lúc tiết mục kia bắt đầu (tiết mục kết thúc đúng lúc 5 thì tiết mục khác được bắt đầu đúng lúc 5). Hãy chọn được nhiều tiết mục nhất để diễn trên sân khấu.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo, dòng thứ i gồm hai số nguyên s[i], e[i] (0 ≤ s[i] < e[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số tiết mục nhiều nhất có thể diễ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 | 5 1 4 3 5 0 6 5 7 8 9 | 3 Giải thích: chọn các tiết mục (1, 4), (5, 7) và (8, 9). Không thể chọn được 4 tiết mục. |
| 2 | 3 1 3 3 5 5 7 | 3 Giải thích: các tiết mục nối tiếp nhau, tiết mục trước kết thúc đúng lúc tiết mục sau bắt đầu nên vẫn chọn được cả ba. |
| 3 | 3 1 10 2 5 3 6 | 1 Giải thích: ba tiết mục đôi một chồng lên nhau nên chỉ chọn được một tiết mục. |
Bài 2. Hổ leo cầu thang
Cầu thang trong hang của Hổ có n bậc, đánh số từ 1 đến n. Hổ đứng ở mặt đất (bậc 0) và muốn leo lên bậc n. Mỗi bước Hổ có thể nhảy lên 1, 2 hoặc 3 bậc. Trong cầu thang có m bậc bị hỏng, Hổ không được đặt chân lên các bậc này (nhưng có thể nhảy vượt qua). Hỏi Hổ có bao nhiêu cách để leo từ mặt đất lên bậc n?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 60; 0 ≤ m ≤ n). Dòng 2: m số nguyên đôi một khác nhau, là số thứ tự các bậc bị hỏng (từ 1 đến n). Nếu m = 0 thì không có dòng này. | |
|---|---|---|
| Đầu ra | Số cách leo lên bậc n (có thể lớn hơn 2.109). | |
| 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 0 | 7 Giải thích: có 7 cách, đó là 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3 và 3+1. |
| 2 | 4 1 2 | 3 Giải thích: không được đặt chân lên bậc 2, nên có 3 cách là 1+3, 3+1 và 1+2+1 (bước 1+2 đặt chân lên bậc 1 rồi bậc 3). |
| 3 | 5 1 5 | 0 Giải thích: bậc cuối cùng bị hỏng nên Hổ không thể đứng lên đó, không có cách nào. |
Bài 3. Túi quà của Thỏ
Thỏ có một chiếc túi chịu được tối đa W ki-lô-gam và n món quà. Món quà thứ i nặng w[i] ki-lô-gam và có giá trị v[i]. Thỏ muốn bỏ vào túi một số món quà (mỗi món chỉ có một cái) sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Hãy tính tổng giá trị lớn nhất đó.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100; 1 ≤ W ≤ 104). n dòng tiếp theo, dòng thứ i gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 104; 1 ≤ v[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng giá trị lớn nhất (có thể lớn hơn 2.109). | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 15. 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 5 10 4 40 6 30 3 50 | 90 Giải thích: chọn món nặng 4 (giá trị 40) và món nặng 3 (giá trị 50), tổng nặng 7 và tổng giá trị 90. |
| 2 | 2 5 6 100 7 200 | 0 Giải thích: cả hai món đều nặng hơn 5 nên không bỏ được món nào. |
| 3 | 3 7 3 4 4 5 7 8 | 9 Giải thích: chọn hai món nặng 3 và 4 (tổng nặng 7) được giá trị 9, hơn việc chọn riêng món nặng 7 chỉ được 8. |
Bài 4. Con đường kẹo
Gấu Po đi trong khu vườn hình bảng chữ nhật gồm n hàng và m cột. Ô ở hàng i, cột j có a[i][j] viên kẹo; ô có số âm nghĩa là Gấu Po bị đánh rơi đúng chừng ấy viên kẹo khi đi qua. Gấu Po xuất phát ở ô góc trên trái (1, 1), mỗi bước chỉ được đi sang phải hoặc đi xuống dưới một ô, và dừng lại ở ô góc dưới phải (n, m). Gấu Po đi qua ô nào thì cộng số kẹo ở ô đó (kể cả ô xuất phát và ô cuối). Hỏi tổng số kẹo lớn nhất mà Gấu Po có thể có là bao nhiêu?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo, mỗi dòng m số nguyên a[i][j] (|a[i][j]| ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng số kẹo lớn nhất (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, m ≤ 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 | 3 3 1 2 3 4 5 6 7 8 9 | 29 Giải thích: đường đi 1, 4, 7, 8, 9 có tổng 29 là lớn nhất. |
| 2 | 2 2 -1 -2 -3 -4 | -7 Giải thích: đường đi -1, -2, -4 có tổng -7, tốt hơn đường -1, -3, -4 có tổng -8. |
| 3 | 1 4 5 -1 3 -2 | 5 Giải thích: chỉ có một đường đi duy nhất, tổng là 5 - 1 + 3 - 2 = 5. |