Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án)

 Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
Bài 2: Tổng chéo
C++
#include 
#include 
#include 
#include 
using namespace std;
// Hằng số Modulo và Nghịch đảo Modulo của 2
const long long MOD = 1e9 + 7;
const long long INV_2 = 500000004;
// Hàm tính giá trị tại ô (i, j)
long long get_value(long long i, long long j, long long N) {
 // i, j là 1-based index (từ 1 đến N)
 return (i - 1) * N + j;
}
// Hàm tính tổng cấp số cộng S = (k/2) * (a1 + ak) (Modulo arithmetic)
long long sum_arithmetic_series(long long k, long long a1, long long ak) {
 // k: số lượng phần tử
 // a1, ak: phần tử đầu và cuối (đã được lấy modulo)
 // Sum_term = (a1 + ak) % MOD
 long long sum_term = (a1 + ak) % MOD;
 // Result = (k % MOD) * (sum_term) * (INV_2) % MOD
 long long result = (k % MOD * sum_term) % MOD;
 return (result * INV_2) % MOD;
}
void solve_bai_2() {
 long long N, Q;
 // Đọc N (kích thước bảng) và Q (số lượng truy vấn)
 if (!(cin >> N >> Q)) return;
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
for (long long q = 0; q < Q; ++q) {
 long long x, y;
 // Đọc truy vấn (x, y)
 if (!(cin >> x >> y)) break;
 // --- 1. Tính tổng Đường chéo Chính (i - j = x - y) ---
 long long diff = x - y;
 // Số lượng phần tử L_chinh
 long long L_chinh = N - abs(diff);
 // Hàng bắt đầu và kết thúc
 long long i_start_chinh = max(1LL, 1 + diff);
 long long i_end_chinh = min(N, N + diff);
 // Tính giá trị đầu và cuối
 long long a1_chinh = get_value(i_start_chinh, i_start_chinh - diff, N);
 long long ak_chinh = get_value(i_end_chinh, i_end_chinh - diff, N);
 long long S_chinh = sum_arithmetic_series(L_chinh, a1_chinh, ak_chinh);
 // --- 2. Tính tổng Đường chéo Phụ (i + j = x + y) ---
 long long sum = x + y;
 // Số lượng phần tử L_phu
 long long L_phu = N - abs(sum - (N + 1));
 // Hàng bắt đầu và kết thúc
 long long i_start_phu = max(1LL, sum - N);
 long long i_end_phu = min(N, sum - 1);
 // Tính giá trị đầu và cuối
 long long a1_phu = get_value(i_start_phu, sum - i_start_phu, N);
 long long ak_phu = get_value(i_end_phu, sum - i_end_phu, N);
 long long S_phu = sum_arithmetic_series(L_phu, a1_phu, ak_phu);
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
 // --- 3. Tính và in kết quả cuối cùng ---
 // Tổng hai đường chéo
 long long S_total = (S_chinh + S_phu) % MOD;
 // Giá trị trùng lặp A[x][y]
 long long A_xy = get_value(x, y, N) % MOD;
 // Kết quả = S_chinh + S_phu - A[x][y] (vì A[x][y] bị tính 2 lần)
 // Cộng thêm MOD để đảm bảo kết quả luôn dương trước khi lấy modulo cuối
 long long result = (S_total - A_xy + MOD) % MOD;
 cout << result << "\n";
 }
}
int main() {
 // Tối ưu tốc độ I/O
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 solve_bai_2();
 return 0;
}
Bài 3: Đoạn con 3
C++
#include 
#include 
#include 
#include 
using namespace std;
// Sử dụng long long cho tổng để tránh tràn số (vì |Ai| <= 10^9 và N <= 10^5)
typedef long long ll;
const ll NEG_INF = numeric_limits ::min() / 2; // Dùng một giá trị âm rất lớn
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
void solve_bai_3() {
 int N;
 if (!(cin >> N)) return;
 vector A(N + 1);
 for (int i = 1; i <= N; ++i) {
 cin >> A[i];
 }
 // P[k][i]: Max sum của k đoạn con không giao nhau, với đoạn con thứ k KẾT THÚC tại i.
 // M[k][i]: Max sum của k đoạn con không giao nhau, trong A[1..i].
 // Index 0 không dùng. Khởi tạo với giá trị âm rất lớn.
 vector > P(4, vector (N + 1, NEG_INF));
 vector > M(4, vector (N + 1, NEG_INF));
 // Khởi tạo M[k][0] = NEG_INF
 for (int i = 1; i <= N; ++i) {
 // --- Tính P[1][i] và M[1][i] (1 đoạn con) ---
 // P1[i]: Max sum 1 đoạn, kết thúc tại i (Kadane)
 // max(0, P1[i-1]) tương đương với max(0, P1[i-1]) vì 0 >= NEG_INF
 P[1][i] = A[i] + max(0LL, P[1][i-1]); 
 // M1[i]: Max sum 1 đoạn trong A[1..i]
 M[1][i] = max(M[1][i-1], P[1][i]);
 // --- Tính P[2][i] và M[2][i] (2 đoạn con) ---
 // P2[i]: Max sum 2 đoạn, đoạn 2 kết thúc tại i.
 // Option 1: Kéo dài đoạn 2: P2[i-1] + A[i]
 // Option 2: Bắt đầu đoạn 2 tại i: M1[i-1] + A[i] (M1[i-1] là max sum của đoạn 1 trong 
A[1..i-1])
 if (i >= 2) {
 P[2][i] = A[i] + max(P[2][i-1], M[1][i-1]);
 }
 M[2][i] = max(M[2][i-1], P[2][i]);
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
 // --- Tính P[3][i] và M[3][i] (3 đoạn con) ---
 // P3[i]: Max sum 3 đoạn, đoạn 3 kết thúc tại i.
 // Option 1: Kéo dài đoạn 3: P3[i-1] + A[i]
 // Option 2: Bắt đầu đoạn 3 tại i: M2[i-1] + A[i] (M2[i-1] là max sum của 2 đoạn trong 
A[1..i-1])
 if (i >= 3) {
 P[3][i] = A[i] + max(P[3][i-1], M[2][i-1]);
 }
 M[3][i] = max(M[3][i-1], P[3][i]);
 }
 // Kết quả cuối cùng là Max sum của 3 đoạn con không giao nhau trong A[1..N]
 // Đây chính là M[3][N]
 cout << M[3][N] << endl;
}
int main() {
 // Tối ưu tốc độ I/O
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 solve_bai_3();
 return 0;
}
Bài 4: NUM9
C++
#include 
using namespace std;
struct Triple {
 long long val;
 vector idx;
};
int main() {
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector a(n);
for (int i = 0; i > a[i];
// Tạo mảng giá trị + chỉ số
vector > arr;
for (int i = 0; i < n; i++) arr.push_back({a[i], i});
sort(arr.begin(), arr.end());
// Lấy 20 phần tử nhỏ nhất và 20 phần tử lớn nhất
vector > cand;
for (int i = 0; i < min(20, n); i++) cand.push_back(arr[i]);
for (int i = max(0, n-20); i < n; i++) cand.push_back(arr[i]);
int m = cand.size();
vector triples;
// Sinh tất cả bộ ba khác nhau
for (int i = 0; i < m; i++) {
 for (int j = i+1; j < m; j++) {
 for (int k = j+1; k < m; k++) {
 long long val = cand[i].first * cand[j].first * cand[k].first;
 triples.push_back({val, {cand[i].second, cand[j].second, cand[k].second}});
 }
 }
}
// Sắp xếp giảm dần theo giá trị tích
sort(triples.begin(), triples.end(), [](const Triple &x, const Triple &y){
 return x.val > y.val;
});
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
 long long ans = LLONG_MIN;
 int sz = triples.size();
 // Chọn 3 bộ ba khác nhau (9 chỉ số khác nhau)
 for (int i = 0; i < sz; i++) {
 for (int j = i+1; j < sz; j++) {
 for (int k = j+1; k < sz; k++) {
 set used;
 for (int x : triples[i].idx) used.insert(x);
 for (int x : triples[j].idx) used.insert(x);
 for (int x : triples[k].idx) used.insert(x);
 if ((int)used.size() == 9) {
 long long total = triples[i].val + triples[j].val + triples[k].val;
 ans = max(ans, total);
 }
 }
 }
 }
 cout << ans << "\n";
 return 0;
}
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
 ĐỀ SỐ 4
 HỘI THI TIN HỌC TRẺ ĐỀ THI VÒNG SƠ KHẢO 
 THÀNH PHỐ HÀ NỘI BẢNG C
 Thời gian: 90 phút (không kể thời gian giao đề)
Bài 1: Tổng hiệu
Với 2 số nguyên A và B, ta tính A + B và A - B. Từ tổng và hiệu của hai số ta có thể tìm 
được A và B.
Yêu cầu: Cho tổng và hiệu của hai số, tìm hai số đó.
Input
- Dòng 1: chứa số A + B;
- Dòng 2: chứa số A - B.
Output
- Dòng 1: ghi A;
- Dòng 2: ghi B.
 Input Output
 0 -100
 -200 100
Subtask 1 (80% điểm): |A|, |B| ≤ 109;
Subtask 2 (20% điểm): |A|, |B| ≤ 10100;
Bài 2: BSR
Cho bảng số nguyên không âm kích thước m x n, các hàng được đánh số từ 1 đến m từ trên 
xuống, các cột được đánh số từ 1 đến n từ trái sang. Ô nằm ở hàng i (1 ≤ i ≤ m), cột j (1 ≤ j ≤ 
n) được gọi là ô (i, j).
Một bảng số nguyên không âm được gọi là bảng đẹp nếu tổng các số trong bảng chia hết cho 
9.
 3 3 3
Ví dụ, bảng 1 2 6 là một bảng đẹp.
Yêu cầu: Cho bảng số nguyên không âm kích thước m x n, hãy đếm số bộ chỉ số (x, y, u, v) 
sao cho bảng số con có ô trái trên (x, y) và ô phải dưới (u, v) là một bảng đẹp (x ≤ u; y ≤ v).
Input:
- Dòng đầu chứa số nguyên m, n: 
 9
- m dòng sau, dòng thứ i gồm n số nguyên ai,1, ai,2, , ai,n (ai,j ≤ 10 ).
Output:
- Gồm một dòng chứa một số nguyên là số số bộ chỉ số (x, y, u, v) thỏa mãn.
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
 Input Output
 2 3 5
 3 3 3
 1 2 6
Subtask 1 (50% điểm): m, n ≤ 5;
Subtask 2 (25% điểm): m, n ≤ 50;
Subtask 3 (25% điểm): m, n ≤ 500.
Bài 3: Quay súc sắc
Một con súc sắc là một hình hộp ba chiều có kích thước 1 x 1 x 1 và 6 mặt như minh họa ở 
Hình 1:
- Mặt trên
- Mặt dưới: đối diện với mặt trên
- Mặt phải
- Mặt trái: đối diện với mặt phải
- Mặt trước
- Mặt sau: Đối diện với mặt trước
Mỗi mặt của con súc sắc được đánh số là một số nguyên. Trong bài toán này, chúng ta xét 
một loại súc sắc đặc biệt trong đó các mặt được đánh số 1,2, hoặc 3.
 Hình 1: Minh họa một con súc sắc
Xét một hình hộp D có kích thước 3 x 3 x 3 chứa 27 con súc sắc có số hiệu từ 1 đến 27. Số 
hiệu của các con súc sắc nằm trong hình hộp D được đánh từ trái qua phải, từ trước ra sau và 
từ dưới lên trên. Tức là, con súc sắc có đỉnh trái-trước-dưới trùng với đỉnh trái- trước-dưới 
 De-Thi.com Bộ đề ôn thi Tin Học Trẻ các vòng Thành phố Hà Nội (Có đáp án) - De-Thi.com
của hình hộp D có số hiệu là 1, và con súc sắc có đỉnh phải-sau-trên trùng với đỉnh phải-sau-
trên của hình hộp D có số hiệu 27 (xem Hình 2 để biết thêm chi tiết).
 Hình 2: Số hiệu các con xúc sắc nhìn thấy từ ba mặt trước, phải, trên của hình hộp D.
Hai con súc sắc được gọi là nằm kề nhau trong D nếu như chúng có hai mặt được áp sát vào 
nhau. Ví dụ, con súc sắc nằm ở tâm của hình hộp D có số hiệu 14 nằm liền kề với 6 con súc 
sắc khác với số hiệu 5, 11, 1315, 17, 23. Hình hộp D được gọi là thống nhất nếu như hai mặt 
áp vào nhau của hai con súc sắc nằm kề nhau thì có giá trị giống nhau. Chúng ta được phép 
xoay các con súc sắc nằm trong hình hộp D theo các hướng khác nhau với số lần xoay không 
hạn chế. Hãy tìm cách xoay ít con súc sắc nhất để hình hộp D là thống nhất.
Input
Gồm 27 dòng. Dòng thứ i chứa 6 số nguyên T, D, R, L, F, B mô tả cách đánh số các mặt của 
con súc sắc thứ 푖, trong đó: T : số hiệu của mặt trên của con súc sắc; D : số hiệu của mặt dưới 
của con súc sắc; R: số hiệu của mặt phải của con súc sắc; L: số hiệu của mặt trái của con súc 
sắc; F : số hiệu của mặt trước của con súc sắc; B: số hiệu của mặt sau của con súc sắc
Output
Ghi một số nguyên duy nhất là số lượng con súc sắc phải xoay nhỏ nhất tìm được để hình 
hộp D là thống nhất. Nếu không tồn tại bất cứ cách xoay nào để D là thống nhất, thì ghi ra số 
-1.
 Input Output
2 1 2 1 1 2 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
 De-Thi.com