KỲ THI LẬP ĐỘI TUYỂN HỌC SINH GIỎI CỦA TỈNH DỰ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM HỌC 2025 - 2026
Sở Giáo dục và Đào tạo Tỉnh Quảng Ninh | Môn thi: TIN HỌC (Ngày thi thứ nhất)
Ngày thi: 11/09/2025 | Thời gian làm bài: 180 phút
TỔNG QUAN NGÀY THI THỨ NHẤT
| Bài | Tên bài | Tệp chương trình | Tệp dữ liệu | Tệp kết quả | Điểm |
|---|---|---|---|---|---|
| 1 | Liên minh | spc.* | spc.inp | spc.out | 7 |
| 2 | Bật đèn | lamp.* | lamp.inp | lamp.out | 7 |
| 3 | Đoạn phủ mạnh | segcov.* | segcov.inp | segcov.out | 6 |
Dấu * được thay thế bởi PY hoặc CPP của ngôn ngữ lập trình tương ứng là Python hoặc C++.
Bài 1. Liên minh (7 điểm)
Tại một quốc gia XYZ, trong quốc hội có \(N\) ghế, mỗi ghế thuộc về một trong \(K\) đảng. Nhiệm vụ của các đảng là thành lập một liên minh cầm quyền.
Để một liên minh có thể cầm quyền, liên minh cần chiếm đa số trong quốc hội. Tuy nhiên, số lượng đảng trong liên minh càng nhiều thì sự ổn định càng giảm do sự khác biệt quan điểm. Do đó, một liên minh mà sau khi loại bỏ bất kỳ đảng nào vẫn còn chiếm đa số thì không được xem là ổn định.
Cụ thể, một nhóm các đảng có thể tạo thành liên minh cầm quyền ổn định nếu thỏa mãn hai điều kiện:
- Tổng số ghế của các đảng trong liên minh phải lớn hơn \(N/2\).
- Nếu loại bỏ bất kỳ đảng nào khỏi liên minh thì số ghế còn lại không còn lớn hơn \(N/2\).
Yêu cầu: Hãy đếm số lượng nhóm đảng có thể tạo thành liên minh cầm quyền ổn định.
Dữ liệu: Vào từ tệp văn bản spc.inp
- Dòng đầu tiên gồm hai số nguyên \(N\) và \(K\), theo thứ tự là số ghế trong quốc hội và số đảng (\(1 \le N \le 10^{18}, 1 \le K \le 36\));
- Dòng thứ hai gồm \(K\) số nguyên \(M_1, M_2, \dots, M_K\) là số ghế của từng đảng (\(1 \le M_i \le N\)), với tổng \(M_1 + M_2 + \dots + M_K = N\).
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra tệp văn bản spc.out một số nguyên duy nhất là số lượng liên minh cầm quyền ổn định có thể tạo thành.
Ví dụ:
| spc.inp | spc.out |
|---|---|
| 18 5 7 2 3 4 2 | 4 |
| 6 6 1 1 1 1 1 1 | 15 |
Giải thích:
- Ví dụ 1: Các đảng lần lượt là 1, 2, 3, 4, 5. Các liên minh ổn định: {1, 3}, {1, 4}, {1, 2, 5}, {2, 3, 4, 5}. Nhóm {1, 2} có tổng 9 ghế, không lớn hơn N/2 = 9. Nhóm {1, 2, 3} không ổn định vì khi loại 2 ra vẫn còn {1, 3} đủ ghế lớn hơn N/2 = 9.
- Ví dụ 2: Bất kỳ nhóm 4 đảng nào trong 6 đảng cũng tạo thành liên minh ổn định.
Ràng buộc:
- 20% số điểm có \(K = 3\);
- 20% số điểm có \(K = N\);
- 15% số điểm có \(K \le 20\);
- 15% số điểm có \(N \le 10^6\);
- 30% số điểm còn lại không có ràng buộc nào thêm.
Bài 2. Bật đèn (7 điểm)
Trong tòa nhà trung tâm hội nghị Bitland có \(N\) phòng họp (đánh số từ 1 đến \(N\)) và \(M\) hành lang nối các phòng đó. Biết rằng:
- Mỗi hành lang nối hai phòng khác nhau.
- Giữa hai phòng bất kỳ, tối đa chỉ có một hành lang.
- Từ bất kỳ phòng nào cũng có thể đi tới bất kỳ phòng khác thông qua các hành lang.
Vào buổi sáng, hệ thống đèn trong một số phòng có thể đang bật, trong khi ở những phòng khác thì không. Nhiệm vụ của bạn là bật đèn trong tất cả các phòng vào đầu ngày làm việc.
Tuy nhiên, toàn bộ đèn của mỗi phòng họp chỉ dùng chung một công tắc cảm biến rất kỳ lạ. Mỗi lần bạn bước vào một phòng, nếu toàn bộ đèn trong phòng đang bật thì công tắc sẽ tự động tắt hết đèn; nếu toàn bộ đèn đang tắt thì công tắc sẽ tự động bật hết đèn.
Cửa vào tòa nhà là ở phòng số 1, vì vậy bạn bắt đầu bằng cách bước vào phòng 1 và đi theo một hành trình theo thứ tự đến các phòng. Bạn có thể kết thúc hành trình ở bất kỳ phòng nào. Hãy tìm một hành trình sao cho tất cả các phòng đều được bật đèn và tổng số lần đến các phòng không vượt quá \(5 \times 10^5\).
Dữ liệu: Vào từ tệp văn bản lamp.inp
- Dòng đầu tiên gồm hai số nguyên \(N\) và \(M\) (\(2 \le N \le 10^5, 1 \le M \le 10^5\)).
- Dòng thứ hai gồm \(N\) số nguyên (0 hoặc 1). Số thứ \(i\) là 1 nếu đèn phòng \(i\) đang bật, là 0 nếu đèn đang tắt. Dữ liệu đảm bảo ít nhất một phòng có đèn đang tắt.
- \(M\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(U_i\) và \(V_i\) (\(1 \le U_i < V_i \le N\)) thể hiện hành lang nối giữa phòng \(U_i\) và \(V_i\).
Kết quả: Ghi ra tệp văn bản lamp.out
- Dòng đầu tiên ghi số nguyên \(K\) - số lượt đi vào các phòng trong hành trình (\(K \le 5 \times 10^5\)).
- Dòng thứ hai ghi \(K\) số nguyên là thứ tự các phòng bước vào (bắt đầu từ phòng 1).
Ví dụ:
| lamp.inp | lamp.out |
|---|---|
| 4 5 0 1 1 0 1 2 2 3 1 3 2 4 3 4 | 6 1 3 2 4 3 2 |
Ràng buộc:
- 30% số điểm có \(N \le 100\);
- 15% số điểm chỉ có một phòng duy nhất có đèn tắt;
- 15% số điểm các phòng nối tiếp thành một dãy theo thứ tự 1, 2, 3,..., N;
- 20% số điểm tất cả các phòng (trừ phòng 1) chỉ nối với phòng 1;
- 20% số điểm còn lại không có ràng buộc nào thêm.
Bài 3. Đoạn phủ mạnh (6 điểm)
Trên trục số, bạn được cho \(N\) đoạn thẳng \([L_1; R_1], [L_2; R_2], \dots, [L_N; R_N]\) với tọa độ đầu mút là các số nguyên dương.
Một thao tác chia nhỏ sẽ thay thế đoạn thẳng \([L; R]\) bằng hai đoạn \([L; M]\) và \([M; R]\), trong đó \(M\) là số nguyên dương và \(L < M < R\).
Ta nói đoạn thẳng \([A; B]\) phủ mạnh đoạn \([L; R]\) nếu đoạn \([A; B]\) bao phủ ít nhất một nửa độ dài của đoạn \([L; R]\).
Yêu cầu: Tìm độ dài ngắn nhất có thể của một đoạn thẳng \([A; B]\) sao cho sau khi thực hiện chính xác \(K\) thao tác chia nhỏ, đoạn \([A; B]\) phủ mạnh tất cả \(N+K\) đoạn thẳng cuối cùng.
Dữ liệu: Vào từ tệp văn bản segcov.inp
- Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5, 0 \le K \le 10^{14}\)).
- \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\) (\(1 \le L_i < R_i \le 10^9\)).
Kết quả: Ghi ra tệp văn bản segcov.out một số nguyên duy nhất là độ dài nhỏ nhất có thể của đoạn \([A; B]\).
Ví dụ:
| segcov.inp | segcov.out |
|---|---|
| 3 3 1 7 3 8 2 9 | 4 |
| 6 1 5 10 2 8 7 14 1 9 5 12 3 13 | 7 |
Ràng buộc:
- 15% số điểm có \(K = 0\);
- 15% số điểm không có hai đoạn thẳng nào giao nhau;
- 10% số điểm có \(N \le 500, R_i \le 500\);
- 20% số điểm có \(N \le 5000, R_i \le 5000\);
- 20% số điểm có \(N \le 10^4\);
- 20% số điểm còn lại không có ràng buộc nào thêm.