Tóm tắt: Đề thi chọn học sinh giỏi cấp tỉnh lớp 12 môn Tin học năm học 2025-2026 của Sở GD&ĐT Phú Thọ bao gồm 4 bài lập trình: Dãy số, Đếm số nguyên tố, Xâu con dài nhất và Ăn vặt. Thời gian làm bài 150 phút với tổng điểm là 20 điểm.
TỔNG QUAN CÁC BÀI THI
| Câu | Tên bài | Chương trình | Dữ liệu | Kết quả | Điểm | Thời gian |
|---|---|---|---|---|---|---|
| 1 | Dãy số | CAU1.* | CAU1.INP | CAU1.OUT | 6 | 1 giây |
| 2 | Đếm số nguyên tố | CAU2.* | CAU2.INP | CAU2.OUT | 6 | 1 giây |
| 3 | Xâu con dài nhất | CAU3.* | CAU3.INP | CAU3.OUT | 5 | 1 giây |
| 4 | Ăn vặt | CAU4.* | CAU4.INP | CAU4.OUT | 3 | 1 giây |
* Phần mở rộng .* là: .CPP đối với ngôn ngữ C++; .C đối với ngôn ngữ C; hoặc .PY đối với ngôn ngữ Python.
Câu 1. Dãy số
Cho dãy gồm tám số nguyên là một hoán vị của tập {1; 2; 3; 4; 5; 6; 7; 8}. Hãy xác định xem dãy đã cho là dãy đơn điệu tăng, đơn điệu giảm hay không đơn điệu.
Dữ liệu: Một dòng gồm 8 số nguyên dương là một hoán vị của tập {1; 2; 3; 4; 5; 6; 7; 8}.
Kết quả: Ghi trên một dòng:
- “ascending” nếu dãy đơn điệu tăng;
- “descending” nếu dãy đơn điệu giảm;
- “mixed” nếu dãy không đơn điệu.
Ví dụ:
| CAU1.INP | CAU1.OUT | GIẢI THÍCH |
|---|---|---|
| 1 2 3 4 5 6 7 8 | ascending | Dãy đơn điệu tăng |
| 8 7 6 5 4 3 2 1 | descending | Dãy đơn điệu giảm |
| 5 8 4 3 1 6 7 2 | mixed | Dãy không đơn điệu |
Ràng buộc:
- Subtask 1 (25% điểm): số thứ \(i\) (\(1 \le i \le 8\)) có giá trị đúng bằng \(i\);
- Subtask 2 (25% điểm): số thứ \(i\) (\(1 \le i \le 8\)) có giá trị bằng \(8 - i + 1\);
- Subtask 3 (50% điểm): Không có thêm ràng buộc bổ sung.
Câu 2. Đếm số nguyên tố
Cho ba số nguyên dương \(L, R, k\). Hãy đếm số lượng các số nguyên tố trong đoạn \([L; R]\) mà có tổng chữ số chia hết cho \(k\).
Dữ liệu: Gồm một dòng chứa ba số nguyên dương \(L, R, k\) (\(1 \le L \le R \le 10^7\), \(1 \le k \le 100\)).
Kết quả: Ghi ra một số nguyên là kết quả tìm được.
Ví dụ:
| CAU2.INP | CAU2.OUT | GIẢI THÍCH |
|---|---|---|
| 1 10 2 | 1 | Trong đoạn [1;10] có các số nguyên tố là 2, 3, 5, 7. Trong đó chỉ có số 2 có tổng chữ số chia hết cho 2. |
| 19 88 8 | 3 | Các số thỏa mãn điều kiện là: 53, 71, 79. |
Ràng buộc:
- Subtask 1 (35% điểm): \(1 \le L, R \le 10\);
- Subtask 2 (20% điểm): \(1 \le L \le R \le 100\);
- Subtask 3 (45% điểm): Không có thêm ràng buộc bổ sung.
Câu 3. Xâu con dài nhất
Cho xâu \(S\) chỉ chứa các kí tự chữ cái tiếng Anh viết thường. Một xâu con của \(S\) là một dãy các kí tự liên tiếp trong xâu \(S\). Ví dụ, “cd” là một xâu con của “abcde” còn “ac” thì không.
Hãy tính độ dài xâu con dài nhất mà xuất hiện ít nhất hai lần trong \(S\).
Dữ liệu:
- Dòng 1: Gồm một số nguyên \(N\) (\(1 \le N \le 200\,000\)) là độ dài của xâu \(S\).
- Dòng 2: Gồm \(N\) chữ cái tiếng Anh viết thường mô tả xâu \(S\).
Kết quả: Ghi ra một số nguyên là độ dài xâu con dài nhất xuất hiện ít nhất hai lần trong \(S\). Nếu không có xâu con nào thỏa mãn, in ra số 0.
Ví dụ:
| CAU3.INP | CAU3.OUT | GIẢI THÍCH |
|---|---|---|
| 3 aba | 1 | Xâu con “a” xuất hiện hai lần. Đây là xâu con dài nhất thỏa mãn. |
| 3 abc | 0 | Không có xâu con nào xuất hiện ít nhất hai lần trong S. |
| 10 abcabckabc | 3 | Xâu con “abc” xuất hiện ba lần. Đây là xâu con dài nhất thỏa mãn. |
| 19 chuchucikciklolipop | 4 | Xâu con “chuc” xuất hiện hai lần. Đây là xâu con dài nhất thỏa mãn. |
Ràng buộc:
- Subtask 1 (20% điểm): \(N \le 3\);
- Subtask 2 (60% điểm): \(N \le 200\);
- Subtask 3 (20% điểm): Không có thêm ràng buộc bổ sung.
Câu 4. Ăn vặt
Bạn An lên kế hoạch đi ăn vặt ở phố đi bộ. Trên phố đi bộ đó có \(R\) cửa hàng bán đồ ăn vặt. Nếu An ghé thăm cửa hàng thứ \(i\) (\(1 \le i \le R\)) thì:
- Mức độ vui vẻ tăng thêm \(V_i\);
- Tốn thêm \(T_i\) phút để ăn;
- Ăn được thêm \(F_i\) đơn vị thức ăn.
An muốn chọn ghé thăm một số cửa hàng sao cho: Tổng thời gian ăn không quá \(M\) phút; Tổng lượng thức ăn không quá \(U\) đơn vị; Mỗi cửa hàng chỉ được ghé thăm không quá một lần.
Hãy giúp An chọn một tập các cửa hàng để ghé thăm sao cho thỏa mãn điều kiện trên và tổng mức độ vui vẻ đạt được là lớn nhất.
Dữ liệu:
- Dòng 1: Gồm ba số nguyên \(M, U, R\) (\(1 \le M \le 300, 1 \le U \le 100, 1 \le R \le 150\)) - thời gian tối đa, lượng thức ăn tối đa và số cửa hàng.
- Dòng thứ \(i\) trong \(R\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(V_i, T_i, F_i\):
\(1 \le V_i \le 10^4\) – mức độ vui vẻ nhận được khi ghé thăm cửa hàng thứ \(i\);
\(1 \le T_i \le M\) – thời gian ăn tại cửa hàng thứ \(i\);
\(1 \le F_i \le U\) – lượng thức ăn mà An ăn được khi ghé thăm cửa hàng thứ \(i\).
Kết quả: Ghi ra một số nguyên duy nhất là tổng mức độ vui vẻ lớn nhất có thể đạt được theo yêu cầu đề bài.
Ví dụ:
| CAU4.INP | CAU4.OUT | GIẢI THÍCH |
|---|---|---|
| 35 1 2 1 15 1 2 20 1 | 2 | Chọn ăn ở quán thứ hai: - Tổng thời gian ăn: 20; - Tổng lượng thức ăn: 1; - Tổng mức độ vui vẻ: 2. |
| 125 10 3 19 35 5 28 90 4 88 70 3 | 107 | Chọn ăn ở quán thứ nhất và quán thứ ba: - Tổng thời gian ăn: 35 + 70 = 105; - Tổng lượng thức ăn: 5 + 3 = 8; - Tổng mức độ vui vẻ: 19 + 88 = 107. |
Ràng buộc:
- Subtask 1 (35% điểm): \(1 \le M \le 100, 1 \le U \le 55, 1 \le R \le 12\);
- Subtask 2 (30% điểm): \(1 \le M \le 240, 1 \le U \le 75, 1 \le R \le 50\);
- Subtask 3 (35% điểm): Không có thêm ràng buộc bổ sung.