Ôn tập GĐ2: Đề 1
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Ôn tổng hợp GĐ2
- 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 | Cuộc đua hái nấm | 25 | |
| 2 | Táo trong tầm với | 25 | |
| 3 | Tưới vườn hoa | 25 | |
| 4 | Đoạn đường nhặt xu | 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, truy vấn nằm ngoài dãy...).
Ở 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 giới hạn: sắp xếp, tìm kiếm nhị phân (lower_bound, upper_bound), mảng cộng dồn, mảng hiệu, hai con trỏ, cửa sổ trượt. Chú ý kiểu dữ liệu: khi kết quả có thể vượt quá khoảng 2 tỷ thì dùng long long. Nhớ kiểm tra chỉ số đầu và cuối mảng (l - 1, r + 1) trước khi truy cập.
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. Cuộc đua hái nấm
Gấu Po tổ chức cuộc đua hái nấm cho n bạn, các bạn được đánh số từ 1 đến n. Bạn thứ i hái được c[i] cây nấm và mất t[i] phút. Bảng xếp hạng được tính như sau: bạn hái được nhiều nấm hơn thì đứng trước; nếu bằng số nấm thì bạn mất ít phút hơn đứng trước; nếu vẫn bằng nhau thì bạn có số thứ tự nhỏ hơn đứng trước. Hãy in số thứ tự của các bạn theo đúng thứ hạng từ đầu bảng đến cuối bảng.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2 đến dòng n + 1: dòng thứ i + 1 gồm hai số nguyên c[i], t[i] (0 ≤ c[i], t[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một dòng gồm n số cách nhau một dấu cách: số thứ tự các bạn theo thứ hạng. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 1000. 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 5 30 7 50 5 20 7 50 | 2 4 3 1 Giải thích: bạn 2 và bạn 4 cùng 7 nấm, cùng 50 phút nên bạn 2 (số nhỏ hơn) đứng trước. Hai bạn 1 và 3 cùng 5 nấm, bạn 3 mất 20 phút nên đứng trước bạn 1 (30 phút). |
| 2 | 1 3 10 | 1 Giải thích: chỉ có một bạn. |
| 3 | 3 2 2 2 2 2 2 | 1 2 3 Giải thích: ba bạn bằng nhau hoàn toàn nên xếp theo số thứ tự. |
Bài 2. Táo trong tầm với
Thỏ đứng dưới một cây táo có n quả táo, quả thứ i treo ở độ cao h[i]. Thỏ có q câu hỏi, mỗi câu gồm hai số L và R: có bao nhiêu quả táo treo ở độ cao từ L đến R (tính cả độ cao L và độ cao R)? Hãy trả lời giúp Thỏ.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). q dòng tiếp theo, mỗi dòng gồm hai số nguyên L, R (1 ≤ L ≤ R ≤ 109). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là câu trả lời cho một câu hỏi theo đúng thứ tự. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n, q ≤ 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 | 6 3 5 1 9 5 3 7 3 5 6 8 10 20 | 3 1 0 Giải thích: độ cao từ 3 đến 5 có ba quả (3, 5, 5); từ 6 đến 8 có một quả (7); từ 10 đến 20 không có quả nào. |
| 2 | 1 1 4 4 4 | 1 Giải thích: L = R = 4 và quả táo duy nhất ở độ cao 4. |
Bài 3. Tưới vườn hoa
Hổ có một vườn hoa gồm n luống, đánh số từ 1 đến n, ban đầu mỗi luống chưa có giọt nước nào. Hổ thực hiện m lần tưới: lần thứ i tưới cho các luống từ l đến r, mỗi luống nhận thêm v lít nước. Hoa ở một luống chỉ nở khi luống đó nhận được ít nhất K lít nước. Hỏi sau m lần tưới có bao nhiêu luống hoa nở?
| Đầu vào | Dòng 1: ba số nguyên n, m, K (1 ≤ n, m ≤ 105; 1 ≤ K ≤ 1014). m dòng tiếp theo, mỗi dòng gồm ba số nguyên l, r, v (1 ≤ l ≤ r ≤ n; 1 ≤ v ≤ 109). | |
|---|---|---|
| Đầu ra | Số luống hoa nở. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n, m ≤ 1000. 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 3 4 1 3 2 2 5 3 4 4 1 | 3 Giải thích: sau ba lần tưới, lượng nước của năm luống là 2, 5, 5, 4, 3. Có ba luống (luống 2, 3, 4) có ít nhất 4 lít. |
| 2 | 3 1 10 1 3 5 | 0 Giải thích: mỗi luống chỉ có 5 lít, chưa luống nào đủ 10 lít. |
| 3 | 2 3 3000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 | 2 Giải thích: mỗi luống nhận 3 000 000 000 lít, đúng bằng K nên cả hai luống đều nở. Lượng nước vượt quá giới hạn của int, cần dùng long long. |
Bài 4. Đoạn đường nhặt xu
Gấu Po đi dọc một con đường gồm n ô, ô thứ i có a[i] đồng xu. Gấu Po muốn chọn một đoạn gồm các ô liên tiếp (từ ô l đến ô r, l ≤ r) để nhặt hết xu trong đoạn đó, nhưng túi chỉ chứa được tối đa S đồng xu. Hãy đếm xem có bao nhiêu đoạn mà tổng số xu không vượt quá S. Hai đoạn khác nhau nếu khác vị trí đầu hoặc khác vị trí cuối.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn có tổng không vượt quá S (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 | 5 7 2 1 3 4 1 | 10 Giải thích: có 5 đoạn một ô, 4 đoạn hai ô (tổng 3, 4, 7, 5) và 1 đoạn ba ô (2 + 1 + 3 = 6); các đoạn còn lại có tổng lớn hơn 7. |
| 2 | 3 1 5 5 5 | 0 Giải thích: mỗi ô đã có 5 xu, vượt quá S = 1. |
| 3 | 4 100 1 1 1 1 | 10 Giải thích: mọi đoạn đều thỏa mãn, có 4 + 3 + 2 + 1 = 10 đoạn. |