Tóm tắt: Đề thi chọn học sinh giỏi THPT cấp tỉnh Cà Mau năm học 2026 - 2027 môn Tin học (Buổi 1). Thời gian làm bài 180 phút với 3 bài toán lập trình xử lý mảng, xâu chuỗi và đồ thị.
TỔNG QUAN ĐỀ THI
| Tên bài | File chương trình | File dữ liệu vào | File kết quả |
|---|---|---|---|
| Câu 1: Xây dựng dãy đẹp | BSBUILD.* | BSBUILD.INP | BSBUILD.OUT |
| Câu 2: Tìm kiếm xâu | MATCHSDK.* | MATCHSDK.INP | MATCHSDK.OUT |
| Câu 3: Đảo chiều cạnh | TOUREDGE.* | TOUREDGE.INP | TOUREDGE.OUT |
Ghi chú: Dấu * được thay thế bởi PY hoặc CPP của ngôn ngữ lập trình sử dụng tương ứng là Python hoặc C++.
CÂU 1 (7 ĐIỂM). XÂY DỰNG DÃY ĐẸP [BSBUILD]
Nhằm xây dựng dãy số nguyên không âm \(N\) phần tử (đánh số \(1 \dots N\)) từ dãy \(N\) số 0, ta có dãy \(M\) lệnh dạng: “gia tăng các phần tử từ vị trí \(l\) đến \(r\)” một đơn vị.
Một dãy được gọi là đẹp nếu phần tử thứ \(i\) không vượt quá giá trị \(a_i\). Hãy xác định số lệnh ít nhất cần loại bỏ sao cho sau khi thực hiện dãy lệnh còn lại, mỗi lệnh một lần, ta thu được dãy đẹp.
Dữ liệu (nhập vào từ file văn bản BSBUILD.INP):
- Dòng 1: số nguyên \(N\) \((1 \le N \le 10^5)\)
- Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((0 \le a_i \le 10^5 \,\forall i)\)
- Dòng 3: số nguyên \(M\) \((1 \le M \le 10^5)\)
- \(M\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên \(l_i, r_i\) \((1 \le l_i \le r_i \le N, \forall i: 1 \le i \le M)\), mô tả lệnh thứ \(i\).
Kết quả (ghi ra file văn bản BSBUILD.OUT):
- In ra một số nguyên duy nhất là số lệnh ít nhất cần loại bỏ để sau khi thực hiện tất cả các lệnh còn lại, phần tử thứ \(i\) \((1 \le i \le N)\) của dãy nhận được không vượt quá \(a_i\).
Subtasks:
| # | Điểm | Ràng buộc bổ sung |
|---|---|---|
| 1 | 20% | \(N \le 15, M \le 15\) |
| 2 | 30% | \(N \le 1000, M \le 1000\) |
| 3 | 50% | Không có ràng buộc bổ sung |
Ví dụ:
| BSBUILD.INP | BSBUILD.OUT | Giải thích |
|---|---|---|
| 4 3 4 4 2 4 3 4 | 1 | Nếu thực hiện cả 4 lệnh, phần tử thứ 4 có giá trị 3 không thoả mãn điều kiện dãy đẹp. Nếu loại bỏ lệnh 4, ta thu được dãy [1,0,1,2], đây là một dãy đẹp. |