Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án)

 Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
PHÒNG GIÁO DỤC & ĐÀO TẠO ĐỀ KIỂM TRA CHẤT LƯỢNG HỌC SINH 
  GIỎI CẤP TRƯỜNG
 MÔN: TIN HỌC – LỚP 12
 Thời gian: 180 phút (không kể thời gian giao đề)
 TỔNG QUAN BÀI THI
 Bài File mã nguồn File dữ liệu vào File dữ liệu ra Bộ nhớ Điểm
 Bài 1 SEQ.* SEQ.INP SEQ.OUT 1024 MB 5.0
 Bài 2 TRI.* TRI.INP TRI.OUT 1024 MB 5.0
 Bài 3 GRID.* GRID.INP GRID.OUT 1024 MB 6.0
 Bài 4 MSD.* MSD.INP MSD.OUT 1024 MB 6.0
 Bài 5 PLAN.* PLAN.INP PLAN.OUT 1024 MB 8.0
Chú ý: Học sinh làm bài trên máy tính, sử dụng ngôn ngữ lập trình C++ hoặc Python viết 
chương trình theo yêu cầu của các bài toán
- Học sinh nộp bài thi là các file mã nguồn được đặt tên theo quy định trên; dấu * trong tên 
file mã nguồn là cpp hoặc py tương ứng với ngôn ngữ C++ hoặc Python;
- Không ghi thông tin cá nhân (họ tên, số báo danh, ngày sinh, trường,...) và các ký hiệu 
khác thường vào file mã nguồn nộp;
Bài 1. Dãy số nguyên
 a1 k
Dãy số nguyên A {a1, a2, a3, a4,} được xây dựng như sau: với k và d là các số 
 ai ai 1 d
nguyên cho trước. Ví dụ: với k = 2 và d = 3 thì dãy số A là {2, 5, 8, 11}.
Yêu cầu: Cho số nguyên dương n, tìm số an của dãy A và tính tổng a1 + a2 +  + an. 
Dữ liệu: Nhập vào từ file văn bản SEQ. INP có 3 số nguyên dương k, d và n viết cách nhau 
bởi dấu cách trống (k, d ≤ 103; n ≤ 1015).
Kết quả: Ghi ra file văn bản SEQ.OUT 2 dòng:
• Dòng đầu tiên ghi số nguyên an của dãy A;
• Dòng thứ hai ghi số nguyên là phần dư trong phép chia tổng a 1 + a2 +  + an cho số 
nguyên 1000000007.
Ví dụ:
 SEQ.INP SEQ.OUT Giải thích
1 2 5 9 Dãy số là {1, 3, 5, 7, 9, 11  }. Số 5 = 9;
 25 Tổng 푆 = 1 + 3 + 5 + 7 + 9 = 25
10 100 1000 99910
 49960000
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
Chấm điểm:
• Subtask 1 (80% số điểm): Dữ liệu vào có 푛 ≤ 106.
• Subtask 2 (20% số điểm): Không có ràng buộc nào thêm.
Bài 2. Tam giác vuông
Trong mặt phẳng tọa độ , cho đoạn thẳng nằm trên trục hoành và có trung điểm 
là gốc tọa độ (0; 0).
Yêu cầu: Đếm số tam giác vuông có cạnh huyền là và tọa độ của đỉnh ở góc vuông là số 
nguyên.
Dữ liệu: Nhập vào từ file văn bản TRI.INP có một số nguyên dương ( ≤ 1016) là hoành độ 
của điểm .
Kết quả: Ghi ra file văn bản TRI.OUT một số nguyên dương là kết quả tìm được theo yêu 
cầu của bài toán.
Ví dụ:
 TRI.INP TRI.OUT Giải thích
5 10 Có 10 tam giác vuông như hình vẽ sau đây:
3125 42
Chấm điểm:
• Subtask 1 (80% số điểm): Dữ liệu vào có ≤ 108.
• Subtask 2 (20% số điểm): Không có ràng buộc nào thêm.
Bài 3. Lưới ô vuông
Cho lưới ô vuông có hàng và 푛 cột. Ô vuông (푖, 푗) là ô giao giữa hàng 푖 (푖 ∈ [1, ])
với cột 푗 (푗 ∈ [1, 푛]). Trên mỗi ô (푖, 푗) ghi một số nguyên dương theo quy tắc sau:
• Bắt đầu từ ô trên cùng bên trái (1,1) ghi số nguyên dương .
• Các ô tiếp theo lần lượt từ trái sang phải, từ trên xuống dưới, từ phải quay về trái ghi một số 
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
có giá trị hơn số ở ô liền kề phía trước đó một giá trị nguyên dương cho trước. Thao tác 
này lặp lại cho đến hết ô cuối cùng.
Ví dụ: với = 6, 푛 = 5, = 2, = 3, các số trong hình chữ nhật như sau:
 2 5 8 11 14 17
 35 20
 38
 89
Yêu cầu: Tìm hình chữ nhật (gồm các ô liền kề nhau) có nhiều ô nhất sao cho tổng các số 
trong hình chữ nhật đó có giá trị bằng số nguyên 퐾 cho trước.
Dữ liệu: Nhập vào từ file văn bản GRID.INP có nội dung như sau:
• Dòng đầu tiên có 4 số nguyên dương , 푛, , ( , ≤ 102; , 푛 ≤ 103) viết cách nhau bởi 
dấu cách trống.
• Dòng thứ hai là số nguyên dương 퐾 (퐾 ≤ 1012).
Kết quả: Ghi ra file văn bản GRID.OUT số lượng ô của hình chữ nhật tìm được theo yêu 
cầu. Nếu không có hình chữ nhật nào thỏa mãn thì ghi ra -1.
Ví dụ:
 GRID.INP GRID.OUT Giải thích
1 8 1 2 4 Hình chữ nhật có các số in đậm:
32 1 3 5 7 9 11 13 15
5 6 2 3 9 Hình chữ nhật có các số in đậm:
414 2 5 8 11 14 17
 35 32 29 26 23 20
 38 41 44 47 50 53
 71 68 65 62 59 56
 74 77 80 83 86 89
Chấm điểm:
• Subtask 1 (50% số điểm): Dữ liệu vào có: = 1.
• Subtask 2 (50% số điểm): Không có ràng buộc nào thêm.
Bài 4. Tổng ước lớn nhất
Cho mảng có 푛 số nguyên dương { 1, 2,  , 푛} và số nguyên dương ( ≤ 푛). Có
푞 yêu cầu, mỗi yêu cầu là: cho số nguyên dương 푖 (푖 ≤ 푛 − + 1), tính tổng ước dương của 
phần tử có tổng ước dương (không kể chính nó) lớn nhất trong mảng con có đúng phần tử 
bắt đầu tử phần tử 푖 của mảng .
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
Yêu cầu: Tìm kết quả của 푞 yêu cầu trên.
Dữ liệu: Nhập vào từ file văn bản MSD.INP có nội dung như sau:
• Dòng đầu tiên có 3 số nguyên dương 푛, , 푞 ( , 푞 ≤ 푛 ≤ 106);
• Dòng thứ hai có 푛 số nguyên dương 1, 2,  , 푛( 푖 ≤ 106);
• 푞 dòng tiếp theo, mỗi dòng có một số nguyên dương 푖 (푖 ≤ 푛 − + 1) tương ứng với số 
nguyên dương 푖 được mô tả trong bài toán.
Các số nguyên trong cùng dòng dữ liệu viết cách nhau bởi dấu cách trống.
Kết quả: Ghi ra file văn bản MSD.OUT 푞 dòng dữ liệu, mỗi dòng có một số nguyên là kết 
quả của một yêu cầu được mô tả trong bài toán, theo thứ tự tương ứng với số nguyên 푖 mô tả 
trong file dữ liệu vào.
Ví dụ:
 MSD.INP MSD.OUT Giải thích
10 4 5 9 Tổng ước số dương của các số lần lượt là:
2 9 10 14 4 15 8 6 1 20 10 1 4 8 10 3 9 7 6 0 22
6 22 Yêu cầu: 1: 푖 = 6 → mảng con 4 phần tử là: {15, 
2 10 8, 6, 1} có tổng ước là {9,7,6,0}, giá trị lớn nhất 
7 10 của tổng ước là 9
4 Yêu cầu: 2: 푖 = 2 → mảng con 4 phần tử là: {9, 
1 10, 14, 4} có tổng ước là {4,8,10,3}, giá trị lớn 
 nhất của tổng ước là 10
Chấm điểm:
• Subtask 1 (30% số điểm): Dữ liệu vào có n ≤ 103.
• Subtask 2 (30% số điểm): Dữ liệu vào có 푞 ≤ 102.
• Subtask 3 (40% số điểm): Không có ràng buộc nào thêm.
Bài 5. Kế hoạch sửa đường
Thành phố HP có 푛 khu dân cư được đánh số từ 1 đến 푛. Ban đầu, thành phố có con 
đường 2 chiều, mỗi con đường kết nối 2 khu dân cư và 푣 (1 ≤ , 푣 ≤ 푛; ≠ 푣). Hệ thống 
giao thông đảm bảo luôn có đường đi từ một khu dân cư đến bất kì khu dân cư khác.
Sau một thời gian sử dụng, hiện tại tất cả con đường cần phải bảo trì và Ban quản lý đã lập 
danh sách thứ tự bảo trì các con đường. Mỗi khi sửa chữa thì con đường đó bị cấm và tất 
nhiên hệ thống giao thông có thể bị chia cắt và tạo nên các vùng dân cư độc lập với nhau 
(một vùng dân cư gồm các khu dân cư có đường đi đến nhau; 2 vùng dân cư được gọi là độc 
lập nhau nếu không có con đường đi từ khu dân cư ở vùng này đến khu dân cư ở vùng kia).
Ban quản lý thành phố muốn tính mức độ chia cắt của hệ thống giao thông khi thực hiện sửa 
chữa lần lượt m con đường theo danh sách. Biết rằng mức độ chia cắt của hệ thống giao 
thông là số vùng dân cư độc lập với nhau được tạo thành khi sửa chữa các con đường.
Yêu cầu: Tính mức độ chia cắt của hệ thống giao thông.
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
Dữ liệu: Vào từ file văn bản PLAN.INP có nội dung như sau:
• Dòng đầu tiên có 2 số nguyên dương 푛, (푛, ≤ 105) là số lượng khu dân cư và số lượng 
con đường hai chiều.
• dòng tiếp theo, mỗi dòng có 2 số nguyên dương và 푣 mô tả có một tuyến đường 2 
chiều 2 khu dân cư và 푣 ( , 푣 ≤ 푛; ≠ 푣).
• Dòng cuối cùng có số nguyên dương là hoán vị của dãy 1,2,3,  , mô tả danh sách thứ 
tự các con đường được sửa chữa.
Các số nguyên trong cùng dòng dữ liệu cách nhau bởi dấu cách trống.
Kết quả: Ghi ra file văn bản PLAN.OUT có dòng dữ liệu, mỗi dòng dữ liệu thứ 푖 ghi một 
số nguyên dương lần lượt là độ chia cắt của hệ thống giao thông khi thực hiện sửa chữa đến 
con đường thứ 푖 (푖 = 1 ÷ ) trong kế hoạch.
Ví dụ:
 PLAN.INP PLAN.OUT
 4 5 1
 1 2 1
 1 3 2
 1 4 3
 2 3 4
 4 3
 4 2 5 1 3
Chấm điểm:
• Subtask 1 (60% số điểm): Dữ liệu vào có: 푛, ≤ 103.
• Subtask 2 (40% số điểm): Không có ràng buộc nào thêm.
 ----------HẾT----------
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài 1. Dãy số nguyên
C++
#include 
#include 
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int main() {
 // Tối ưu tốc độ đọc ghi (nếu dùng cin/cout)
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // Mở file input và output
 ifstream fi("SEQ.INP");
 ofstream fo("SEQ.OUT");
 ll k, d, n;
 if (!(fi >> k >> d >> n)) return 0;
 // 1. Tính số hạng thứ n: a_n = k + (n - 1) * d
 // Vì n lên tới 10^15, a_n có thể vượt quá giới hạn long long nếu k, d lớn.
 // Tuy nhiên theo đề k, d <= 10^3 nên long long (max ~ 9*10^18) vẫn chứa đủ.
 ll an = k + (n - 1) * d;
 // 2. Tính tổng S = n * (a1 + an) / 2
 // Vì tính S mod 10^9 + 7, ta cần xử lý phép chia 2 trong modulo
 // Cách an toàn nhất: Tính (n * (a1 + an)) trước khi chia 2, sau đó mới mod.
 ll a1 = k;
 ll sum_val;
 // Để tránh tràn số khi nhân n * (a1 + an), ta xử lý như sau:
 // S = (n * (a1 + an)) / 2
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
 ll v1 = n;
 ll v2 = a1 + an;
 // Một trong hai số v1 hoặc v2 chắc chắn là số chẵn
 if (v1 % 2 == 0) v1 /= 2;
 else v2 /= 2;
 // Tính S % MOD: (v1 % MOD) * (v2 % MOD) % MOD
 sum_val = ((v1 % MOD) * (v2 % MOD)) % MOD;
 // Ghi kết quả
 fo << an << "\n";
 fo << sum_val << endl;
 fi.close();
 fo.close();
 return 0;
}
Bài 2. Tam giác vuông
#include 
#include 
using namespace std;
typedef long long ll;
void solve() {
 ifstream fi("TRI.INP");
 ofstream fo("TRI.OUT");
 ll a;
 if (!(fi >> a)) return;
 if (a == 0) {
 fo << 0 << endl;
 return;
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
 }
 ll temp = a;
 ll count4k1 = 1;
 // Phân tích thừa số nguyên tố của a
 for (ll i = 2; i * i <= temp; ++i) {
 if (temp % i == 0) {
 int exponent = 0;
 while (temp % i == 0) {
 exponent++;
 temp /= i;
 }
 // Nếu là số nguyên tố dạng 4k + 1
 if (i % 4 == 1) {
 // a^2 sẽ có số mũ là 2 * exponent
 count4k1 *= (2 * exponent + 1);
 }
 }
 }
 // Nếu còn lại một thừa số nguyên tố lớn hơn căn(a)
 if (temp > 1) {
 if (temp % 4 == 1) {
 count4k1 *= (2 * 1 + 1); // (2 * 1 + 1) = 3
 }
 }
 // Tổng số cặp (x, y) nguyên là 4 * count4k1
 // Trừ đi 2 điểm nằm trên trục hoành (a, 0) và (-a, 0)
 ll result = 4 * count4k1 - 2;
 fo << result << endl;
 fi.close();
 fo.close();
}
 DeThiTinHoc.net Bộ 10 Đề thi Học sinh giỏi cấp Trường Tin học Lớp 12 (Có đáp án) - DeThiTinHoc.net
int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 solve();
return 0;
}
Bài 3. Lưới ô vuông
C++
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int main() {
 ifstream fi("GRID.INP");
 ofstream fo("GRID.OUT");
 ll m, n, a, d, K;
 if (!(fi >> m >> n >> a >> d >> K)) return 0;
 // Khởi tạo lưới và mảng cộng dồn theo cột
 // grid[i][j] lưu giá trị tại hàng i, cột j
 vector> grid(m + 1, vector(n + 1));
 for (ll i = 1; i <= m; ++i) {
 for (ll j = 1; j <= n; ++j) {
 ll t; // Thứ tự điền số
 if (i % 2 != 0) {
 t = (i - 1) * n + j; // Hàng lẻ: trái sang phải
 } else {
 t = (i - 1) * n + (n - j + 1); // Hàng chẵn: phải sang trái
 }
 grid[i][j] = a + (t - 1) * d;
 }
 DeThiTinHoc.net