ĐỀ BÀI
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12
NGHỆ AN NĂM HỌC 2024 - 2025
Môn thi: TIN HỌC – BẢNG A (Phần lập trình)
| ĐỀ CHÍNH THỨC |
|---|
Thời gian: 100 phút (không kể thời gian giao đề)
Tổng quan bài thi
| Tên bài | File nguồn | File Input | File Output | Thời gian | Bộ nhớ |
|---|---|---|---|---|---|
| Biểu thức có giá trị là số nguyên tố | BIEUTHUCNT.* | BIEUTHUCNT.INP | BIEUTHUCNT.OUT | 1 giây | 1024MB |
| Tặng quà | TANGQUA.* | TANGQUA.INP | TANGQUA.OUT | 1 giây | 1024MB |
| Dãy con có độ dãn 𝑘 | DODANK.* | DODANK.INP | DODANK.OUT | 1 giây | 1024MB |
Phần mở rộng .* được thay thế bằng Pas, Cpp, Py ứng với các ngôn ngữ lập trình Pascal, C++, Python.
Hãy lập trình giải các bài toán sau:
Câu 1 (5.0 điểm). Biểu thức có giá trị là số nguyên tố
An cùng các bạn trong đội tuyển Tin học của trường đang học tập tích cực để tham gia một kì thi lập trình danh giá sắp tới. Bài tập ôn luyện hôm nay được thầy giáo ra cho đội tuyển như sau:
Cho số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 106).
Xét biểu thức 𝑝 = 𝑥 + 2𝑦.
Yêu cầu: Tìm số lượng cặp số nguyên dương (𝑥, 𝑦) sao cho:
- 1 ≤ 𝑥, 𝑦 ≤ 𝑛
- 𝑝 là một số nguyên tố
Dữ liệu cho trong tệp văn bản BIEUTHUCNT.INP gồm một số nguyên dương 𝑛.
Kết quả ghi ra tệp văn bản BIEUTHUCNT.OUT gồm một số nguyên dương là giá trị của 𝑠. Trong đó 𝑠 là số lượng các cặp số nguyên dương (𝑥, 𝑦) thoả mãn hai điều kiện trên. Ví dụ:
| BIEUTHUCNT.INP | BIEUTHUCNT.OUT | GIẢI THÍCH |
| 4 | 6 | Có 6 cặp (𝑥, 𝑦) thoả mãn: (𝑥, 𝑦) = (1,1), 𝑝 = 𝑥 + 2𝑦 = 3 (𝑥, 𝑦) = (1,2), 𝑝 = 𝑥 + 2𝑦 = 5 (𝑥, 𝑦) = (1,3), 𝑝 = 𝑥 + 2𝑦 = 7 (𝑥, 𝑦) = (3,1), 𝑝 = 𝑥 + 2𝑦 = 5 (𝑥, 𝑦) = (3,2), 𝑝 = 𝑥 + 2𝑦 = 7 (𝑥, 𝑦) = (3,4), 𝑝 = 𝑥 + 2𝑦 = 11 |
Giới hạn:
- Có 80% số test ứng với 𝑛 ≤ 103;
- Có 20% số test còn lại ứng với 103 < 𝑛 ≤ 106.
Câu 2 (4.0 điểm).Tặng quà
Buổi lễ bế mạc của một kì thi lập trình danh giá được tổ chức rất hoành tráng, đã đem lại nhiều cảm xúc và bất ngờ cho người tham dự. Có 𝑛 học sinh tham gia cuộc thi danh giá này, trong đó có đội tuyển Tin học của An. Các em đều thấy rất thú vị trong phần tặng quà của buổi lễ bế mạc. Phần tặng quà được điều khiển bởi hai con robot. Các em lần lượt lên sân khấu nhận quà, đến lượt học sinh thứ 𝑖 (𝑖 = 1, 2, … , 𝑛), robot thứ nhất sẽ chọn ngẫu nhiên một món quà có giá là 𝑎𝑖, robot thứ hai yêu cầu trả lời câu hỏi: “Món quà có giá nhỏ nhất và khác với giá của 𝑖 món quà mà robot thứ nhất đã tặng có giá bao nhiêu? ”. Robot thứ hai đã biết kết quả câu trả lời đúng là 𝑏𝑖. Nếu học sinh trả lời đúng sẽ được nhận một món quà đặc biệt của robot thứ hai. Biết rằng, giá của các món quà đều là số nguyên dương.
Yêu cầu: Hãy tìm 𝑏1, 𝑏2, … , 𝑏𝑛.
Dữ liệu cho trong tệp văn bản TANGQUA.INP gồm:
- Dòng 1 ghi số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 106).
- Dòng 2 ghi 𝑛 số nguyên dương 𝑎1, 𝑎2, … , 𝑎𝑛 (1 ≤ 𝑎𝑖 ≤ 106) lần lượt là giá của 𝑛 món quà mà robot thứ nhất tặng cho 𝑛 học sinh.
Kết quả ghi ra tệp văn bản TANGQUA.OUT gồm 𝑛 số nguyên dương 𝑏1, 𝑏2, … , 𝑏𝑛. Các số được ghi trên một dòng và cách nhau bởi dấu cách. Ví dụ:
| TANGQUA.INP | TANGQUA.OUT | GIẢI THÍCH |
| 5 1 2 3 5 7 | 2 3 4 4 4 | Lượt học sinh 1: [𝑎1] = [1] → 𝑏1 = 2. Lượt học sinh 2: [𝑎1, 𝑎2] = [1, 2] → 𝑏2 = 3. Lượt học sinh 3: [𝑎1, 𝑎2,𝑎3] = [1, 2, 3] → 𝑏3 = 4. Lượt học sinh 4: [𝑎1, 𝑎2,𝑎3, 𝑎4] = [1, 2, 3,5] → 𝑏4 = 4. Lượt học sinh 5: [𝑎1, 𝑎2,𝑎3, 𝑎4,𝑎5] = [1, 2, 3, 5,7] → 𝑏5 = 4. |
| 5 2 1 5 4 3 | 1 3 3 3 6 | Lượt học sinh 1: [𝑎1] = [2] → 𝑏1 = 1. Lượt học sinh 2: [𝑎1, 𝑎2] = [2, 1] → 𝑏2 = 3. Lượt học sinh 3: [𝑎1, 𝑎2,𝑎3] = [2, 1, 5] → 𝑏3 = 3. Lượt học sinh 4: [𝑎1, 𝑎2,𝑎3, 𝑎4] = [2, 1, 5,4] → 𝑏4 = 3. Lượt học sinh 5: [𝑎1, 𝑎2,𝑎3, 𝑎4,𝑎5] = [2, 1, 5, 4,3] → 𝑏5 = 6. |
Giới hạn:
- Có 70% số test thoả mãn 𝑛 ≤ 103; 1 ≤ 𝑎1 ≤ 𝑎2 ≤ ⋯ ≤ 𝑎𝑛;
- Có 30% số test thoả mãn 103 < 𝑛 ≤ 106.
Câu 3 (3.0 điểm). Dãy con có độ dãn 𝒌
Đội tuyển Tin học của An đã đạt kết quả tốt trong một kì thi lập trình danh giá. Tất cả các bạn trong đội tuyển đều rất vui và tiếp tục quyết tâm dành giải cao trong kì thi lập trình siêu cup. Kì thi lập trình siêu cup quy tụ các học sinh giỏi về lập trình và có tính cạnh tranh cao. Để giải các bài tập trong kì thi, học sinh phải có kĩ năng phân tích thuật toán. Do vậy, các bài ôn tập cho đội tuyển có mức độ khó hơn. Dưới đây là một bài tập mà thầy giáo đã ra cho đội tuyển của An.
Cho dãy 𝐴 gồm 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 và số nguyên dương 𝑘 (1 ≤ 𝑘 < 𝑛). Một dãy con 𝐵 của 𝐴 gồm các số hạng 𝑎𝑖1, 𝑎𝑖2, … , 𝑎𝑖𝑚 thoả mãn: o 1 ≤ 𝑖1 < 𝑖2 < ⋯ < 𝑖𝑚 ≤ 𝑛. o 𝑖2 − 𝑖1 ≥ 𝑘; 𝑖3 − 𝑖2 ≥ 𝑘; 𝑖4 − 𝑖3 ≥ 𝑘; … . ; 𝑖𝑚 − 𝑖𝑚−1 ≥ 𝑘.
được gọi là dãy con có độ dãn 𝑘. Nói cách khác, các số hạng 𝑎𝑖 và 𝑎𝑗 thuộc dãy con 𝐵 thì |𝑖 − 𝑗| ≥ 𝑘.
Dãy con có một số hạng cũng được gọi là dãy con có độ dãn 𝑘.
Gọi trọng số của dãy con 𝐵 là tổng các số hạng trong dãy con đó, tức là 𝑎𝑖1 + 𝑎𝑖2 + ⋯ + 𝑎𝑖𝑚.
Yêu cầu: Tính tổng trọng số của tất cả các dãy con độ dãn 𝑘 của dãy 𝐴.
Dữ liệu cho trong tệp văn bản DODANK.INP gồm:
- Dòng 1 ghi hai số nguyên dương 𝑛, 𝑘 (1 ≤ 𝑘 < 𝑛 ≤ 106).
- Dòng 2 ghi 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 (0 ≤ 𝑎𝑖 ≤ 106).
Kết quả đưa ra tệp văn bản DODANK.OUT gồm một số nguyên là số dư khi chia 𝑠 cho 109 + 7, tức là 𝑠 % (109 + 7), trong đó 𝑠 là tổng trọng số của tất cả các dãy con độ dãn 𝑘 của dãy 𝐴. Ví dụ:
| DODANK.INP | DODANK.OUT | GIẢI THÍCH |
| 4 2 1 3 3 4 | 27 | Các dãy con có độ dãn 𝑘 = 2. [𝑎1] = [1] → trọng số bằng 1. [𝑎2] = [3] → trọng số bằng 3. [𝑎3] = [3] → trọng số bằng 3. [𝑎4] = [4] → trọng số bằng 4. [𝑎1,𝑎3] = [1, 3] → trọng số bằng 1 + 3 = 4. [𝑎1,𝑎4] = [1, 4] → trọng số bằng 1 + 4 = 5. [𝑎2,𝑎4] = [3, 4] → trọng số bằng 3 + 4 = 7. Tổng 1 + 3 + 3 + 4 + 4 + 5 + 7 = 27. |
| 3 1 1 2 3 | 24 | Các dãy con có độ dãn 𝑘 = 1. [𝑎1] = [1] → trọng số bằng 1. [𝑎2] = [2] → trọng số bằng 2. [𝑎3] = [3] → trọng số bằng 3. [𝑎1,𝑎2] = [1, 2] → trọng số bằng 1 + 2 = 3. [𝑎1,𝑎3] = [1, 3] → trọng số bằng 1 + 3 = 4. [𝑎2,𝑎3] = [2, 3] → trọng số bằng 2 + 3 = 5. [𝑎1,𝑎2,𝑎3] = [1,2,3] → trọng số bằng 1 + 2 + 3 = 6. Tổng 1 + 2 + 3 + 3 + 4 + 5 + 6 = 24. |
Giới hạn:
- Có 25% số test ứng với 𝑘 = 1, 𝑛 ≤ 20; • Có 25% số test ứng với 𝑛 ≤ 20;
- Có 50% số test ứng với 20 < 𝑛 ≤ 106.
------ HẾT -----
Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm.
Họ và tên thí sinh: …………….…………………………….……………; Số báo danh: ……..…….……….
HƯỚNG DẪN GIẢI VÀ CODE C++
Bài 1 BIEUTHUCNT
Link chấm:
https://chuyentinpbc.ucode.vn/problems/hsg-na-2425-bai-1-bieuthucnt-179254
Solution
// với mỗi giá trị p mà 2y+n >= p > 2y
// ta sẽ tìm được một giá trị 0 < x <= n thỏa mãn
// nên bài toán chuyển thành đếm số lượng số nguyên tố trong đoạn (2y, 2y+n]
// sử dụng sàng và mảng cộng dồn
// đpt O(log2(log2(n)))
Code C++:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define task "BIEUTHUCNT"
void read() {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const int N = (int)3e6+5;
int n, c[N];
bool p[N];
void solve() {
cin >> n;
fill(p, p+N, 1); //khởi tạo các giá trị mảng p bằng 1
p[0] = p[1] = 0; // 0, 1 ko ng tố
fo(i,2,sqrt(N)) if (p[i]) for (int j = i * i; j < N; j += i) p[j] = 0; //j là bội của i nen j ko ng tố
fo(i,1,3*n) c[i] = c[i-1] + p[i]; // mảng cộng dồn c[i] là tổng các số nguyên tố đến p[i]
ll ans = 0;
fo(y,1,n) {
ans += c[y*2+n]-c[y*2]; //tổng các số nguyên tố từ 2y đến 2y+n
}
cout << ans;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
// int tc; cin >> tc;
// while (tc--) solve();
read();
solve();
}
Bài 2. TANG QUA
Link chấm:
https://chuyentinpbc.ucode.vn/problems/hsg-na-2425-bai-2-quatang-179255
Solution
// lưu biến j thể hiện số nguyên dương nhỏ nhất chưa được chọn
// mỗi lần nhập vào cập nhật số đó đã được chọn và tìm số nhỏ nhất chưa
// được chọn
// đpt O(n) do mỗi phần tử chỉ duyệt một lần
Code C++:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define task "TANGQUA"
void read() {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const int N = (int)3e6+5;
int n;
bool c[N];
void solve() {
cin >> n;
int j = 1;
fo(i,1,n) {
int x; cin >> x;
c[x] = 1;
while (c[j]) j++;
cout << j << ' ';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
// int tc; cin >> tc;
// while (tc--) solve();
read();
solve();
}
Bài 3 DODANK
Link chấm:
https://chuyentinpbc.ucode.vn/problems/hsg-na-2425-bai-3-dodank-179256
Solution
- sub12() {
// duyệt bitmask để tính và cập nhật kết quả nếu dãy thỏa mãn điều kiện
// khoảng cách giữa 2 vị trí không bé hơn k
- sub3() {
// dpCount[i] : số dãy kết thúc tại vị trí i
// dpSum[i] : tổng trọng số các dãy kết thúc tại vị trí i
// preCount[i] : số dãy kết thúc tại vị trí <= i
// preSum[i] : tổng trọng số các dãy kết thúc tại vị trí <= i
Code c++:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define task "DODANK"
void read() {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const int N = (int)3e6+5, mod = 1e9+7;
int n, k, a[N];
void sub12() {
// duyệt bitmask để tính và cập nhật kết quả nếu dãy thỏa mãn điều kiện
// khoảng cách giữa 2 vị trí không bé hơn k
ll ans = 0;
for (int mask = 0; mask < (1<<n); ++mask) {
ll sum = 0, pre = -1e6;
bool invalid = 0;
fo(i,0,n-1) if (mask>>i&1) {
sum += a[i+1];
if (i-pre<k) invalid = 1;
pre = i;
}
if (!invalid) ans += sum;
}
cout << ans;
}
ll dpCount[N], dpSum[N], preCount[N], preSum[N];
void sub3() {
// dpCount[i] : số dãy kết thúc tại vị trí i
// dpSum[i] : tổng trọng số các dãy kết thúc tại vị trí i
// preCount[i] : số dãy kết thúc tại vị trí <= i
// preSum[i] : tổng trọng số các dãy kết thúc tại vị trí <= i
fo(i,1,n) {
if (i < k) { // trường hợp cơ sở
dpCount[i] = 1;
dpSum[i] = a[i];
} else {
dpCount[i] = (preCount[i-k] + 1) % mod; // cập nhật từ các dãy có sẵn hoặc tạo một dãy mới
dpSum[i] = (preSum[i-k] + dpCount[i] * a[i]) % mod; // tính tổng trọng số
}
// cập nhật cho 2 mảng tổng tiền tố
preCount[i] = (preCount[i-1] + dpCount[i]) % mod;
preSum[i] = (preSum[i-1] + dpSum[i]) % mod;
}
cout << preSum[n];
}
void solve() {
cin >> n >> k;
fo(i,1,n) cin >> a[i];
if (n <= 20) sub1();
else sub2();
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
// int tc; cin >> tc;
// while (tc--) solve();
read();
solve();
}



Bình luận