Ôn tập GĐ2: Đề 2
- Độ 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 | Nhật ký chạy bộ | 25 | |
| 2 | Cặp quà vừa túi tiền | 25 | |
| 3 | Dải đèn lồng ít màu | 25 | |
| 4 | Cắt dây thừ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, 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. Nhật ký chạy bộ
Gấu Po ghi lại nhật ký chạy bộ trong n ngày liên tiếp, ngày thứ i chạy được a[i] mét. Mỗi lần ngắm lại nhật ký, Gấu Po muốn biết từ ngày l đến ngày r tổng cộng đã chạy bao nhiêu mét. Có q câu hỏi như vậy, hãy trả lời giúp Gấu Po.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). q dòng tiếp theo, mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng số mét từ ngày l đến ngày r. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n, q ≤ 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 2 7 1 6 1 5 2 4 3 3 | 20 10 7 Giải thích: tổng cả năm ngày là 20; ngày 2 đến 4 là 2 + 7 + 1 = 10; ngày 3 một mình là 7. |
| 2 | 3 1 1000000000 1000000000 1000000000 1 3 | 3000000000 Giải thích: tổng vượt quá giới hạn của int, cần dùng long long. |
Bài 2. Cặp quà vừa túi tiền
Thỏ vào cửa hàng có n món quà, món thứ i có giá a[i] đồng. Thỏ có K đồng và muốn mua đúng hai món quà khác nhau sao cho tổng giá không vượt quá K. Hãy đếm xem có bao nhiêu cặp món quà như vậy. Hai cặp được coi là khác nhau nếu có ít nhất một món ở vị trí khác nhau, kể cả khi các món có cùng giá.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 2.109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp món quà có tổng giá không vượt quá K (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 10 1 9 3 5 8 | 5 Giải thích: các cặp thỏa mãn có giá (1, 9), (1, 3), (1, 5), (1, 8) và (3, 5). |
| 2 | 3 1 1 1 1 | 0 Giải thích: mọi cặp đều có tổng 2, lớn hơn K = 1. |
| 3 | 4 100 10 10 10 10 | 6 Giải thích: mọi cặp đều có tổng 20, có 6 cặp. |
Bài 3. Dải đèn lồng ít màu
Hổ treo n chiếc đèn lồng thành một hàng, chiếc thứ i có màu a[i]. Hổ muốn chọn một đoạn gồm các chiếc đèn liên tiếp mà chỉ có không quá d màu khác nhau để làm khung ảnh. Hãy cho biết đoạn dài nhất như vậy có bao nhiêu chiếc đèn.
| Đầu vào | Dòng 1: hai số nguyên n, d (1 ≤ n ≤ 105; 1 ≤ d ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | Độ dài của đoạn dài nhất có không quá d màu khác nhau. | |
| 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 | 8 2 1 2 1 3 3 3 2 1 | 4 Giải thích: đoạn 1 3 3 3 (từ vị trí 3 đến vị trí 6) chỉ có hai màu và dài 4. Mọi đoạn dài 5 đều có ít nhất ba màu. |
| 2 | 4 1 5 5 5 5 | 4 Giải thích: cả dãy chỉ có một màu. |
| 3 | 5 1 1 2 3 4 5 | 1 Giải thích: hai chiếc đèn cạnh nhau luôn khác màu, nên chỉ chọn được một chiếc. |
Bài 4. Cắt dây thừng
Gấu Po có n sợi dây thừng, sợi thứ i dài a[i] mét. Gấu Po muốn cắt các sợi dây thành ít nhất k đoạn có độ dài bằng nhau, mỗi đoạn dài một số nguyên mét (mỗi sợi dây được cắt thành nhiều đoạn, phần thừa nếu có thì bỏ đi). Hãy tìm độ dài lớn nhất của mỗi đoạn. Nếu cắt thế nào cũng không đủ k đoạn thì in 0.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của mỗi đoạn, hoặc 0 nếu không thể. | |
| Giới hạn và chấm điểm | Nhóm 1 (10 điểm): n ≤ 1000 và a[i] ≤ 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 | 3 5 8 5 7 | 3 Giải thích: với độ dài 3, ba sợi dây cho 2 + 1 + 2 = 5 đoạn. Với độ dài 4 chỉ được 2 + 1 + 1 = 4 đoạn, không đủ. |
| 2 | 2 10 3 4 | 0 Giải thích: ngay cả khi cắt thành các đoạn dài 1 mét cũng chỉ được 7 đoạn. |
| 3 | 1 1 1000000000 | 1000000000 Giải thích: giữ nguyên sợi dây, được đúng 1 đoạn. |