11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội

 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 ll N_prime = N % 200;
 // Nếu N=200, N_prime=0. S(200) = 200 * 201 / 2 = 100 * 201 = 20100.
 // 20100 % 100 = 0.
 // Nếu N_prime = 0, ta cần coi nó là 200 để tính S(200).
 if (N_prime == 0) {
 N_prime = 200;
 // Xử lý trường hợp N = 0 (không xảy ra vì N là số dòng >= 1)
 if (N == 0) {
 cout << 0 << endl;
 return;
 }
 }
 // Tính S(N_prime) = N_prime * (N_prime + 1) / 2.
 // Vì N_prime <= 200, N_prime * (N_prime + 1) <= 200 * 201 = 40200, 
 // vẫn nằm trong phạm vi int/long long.
 ll numerator = N_prime * (N_prime + 1);
 ll S_N_prime;
 // Đảm bảo phép chia cho 2 luôn chính xác bằng cách chia số chẵn cho 2 trước.
 if (N_prime % 2 == 0) {
 S_N_prime = (N_prime / 2) * (N_prime + 1);
 } else {
 S_N_prime = N_prime * ((N_prime + 1) / 2);
 }
 // Kết quả cuối cùng là S(N) % 100
 ll result = S_N_prime % 100;
 cout << result << "\n";
}
int main() {
 // Tối ưu tốc độ I/O
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 solve();
 return 0;
}
Bài 4: FIBO100
C++
#include 
#include 
#include 
using namespace std;
// Sử dụng long long cho N vì N <= 10^12
typedef long long ll;
// Chu kỳ Pisano cho m=100 là 300
const int PISANO_PERIOD = 300;
const int MOD = 100;
// Mảng lưu trữ 302 phần tử đầu tiên của F_i mod 100
// F[i] lưu F_i mod 100 (i từ 1 đến 302)
vector F_mod_100(PISANO_PERIOD + 3); 
// Hàm tính trước dãy Fibonacci mod 100
void precompute_fibo_mod_100() {
 // F_1 = 1, F_2 = 1
 F_mod_100[1] = 1;
 F_mod_100[2] = 1;
 for (int i = 3; i <= PISANO_PERIOD + 2; ++i) {
 // F_i = (F_{i-1} + F_{i-2}) mod 100
 F_mod_100[i] = (F_mod_100[i - 1] + F_mod_100[i - 2]) % MOD;
 }
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
}
void solve() {
 ll N;
 if (!(cin >> N)) return;
 // 1. Tính trước dãy F_i mod 100 (tối đa F_302)
 precompute_fibo_mod_100();
 // 2. Sử dụng công thức tổng: S(N) = F_{N+2} - 1 (mod 100)
 // Tìm chỉ số I cho F_{N+2} trong chu kỳ 300
 // Ta cần (N+2) mod 300. 
 // Nếu N+2 là bội của 300 (ví dụ N+2=300, 600, ...), ta cần chỉ số 300.
 // Chỉ số cho F_{N+2}
 ll index_raw = N + 2;
 // I = (index_raw - 1) % 300 + 1: Đảm bảo chỉ số I nằm trong [1, 300]
 ll I = (index_raw - 1) % PISANO_PERIOD + 1;
 // 3. Tính F_I mod 100 (tức là F_{N+2} mod 100)
 int F_I_mod_100 = F_mod_100[I];
 // 4. Tính kết quả: S(N) mod 100 = (F_{N+2} - 1) mod 100
 // Phép trừ phải đảm bảo kết quả dương trước khi lấy modulo cuối
 int result = (F_I_mod_100 - 1 + MOD) % MOD;
 // Ví dụ: N=4. I = (4+2-1)%300 + 1 = 6. F_6=8. S(4)=1+1+2+3=7. 
 // F_6 - 1 = 7. 7 % 100 = 7. (Chuẩn)
 cout << result << "\n";
}
int main() {
 // Tối ưu tốc độ I/O
 ios_base::sync_with_stdio(false);
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 cin.tie(NULL);
 solve();
 return 0;
}
Bài 5: Đếm số chia hết
C++
#include 
#include 
#include 
using namespace std;
// Sử dụng long long vì N, A, B <= 10^12
typedef long long ll;
// Hàm tìm Ước chung lớn nhất (GCD) bằng thuật toán Euclidean
ll gcd(ll a, ll b) {
 while (b) {
 a %= b;
 swap(a, b);
 }
 return a;
}
// Hàm tìm Bội chung nhỏ nhất (LCM)
// Lưu ý: Phép tính (a / g) * b được sử dụng để tránh tràn số.
ll lcm(ll a, ll b) {
 if (a == 0 || b == 0) return 0;
 ll common_divisor = gcd(a, b);
 // Kiểm tra xem (a / common_divisor) * b có tràn số hay không.
 // Vì kết quả cuối cùng BCNN chỉ cần để chia N (N <= 10^12), 
 // nên nếu BCNN lớn hơn N, ta coi như nó rất lớn (hoặc dùng N+1)
 // để N / BCNN = 0.
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 // Nếu BCNN <= N, ta có thể tính.
 // Nếu a / gcd > N / b (chuyển vị để tránh chia): (a / common_divisor) > N / b
 // Nếu a * b / common_divisor > N
 // Do N, A, B <= 10^12, ta cứ tính và kiểm tra kết quả cuối cùng.
 // Ta sử dụng ll. Nếu kết quả tràn, nó sẽ bị sai nhưng N / BCNN sẽ bằng 0 nếu BCNN > N.
 // Nếu BCNN > N, phép chia N / BCNN = 0, nên kết quả không bị ảnh hưởng.
 // Ta chỉ cần lo lắng nếu BCNN < N nhưng lại bị tràn số.
 // Vì N <= 10^12, BCNN(A, B) chỉ cần tính chính xác nếu BCNN <= N.
 ll res;
 // Để tránh tràn số khi A * B > 10^18, ta chia trước rồi nhân
 if (common_divisor != 0) {
 // Kiểm tra BCNN có thể lớn hơn N không.
 // BCNN = (A / g) * B. 
 // Nếu (A / g) > N / B, thì BCNN > N.
 ll factor = a / common_divisor;
 if (b > N / factor && N > 0) { 
 // Nếu BCNN lớn hơn N, ta trả về giá trị lớn hơn N để phép chia N/BCNN cho kết 
quả 0.
 return N + 1; 
 }
 res = factor * b;
 } else {
 return 0; // Xử lý trường hợp A hoặc B là 0
 }
 return res;
}
void solve() {
 ll N, A, B;
 if (!(cin >> N >> A >> B)) return;
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 // 1. Tính số lượng chia hết cho A: |S_A|
 ll count_A = N / A;
 // 2. Tính số lượng chia hết cho B: |S_B|
 ll count_B = N / B;
 // 3. Tính số lượng chia hết cho cả A và B: |S_A ∩ S_B|
 // Số này là số lượng chia hết cho BCNN(A, B).
 ll L = lcm(A, B); // L = BCNN(A, B)
 ll count_intersection = N / L;
 // 4. Kết quả = |S_A| + |S_B| - 2 * |S_A ∩ S_B|
 // (Nguyên tắc bao hàm-loại trừ, loại bỏ phần giao nhau hai lần)
 ll result = count_A + count_B - 2 * count_intersection;
 cout << result << "\n";
}
int main() {
 // Tối ưu tốc độ I/O
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 solve();
 return 0;
}
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 ĐỀ SỐ 3
 HỘI THI TIN HỌC TRẺ ĐỀ THI VÒNG SƠ KHẢO 
 THÀNH PHỐ HÀ NỘI BẢNG B
 Thời gian: 90 phút (không kể thời gian giao đề)
Bài 1: MAXAA
Cho ba phép tính +, –, x và một số nguyên A hãy điền một trong ba phép tính vào dấu? trong 
biểu thức dưới đây để được B lớn nhất.
 A? A = B
Dữ liệu vào từ thiết bị vào chuẩn:
- Gồm một dòng chứa số nguyên A (-109 ≤ A ≤ 109).
Kết quả ghi ra thiết bị ra chuẩn:
- Gồm một dòng chứa số nguyên B lớn nhất tìm được.
Ví dụ:
 Dữ liệu vào Kết quả ra
 -5 25
Bài 2: Tổng chéo
Cho bảng số có kích thước N x N được điền số liên tiếp từ 1 đến N2, từ trái qua phải, từ trên 
xuống dưới. Ví dụ với N = 4, bảng số như sau:
 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16
Yêu cầu: cho vị trí một ô ở dòng thứ x và cột thứ y, hãy tính tổng hai đường chéo đi qua ô 
này.
Dữ liệu vào từ thiết bị vào chuẩn:
- Dòng đầu tiên chứa hai số nguyên dương N và Q (N ≤ 109; Q ≤ 105) mô tả kích thước của 
bảng số và số lượng truy vấn;
- Q dòng sau, mỗi dòng gồm hai số nguyên dương x và y (x, y ≤ N) mô tả một truy vấn là vị 
trí một ô ở dòng thứ x và cột thứ y.
Kết quả ghi ra thiết bị ra chuẩn:
- Gồm Q dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng. Vì kết quả 
có thể rất lớn nên chỉ cần in ra phần dư của kết quả cho 109 + 7.
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
Ví dụ:
 Dữ liệu vào Kết quả ra Giải thích
4 2 46 1 2 3 4 1 2 3 4
2 2 26
 5 6 7 8 5 6 7 8
1 3
 9 10 11 12 9 10 11 12
 13 14 15 16 13 14 15 16
Ràng buộc:
- Có 70% số test ứng với 70% số điểm có: N ≤ 100; Q = 1; 
- 20% số test khác ứng với 20% số điểm có: N ≤ 5000; Q ≤ 105;
- 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.
Bài 3: Đoạn con 3
Cho một dãy số nguyên A gồm N phần tử. Hãy tìm ba đoạn con liên tiếp (có ít nhất một phần 
tử) không giao nhau của dãy số sao cho tổng các phần tử của ba đoạn con này là lớn nhất.
Dữ liệu vào từ thiết bị vào chuẩn:
- Dòng đầu tiên gồm một số nguyên dương N (3 ≤ N ≤ 105) mô tả số phần tử của dãy số;
 9
- Dòng thứ hai gồm N số nguyên Ai (1 ≤ i ≤ N; | Ai| ≤ 10 ) mô tả các phần tử của dãy số.
Kết quả ghi ra thiết bị ra chuẩn:
- Gồm một số nguyên là kết quả của bài toán.
Ví dụ:
 Dữ liệu Kết quả Giải thích
7 10 (1 + 2) + (4 + 1) + (2) = 10
1 2 -3 4 1 -6 2
Ràng buộc: 
- Có 40% số test ứng với 40% số điểm có: N ≤ 102;
- 30% số test khác ứng với 30% số điểm có: N ≤ 103;
- 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.
Bài 4: NUM9
Cho dãy số nguyên a1, a2,  , an. Một cách chọn bộ 9 chỉ số, các chỉ số đôi một khác nhau, 
(i1, j1, k1, i2, j2, k2, i3, j3, k3) được gọi là tối ưu nếu giá trị ai1 × aj1 × ak1 + ai2 × aj2 × ak2 + ai3 × 
aj3 × ak3 đạt giá trị lớn nhất trong tất cả các cách chọn.
Ví dụ, với dãy 0,2,2,0,2, -1,1, - 1,0,0, thì cách chọn bộ 9 chỉ số (2,3,5,1,4,9,6,7,8) là tối ưu vì 
giá trị (2 × 2 × 2) + (0 × 0 × 0) + ((-1) × 1 × (-1)) = 9 là giá trị lớn nhất trong tất cả các cách 
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
chọn.
Yêu cầu: Cho dãy số nguyên a1, a2,  , an, hãy tìm giá trị cách chọn tối ưu.
Dữ liệu vào từ thiết bị vào chuẩn:
- Dòng đầu chứa hai số nguyên n (9 ≤ n ≤ 105);
 6
- Dòng thứ hai chứa n số nguyên a1, a2, . , an (|ai| ≤ 10 ).
Kết quả ghi ra thiết bị ra chuẩn:
- Gồm một dòng, chứa một số nguyên là giá trị của cách chọn tối ưu.
Ví dụ:
 Dữ liệu Kết quả
 10 9
 0 2 2 0 2 -1 1 -1 0 0
Ràng buộc:
- Có 50% số test ứng với 50% số điểm có: n = 9;
- 25% số test khác ứng với 25% số điểm có: n ≤ 18;
- 25% số test còn lại ứng với 25% số điểm không có ràng buộc gì thêm.
 ---------HẾT---------
 DeThiHay.net 11 Đề thi và Đáp án các vòng Tin Học Trẻ Hà Nội - DeThiHay.net
 ĐÁP ÁN
Bài 1: MAXAA
C++
#include 
#include 
#include 
using namespace std;
int main() {
 // Tối ưu tốc độ I/O
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // A: Số nguyên đầu vào. Dùng long long vì |A| <= 10^9.
 long long A; 
 // Đọc dữ liệu nhập vào
 if (!(cin >> A)) {
 return 0;
 }
 // Các kết quả có thể:
 long long B_cong = 2 * A;
 long long B_tru = 0;
 long long B_nhan = A * A;
 // Tìm giá trị B lớn nhất
 long long B_max = max({B_cong, B_tru, B_nhan});
 // In kết quả
 cout << B_max << endl;
 return 0;
}
 DeThiHay.net