10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường

 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Mở file theo yêu cầu đề bài
// freopen("RBPOINT.INP", "r", stdin);
// freopen("RBPOINT.OUT", "w", stdout);
int n;
if (!(cin >> n)) return 0;
vector b(n), r(n);
// Nhập tọa độ n điểm xanh
for (int i = 0; i > b[i];
// Nhập tọa độ n điểm đỏ
for (int i = 0; i > r[i];
// Sắp xếp hai mảng tọa độ
sort(b.begin(), b.end());
sort(r.begin(), r.end());
int i = 0, j = 0;
int min_dist = 2e9; // Khởi tạo giá trị lớn (tọa độ tối đa 10^9)
// Duyệt qua hai mảng bằng hai con trỏ
while (i < n && j < n) {
 int current_dist = abs(b[i] - r[j]);
 if (current_dist < min_dist) {
 min_dist = current_dist;
 }
 // Nếu điểm xanh nhỏ hơn điểm đỏ, tăng con trỏ xanh để thu hẹp khoảng cách
 if (b[i] < r[j]) {
 i++;
 } else {
 // Ngược lại, tăng con trỏ đỏ
 j++;
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 }
 // Nếu tìm thấy khoảng cách bằng 0 thì đây là nhỏ nhất tuyệt đối
 if (min_dist == 0) break;
 }
 // Xuất kết quả duy nhất là khoảng cách nhỏ nhất
 cout << min_dist << endl;
 return 0;
}
Bài 3 (4 điểm): DANCING
C++
#include 
#include 
#include 
#include 
using namespace std;
// Hàm giải quyết việc ghép cặp cho một hướng cụ thể
// listA: những người muốn nhảy với người thấp hơn (lưu giá trị tuyệt đối)
// listB: những người muốn nhảy với người cao hơn (lưu giá trị tuyệt đối)
int countPairs(vector& wantLower, vector& wantHigher) {
 sort(wantLower.begin(), wantLower.end());
 sort(wantHigher.begin(), wantHigher.end());
 int count = 0;
 int i = 0; // Con trỏ cho người muốn nhảy với người cao hơn
 int j = 0; // Con trỏ cho người muốn nhảy với người thấp hơn
 while (i < wantHigher.size() && j < wantLower.size()) {
 // Nếu người muốn nhảy với người cao hơn thực sự thấp hơn người kia
 if (wantHigher[i] < wantLower[j]) {
 count++;
 i++;
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 j++;
 } else {
 // Nếu không, người "muốn nhảy với người thấp hơn" này quá thấp, 
 // không thể ghép với ai trong danh sách wantHigher từ vị trí i trở đi
 j++;
 }
 }
 return count;
}
int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // freopen("DANCING.INP", "r", stdin);
 // freopen("DANCING.OUT", "w", stdout);
 int n;
 if (!(cin >> n)) return 0;
 vector boyHigher, boyLower;
 vector girlHigher, girlLower;
 for (int i = 0; i < n; i++) {
 int h; cin >> h;
 if (h > 0) boyHigher.push_back(h);
 else boyLower.push_back(abs(h));
 }
 for (int i = 0; i < n; i++) {
 int h; cin >> h;
 if (h > 0) girlHigher.push_back(h);
 else girlLower.push_back(abs(h));
 }
 // Tổng số cặp = (Trai muốn thấp + Gái muốn cao) + (Gái muốn thấp + Trai muốn cao)
 int total = countPairs(boyLower, girlHigher) + countPairs(girlLower, boyHigher);
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 cout << total << endl;
 return 0;
}
Bài 4 (3 điểm): FWORD
C++
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
void solve() {
 // Tối ưu nhập xuất
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int n, m, k;
 ll x;
 if (!(cin >> n >> m >> k >> x)) return;
 string s;
 cin >> s;
 vector options(m);
 for (int i = 0; i < m; ++i) {
 cin >> options[i];
 // Sắp xếp các gợi ý theo thứ tự từ điển để đảm bảo thứ tự từ tạo ra
 sort(options[i].begin(), options[i].end());
 }
 // Chuyển X sang chỉ số bắt đầu từ 0
 x--;
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 // Tính toán các chữ cái cho từng vị trí mờ
 // Ta duyệt ngược từ vị trí mờ cuối cùng để xử lý X
 vector replacement(m);
 for (int i = m - 1; i >= 0; --i) {
 replacement[i] = options[i][x % k];
 x /= k;
 }
 // Thay thế các dấu # vào xâu gốc
 int current_m = 0;
 for (int i = 0; i < n; ++i) {
 if (s[i] == '#') {
 s[i] = replacement[current_m++];
 }
 }
 cout << s << endl;
}
int main() {
 // Bỏ chú thích nếu nộp bài cần đọc ghi file
 // freopen("FWORD.INP", "r", stdin);
 // freopen("FWORD.OUT", "w", stdout);
 solve();
 return 0;
}
Bài 5 (2 điểm): LIBRARY
C++
#include 
#include 
#include 
using namespace std;
/**
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 * Bài 5: LIBRARY
 * Sử dụng DFS để tìm các thành phần liên thông và chọn chi phí nhỏ nhất trong mỗi vùng.
 */
const long long INF = 1e18;
vector adj[100005];
long long a[100005];
bool visited[100005];
long long min_cost_in_component;
// Hàm duyệt DFS để tìm tất cả các thành phố trong một thành phần liên thông
void dfs(int u) {
 visited[u] = true;
 // Cập nhật chi phí nhỏ nhất tìm thấy trong thành phần liên thông hiện tại
 if (a[u] < min_cost_in_component) {
 min_cost_in_component = a[u];
 }
 for (int v : adj[u]) {
 if (!visited[v]) {
 dfs(v);
 }
 }
}
int main() {
 // Tối ưu tốc độ nhập xuất dữ liệu
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // Đọc từ file theo yêu cầu (bỏ chú thích nếu nộp bài thực tế)
 // freopen("LIBRARY.INP", "r", stdin);
 // freopen("LIBRARY.OUT", "w", stdout);
 int n, m;
 if (!(cin >> n >> m)) return 0;
 // Nhập chi phí xây dựng tại từng thành phố
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 for (int i = 1; i <= n; i++) {
 cin >> a[i];
 }
 // Nhập các tuyến đường
 for (int i = 0; i < m; i++) {
 int u, v;
 cin >> u >> v;
 adj[u].push_back(v);
 adj[v].push_back(u);
 }
 long long total_min_cost = 0;
 // Duyệt qua tất cả các thành phố để xử lý từng thành phần liên thông
 for (int i = 1; i <= n; i++) {
 if (!visited[i]) {
 min_cost_in_component = INF;
 dfs(i);
 // Cộng chi phí rẻ nhất của vùng này vào tổng chi phí
 total_min_cost += min_cost_in_component;
 }
 }
 // In kết quả cuối cùng
 cout << total_min_cost << endl;
 return 0;
}
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
 ĐỀ SỐ 3
 SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ THI CHỌN HỌC SINH GIỎI CẤP TRƯỜNG
 ĐỒNG THÁP MÔN: TIN HỌC 12
 Thời gian: 180 phút, không kể thời gian phát đề
 Tổng quan đề thi
 Tên tệp Tên tệp Tên tệp 
 Tên bài
 chương trình dữ liệu vào dữ liệu ra
Bài 1. Phương trình bậc hai PTB2.* PTB2.INP PTB2.OUT
Bài 2. Đoàn xe qua cầu DOANXE.* DOANXE.INP DOANXE.OUT
Bài 3. Vận chuyển VANCHUYEN.* VANCHUYEN.INP VANCHUYEN.OUT
Ghi chú: Kí tự * là phần mở rộng của tệp chương trình tùy theo ngôn ngữ lập trình (ngôn 
ngữ C++ là.cpp, ngôn ngữ Python là.py). Thời gian thực hiện chương trình không quá 01 
giây.
Bài 1. (7,0 điểm) PHƯƠNG TRÌNH BẬC HAI
 Sau khi học phương pháp giải phương trình bậc hai, các bạn học sinh được thầy giáo cho 
các bài tập để luyện tập. Các học sinh rất hào hứng đua nhau giải các bài tập xem ai hoàn 
thành sớm nhất. Để tăng thêm phần hấp dẫn, thầy giáo đã yêu cầu các học sinh làm bài toán 
ngược lại: cho trước n số nguyên dương đôi một khác nhau u1, u2,,un, hãy tìm ba số khác 
nhau trong dãy số đã cho làm ba hệ số a, b, c để phương trình bậc hai ax2 + bx + c = 0 có 
nghiệm là -1. Khi bắt tay vào làm bài, các học sinh phát hiện ra rằng có rất nhiều cách chọn 
ra các bộ ba hệ số a, b, c thỏa điều kiện và các em muốn đếm xem có tất cả bao nhiêu cách 
chọn như thế.
Yêu cầu: Hãy cho biết có bao nhiêu cách chọn ba phần tử khác nhau trong dãy số đã cho làm 
ba hệ số a,b,c để phương trình bậc hai ax2 + bx + c = 0 có nghiệm là -1. 
Dữ liệu vào: Cho từ tệp văn bản PTB2.INP có dạng:
- Dòng thứ nhất ghi số nguyên dương n(3 ≤ n ≤ 105);
 9
- Dòng thứ hai ghi n số nguyên dương u1, u2,,un (0 < ui ≤ 10 , i = 1..n; ui ≠ uj ∀i ≠ j).
Các số trên cùng một dòng được ghi cách nhau môt dấu cách.
Kết quả: Ghi ra tệp văn bản PTB2.OUT gồm một dòng ghi một số nguyên là số cách tìm 
được.
Ví dụ:
 PTB2.INP PTB2.OUT
 6 2
 42137510
Giải thích: Có 2 cách chọn:
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
Cách 1: a = 2, b = 7, c = 5; phương trình 2x2 + 7x + 5 = 0 có nghiệm x = -1
Cách 2: a = 5, b = 7, c = 2; phương trình 5x2 + 7x + 2 = 0 có nghiệm x = -1
Giới hạn dữ liệu:
- Có 70% số test ứng với 70% số điểm có giá trị n ≤ 300;
- Có 20% số test ứng với 20% số điểm có giá trị n ≤ 3000;
- Có 10% số test ứng với 10% số điểm có giá trị n ≤ 105, ui ≤ n.
Bài 2. (7,0 điểm) ĐOÀN XE QUA CẦU
Trên tuyến đường một chiều, tình trạng giao thông trở nên đông đúc. Để đảm bảo an toàn, cơ 
quan chức năng phân nhóm cho các xe qua cầu. Các xe phải di chuyển tuần tự theo nhóm 
(nghĩa là nhóm i chỉ được di chuyển sau khi toàn bộ xe của nhóm thứ i -1 đã qua cầu và các 
xe không được phép vượt nhau), tổng trọng lượng của các xe trong nhóm không được vượt 
quá tải trọng của cầu. Thời gian qua cầu của mỗi nhóm phụ thuộc vào xe có vận tốc thấp 
nhất trong nhóm
Có n xe đến cầu, các xe được đánh số từ 1 đến n, 푒 thứ i có trọng lượng wi, chạy với vận tốc 
v푖. Biết cầu có tải trọng P, chiều dài L. Giả thiết rằng P > w푖∀i = 1.n.
Yêu cầu: Bỏ qua khoảng cách giữa các xe, hãy tìm phương án tách đoàn xe thành từng nhóm 
để toàn bộ xe qua cầu được đảm bảo an toàn với tổng thời gian nhỏ nhất.
Dữ liệu vào: Cho từ tệp văn bản DOANXE.INP có dạng:
- Dòng đầu ghi ba số nguyên n,P,L(1 ≤ n ≤ 1000,1 ≤ P ≤ 100,1 ≤ L ≤ 103);
- Dòng thứ i trong n dòng tiếp theo ghi hai số nguyên w푖,v푖(1 ≤ w푖 ≤ P,1 ≤ v푖 ≤ 100). Các 
số trên cùng một dòng được ghi cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản DOANXE.OUT gồm một dòng ghi một số thực là thời gian nhỏ 
nhất tìm được (làm tròn 2 chữ số thập phân).
Ví dụ:
DOANXE.INP DOANXE.OUT Giải thích
10100100 24.33 - Nhóm 1: Xe I - Thời gian qua cầu: 4.00
4025 - Nhóm 2: Xe 2,3 - Thời gian qua cầu: 5.00
5020 - Nhóm 3: Xe 4, 5, 6 - Thời gian qua cầu: 10.00
5020 - Nhóm 4: Xe 7,8 - Thời gian qua cầu: 3.33
7010 - Nhóm 5: Xe 9,10 - Thời gian qua cầu: 2.00
1250 - Tổng thời gian: 
970 4.00 + 5.00 + 10.ô + 3.33 + 2.00 = 24.33
4930
3835
2750
1970
 DeThiHay.net 10 Đề thi và đáp án kỳ thi Học sinh giỏi Tin học 12 cấp Trường - DeThiHay.net
Giới hạn dữ liệu:
- Có 60% số test ứng với 60% số điểm có giá trị n ≤ 10;
- Có 30% số test ứng với 30% số điểm có giá trị n ≤ 100;
- Có 10% số test ứng với 10% số điểm có giá trị n ≤ 1000.
Bài 3. (6,0 điểm) VẬN CHUYỂN
 Ngày nay, việc mua sắm trực tuyến trở nên phổ biến. Chúng ta có thể chọn đặt mua 
những sản phẩm thông qua các kênh bán hàng trực tuyến. Sau đó các đơn vị vận chuyển sẽ 
nhận kiện hàng và giao đến tận nhà.
 Một đơn vị vận chuyển có n trung tâm trung chuyển được đánh số từ 1 đến n. Giữa hai 
trung tâm trung chuyển được nối với nhau tối đa một tuyến đường hai chiều. Có tất cả m 
tuyến đường, tuyến dường thứ i nối hai trung tậm ai và bi có khoảng cách là ci(i = 1..m).
Yêu cầu: Hãy xác định tổng khoảng cách ngắn nhất để vận chuyển một kiện hàng từ trung 
tâm trung chuyển s đến trung tâm trung chuyển t.
Dữ liệu vào: Cho từ tệp văn bản VANCHUYEN.INP có dạng:
- Dòng thứ nhất ghi bốn số nguyên n,m,s,t(1 ≤ s,t ≤ n ≤ 105,1 ≤ m ≤ 105,s ≠ t);
- Dòng thứ i trong m dòng tiếp theo ghi ba số nguyên dương a푖,b푖,c푖(1 ≤ a푖,b푖 ≤ n, a푖 ≠ b푖
 9
,0 < c푖 ≤ 10 ).
Các số trên cùng một dòng dıroc ghi cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản VANCHUYEN.OUT gồm một dòng ghi một số nguyên dương 
là tổng khoảng cách ngắn nhất để vận chuyển kiện hàng từ trung tâm trung chuyển s đến 
trung tâm trung chuyển t.
Ví dụ:
 VANCHUYEN.INP VANCHUYEN.OUT
 5715 10
 123
 148
 235
 244
 355
 438
 453
 DeThiHay.net