Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết)

 Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
 return (root * root == n);
}
void solve() {
 string s;
 if (!(cin >> s)) return;
 long long max_cp = -1;
 string current_num = "";
 // Duyệt qua xâu để tách số
 for (int i = 0; i <= s.length(); ++i) {
 if (i < s.length() && isdigit(s[i])) {
 current_num += s[i];
 } else {
 if (!current_num.empty()) {
 // Loại bỏ số '0' vô nghĩa ở đầu
 size_t first_nonzero = current_num.find_first_not_of('0');
 if (string::npos != first_nonzero) {
 string filtered = current_num.substr(first_nonzero);
 // Chuyển sang long long (tối đa 18 chữ số nên dùng stoll)
 try {
 long long val = stoll(filtered);
 if (isPerfectSquare(val)) {
 if (val > max_cp) max_cp = val;
 }
 } catch (...) {
 // Phòng trường hợp số quá lớn vượt long long 
 // (dù đề bảo tối đa 18 chữ số)
 }
 }
 current_num = ""; // Reset để tìm số tiếp theo
 }
 }
 }
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
 cout << max_cp << endl;
}
int main() {
 // Tối ưu tốc độ nhập xuất
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // Mở file theo yêu cầu đề bài
 // freopen("BAI2.INP", "r", stdin);
 // freopen("BAI2.OUT", "w", stdout);
 solve();
 return 0;
}
Bài 3:
C++ 
#include 
#include 
#include 
using namespace std;
// Cấu trúc lưu trữ thông tin mượn sách
struct Request {
 int start;
 int end;
};
// Hàm so sánh để sắp xếp theo thời điểm trả sách (end) tăng dần
bool compareRequests(Request a, Request b) {
 return a.end < b.end;
}
int main() {
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
 // Tối ưu nhập xuất
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // Mở file (nếu nộp bài theo quy định thi)
 // freopen("BAI3.INP", "r", stdin);
 // freopen("BAI3.OUT", "w", stdout);
 int N;
 if (!(cin >> N)) return 0;
 vector list(N);
 for (int i = 0; i < N; ++i) {
 cin >> list[i].start >> list[i].end;
 }
 // Bước quan trọng: Sắp xếp theo thời điểm kết thúc
 sort(list.begin(), list.end(), compareRequests);
 int count = 0;
 int last_end_time = -1; // Lưu thời điểm kết thúc của yêu cầu cuối cùng được chọn
 for (int i = 0; i < N; ++i) {
 // Nếu thời điểm bắt đầu của yêu cầu này không giao với yêu cầu trước
 // (Tức là start > last_end_time)
 if (list[i].start > last_end_time) {
 count++;
 last_end_time = list[i].end; // Cập nhật mốc thời gian trả sách
 }
 }
 cout << count << endl;
 return 0;
}
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
Bài 4:
C++
#include 
#include 
#include 
#include 
using namespace std;
/**
 * Bài 4: Tìm số đặc biệt thứ N
 * N có thể lên tới 10^18 nên dùng kiểu dữ liệu long long.
 */
void solve() {
 long long n;
 if (!(cin >> n)) return;
 // Tập hợp các chữ số đặc biệt theo thứ tự
 // Tương ứng với dư: 1->1, 2->3, 3->5, 4->7, 0->9
 char digits[] = {'9', '1', '3', '5', '7'};
 string result = "";
 while (n > 0) {
 int remainder = n % 5;
 result += digits[remainder];
 // Nếu chia hết cho 5, ta mượn 1 đơn vị cho hàng tiếp theo
 if (remainder == 0) {
 n = (n / 5) - 1;
 } else {
 n = n / 5;
 }
 }
 // Vì ta tìm từ hàng đơn vị lên nên phải đảo ngược xâu
 reverse(result.begin(), result.end());
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
 cout << result << endl;
}
int main() {
 // Tối ưu nhập xuất cho dữ liệu lớn
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // freopen("BAI4.INP", "r", stdin);
 // freopen("BAI4.OUT", "w", stdout);
 solve();
 return 0;
}
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
 ĐỀ SỐ 4
 SỞ GIÁO DỤC & ĐÀO TẠO ĐỀ THI CHỌN HỌC SINH GIỎI THCS CẤP TỈNH 
 SÓC TRĂNG MÔN: TIN HỌC
 Thời gian: 150 phút (không kể thời gian giao đề)
 Tổng quan đề thi
 Tên bài Tên file File dữ liệu File kết quả
Bài 1 Nhà Toán học tài ba NGUYENTO.* NGUYENTO.INP NGUYENTO.OUT
Bài 2 Tìm người thân ADN.* ADN.INP ADN.OUT
Bài 3 Phân công công việc PHANCONG.* PHANCONG.INP PHANCONG.OUT
Bài 4 Tối ưu năng lực NANGLUC.* NANGLUC.INP NANGLUC.OUT
Lưu ý làm bài: 
- Dấu * trong tên file thay thế cho PAS, CPP, PY, SB3 tương ứng với thí sinh sử dụng ngôn 
ngữ lập trình Pascal, C++, Python, Scratch; 
- Riêng bài làm bằng Scratch không cần nhập/xuất từ file văn bản.
Bài 1: Nhà Toán học tài ba (5,0 điểm) 
Trong một ngôi làng nhỏ có tên là PrimeVille, người dân nơi đây có truyền thống tôn vinh 
những con số nguyên tố. Hằng năm, vào ngày lễ hội lớn nhất làng, dân làng sẽ tổ chức một 
cuộc thi để tìm ra những con số nguyên tố đặc biệt. Người chiến thắng sẽ được nhận danh 
hiệu “Nhà Toán Học Tài Ba”. Năm nay, bài toán mà trưởng làng đưa ra như sau: “Hãy tìm ra 
số nguyên tố nhỏ thứ K trong danh sách số nguyên tố tìm được từ N số nguyên mà ta đã 
chuẩn bị”. Em hãy viết chương trình để giúp dân làng tìm ra kết quả câu đố nhanh nhất. 
Dữ liệu: Vào từ file văn bản NGUYENTO.INP gồm: 
- Dòng đầu tiên ghi hai số nguyên N và K (1 ≤ N ≤ 105, 1 ≤ K < N); 
 9
- Dòng tiếp theo ghi N số nguyên Ai, (0 < Ai ≤ 10 ). 
Kết quả: Ghi ra file văn bản NGUYENTO.OUT: Một số nguyên duy nhất là số nguyên tố 
nhỏ thứ K tìm được, nếu không tìm được, in ra -1. 
Ví dụ:
 NGUYENTO.INP NGUYENTO.OUT
 10 3 5
 2 8 5 3 7 10 11 4 6 13
Chấm điểm: 
- Có 50% số điểm tương ứng với số test 1 ≤ N ≤ 20; 0 ≤ Ai ≤ 104; 
- Có 50% số điểm tương ứng với số test N ≤ 105; 0 ≤ Ai ≤ 109. 
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
Bài 2: Tìm người thân (5,0 điểm) 
Chiến tranh ác liệt, cha mẹ đều tham gia cách mạng và hy sinh, năm chị em ông Hứa Bốn 
(Đại Lộc, Quảng Nam) ly tán, riêng người em kế út mất liên lạc. Gần 50 năm, ông Bốn 
không ngừng tìm kiếm em gái với niềm tin bà vẫn còn sống. Bà Phùng Thị Năm (tên khác là 
Phùng Thị Thuỷ) lưu lạc từ nhỏ, sống lang thang, làm thuê, rồi được gia đinh khác nhận nuôi 
sau đó lập gia đình và sinh sống tại Đại Lộc. Tháng 4/2017, hai người tình cờ gặp nhau, Ông 
Bốn có linh cảm Bà Năm chính là người em gái thất lạc bấy lâu. Để xác minh, họ quyết định 
thực hiện xét nghiệm ADN dựa trên mức độ tương đồng giữa hai chuỗi AND (theo thứ tự 
các cặp). Nếu mức độ giống nhau (tỉ lệ phần trăm giữa số cặp giống nhau trên tổng số cặp) 
trên 50% (sau khi làm tròn 2 chữ số phần thập phân), họ sẽ được xác nhận là anh em ruột1.
Dữ liệu: Vào từ file văn bản ADN.INP gồm: 
- Dòng 1: Chuỗi ADN của người thứ nhất; 
- Dòng 2: Chuỗi ADN của người thứ hai. 
Mỗi chuỗi ADN bao gồm các ký tự A, C, G, T được nối với nhau bằng dấu “_” Ví dụ: 
A_C_G_T_A. Độ dài của chuỗi ADN được xác định nhỏ hơn 106 ký tự. 
Kết quả: Ghi ra file văn bản ADN.OUT gồm: 
- Dòng đầu tiên ghi số tỷ lệ phần trăm (được làm tròn đến 2 chữ số phần thập phân) trùng 
khớp của hai chuỗi AND; 
- Dòng thứ 2 nếu mức độ giống nhau giữa hai chuỗi ADN trên 50%, in ra: “OK” ngược lại 
“NO”. 
Ví dụ:
 ADN.INP ADN.OUT
G_A_C_A_G_A_A_A_A_C_C_A_T_C_C_G_C_A_A_T_T_G_ 74.29 
A_C_A_A_G_C_G_C_C_T_G_A_C OK
A_A_C_A_A_A_A_C_A_A_A_T_T_C_G_G_G_A_A_T_T_G_
A_C_A_A_G_C_A_C_C_T_G_A_C
Chấm điểm: 
- Có 50% số điểm tương ứng với độ dài chuỗi AND < 256 kí tự; 
- Có 50% số điểm tương ứng với độ dài chuỗi AND ≤ 106 kí tự.
Bài 3: Phân công công việc (5,0 điểm) 
Tại thành phố ABC có T cơ quan để đảm nhận các nhiệm vụ quan trọng của thành phố. Hiện 
tại, mỗi cơ quan đang thực hiện một số công việc được giao. Tuy nhiên, do có sự chồng chéo 
trong việc phân công, một số công việc đang được nhiều cơ quan thực hiện đồng thời. Điều 
này dẫn đến lãng phí nguồn lực và giảm hiệu quả hoạt động. Để chuẩn bị phân công lại công 
việc, chính quyền thành phố đánh giá cơ quan có ít công việc hơn sẽ giải quyết nhanh hơn so 
với các cơ quan còn lại nên sẽ ưu tiên giữ lại các nhiệm vụ đã phân công cho cơ quan này. 
Chính quyền thành phố yêu cầu phân công lại công việc theo các quy tắc sau: 
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
- Mỗi công việc chỉ được thực hiện bởi một cơ quan duy nhất, và số lượng công việc của các 
cơ quan sau khi phân công lại phải được cân bằng một cách tối ưu, ưu tiên giữ lại công việc 
cho cơ quan ban đầu được phân công ít công việc hơn. Nếu một cơ quan không còn công 
việc nào, cơ quan đó sẽ bị giải thể để tiết kiệm nguồn lực; 
- Quy tắc chuyển công việc: Nếu một công việc X thuộc cả hai cơ quan A và B, thì công việc 
X sẽ được chuyển từ A sang B nếu: Cơ quan B ban đầu được phân công ít công việc hơn A. 
Dữ liệu: Vào từ file văn bản PHANCONG.INP gồm hai dòng. 
- Dòng đầu ghi số nguyên dương T, 1 ≤ T ≤ 105; 
- Dòng thứ 2 là dãy số N gồm T số nguyên tương ứng số công việc được phân công của lần 
lượt các cơ quan với Ni ≤ 100; 
- Dòng thứ i trong T dòng tiếp theo, mỗi dòng ghi dãy số nguyên dương Xj, 1 ≤ Xj ≤ 100 (1 
≤ j ≤ 100), là các công việc của cơ quan i.
Kết quả: ghi ra file văn bản PHANCONG.OUT 
- Dòng đầu ghi số cơ quan sau khi phân công lại; 
- Các dòng tiếp theo: số đầu tiên ghi số thứ tự ban đầu của cơ quan, các số còn lại là các công 
việc của các cơ quan sẽ được phân công.
Ví dụ:
 PHANCONG.INP PHANCONG.OUT
 3 3 
 3 2 1 1 1 
 1 2 3 2 3 
 2 3 3 2
 2
Chấm điểm: 
- Có 20% số điểm tương ứng với số test có T ≤ 5, Ni ≤ 10, Xj ≤ 50; 
- Có 30% số điểm tương ứng với số test có T ≤ 10, Ni ≤ 50, Xj ≤ 100; 
- Có 50% số điểm tương ứng với số test có T ≤ 106, Ni ≤ 100, Xj ≤ 100. 
Bài 4: Tối ưu năng lực (5,0 điểm) 
Để chuẩn bị tham gia kì thi chọn HSG giỏi sắp tới bạn An được giáo viên cho tham gia lớp 
ôn tập với buổi học khác nhau để nâng cao năng lực lập trình. Mỗi buổi học bạn ấy có thể 
được tăng thêm hoặc bị giảm đi năng lực lập trình của mình (năng lực lập trình được thể hiện 
bằng điểm số trong buổi học, điểm này có thể dương hoặc âm). Dữ liệu dự kiến về năng lực 
lập trình của bạn An được thể hiện bằng một dãy số nguyên gồm phần tử. Để tránh quá 
mệt mỏi khi học tập, An chỉ có tham gia không quá buổi học liên tục (1 ≤ 퐾 ≤ ) trong 
thời gian giáo viên của bạn ấy qui định. 
Yêu cầu: Tìm ra khoảng thời gian tối ưu để nâng cao năng lực nhiều nhất trong giới hạn cho 
phép.
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
Dữ liệu: Vào từ file NANGLUC.INP gồm: 
- Dòng đầu tiên gồm hai số nguyên N, K với 1 ≤ K ≤ N ≤ 106; 
- Dòng thứ hai chứa N số nguyên dương A1, A2, , 푛 (| 푖| ≤ 106;1 ≤ i ≤ n). 
Kết quả: Ghi ra tệp văn bản NANGLUC.OUT, gồm một số nguyên duy nhất là kết quả cần 
tìm. 
Ví dụ:
 NANGLUC.INP NANGLUC.OUT
 6 3 9
 2 1 -3 4 5 -2
Giải thích: tổng 4 + 5 = 9 là lớn nhất của 2 số nguyên liên tiếp không quá 3 phần tử. 
Chấm điểm: 
- Có 30% số điểm tương ứng với số test có K = 1 và N ≤ 106; 
- Có 30% số điểm tương ứng với số test có K ≤ N ≤ 103; 
- Có 40% số điểm tương ứng với số test có K ≤ N ≤ 106.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi HSG Tin học THCS (Có giải chi tiết) - De-Thi.com
 ĐÁP ÁN
A. Chuẩn bị 
1. Máy tính chấm bài phải có cài đặt Free Pascal phiên bản 3.2.2, CodeBlocks, Python. 
2. Giám khảo kiểm tra các test đã xây dựng, mỗi bài trong đề thi đều có 10 test. 
3. Chấm trực tiếp trên máy tính kết hợp với Chương trình chấm bài tự động Themis của thầy 
Lê Minh Hoàng, Đại học Sư phạm Hà Nội. Riêng Bài 1 nếu sử dụng Scratch thì chấm trực 
tiếp trên phần mềm Scratch. 
B. Chấm bài 
1. Các bước thực hiện 
- Bước 1. Chuẩn bị thư mục chứa bài thí sinh, mỗi thí sinh sẽ được lưu vào một thư mục 
riêng. 
- Bước 2. Kiểm tra, rà soát lại tên file chương trình, tên file dữ liệu (input), tên file kết quả 
(output); Trường hợp học sinh đặt sai tên thì sẽ bị trừ điểm 20% tổng số điểm của bài thi đó. 
- Bước 3. Chuẩn bị thư mục chứa test theo qui định của phần mềm chấm bài Themis. 
- Bước 4. Chấm bài thi cho thí sinh. 
- Bước 5. Xuất điểm in biên bản chấm và hoàn thành (lưu ý sẽ trừ điểm do sai tên file). 
2. Hai Giám khảo chấm độc lập trên hai máy tính cùng cấu hình. 
3. Hướng dẫn chi tiết 
Lưu ý: đối với thí sinh làm bài bằng ngôn ngữ lập trình scratch thì không cần nhập xuất file, 
khi chấm bài Giám khảo sẽ nhập dữ liệu trực tiếp từ bàn phím. 
Bài 1 (5,0 điểm): Nhà Toán học Tài ba 
- Có 50% số điểm tương ứng với số test 1 ≤ ≤ 20; 0 ≤ 푖 ≤ 104; 
- Có 50% số điểm tương ứng với số test ≤ 105; 0 ≤ 푖 ≤ 109; 
- Tổng số test là 10 (mỗi test là 0,5 điểm). 
Bài 2 (5,0 điểm): Tìm người thân 
- Có 50% số điểm tương ứng với độ dài chuỗi AND < 256 kí tự; 
- Có 50% số điểm tương ứng với độ dài chuỗi AND ≤ 106 kí tự. 
- Tổng số test là 10 (mỗi test là 0,5 điểm). 
Bài 3 (5,0 điểm): Phân công công việc 
- Có 20% số điểm tương ứng với số test có ≤ 5, 푖 ≤ 10, 푗 ≤ 50; 
- Có 30% số điểm tương ứng với số test có ≤ 10, 푖 ≤ 50, 푗 ≤ 100; 
 6
- Có 50% số điểm tương ứng với số test có ≤ 10 , 푖 ≤ 100, 푗 ≤ 100; 
- Tổng số test là 10 (mỗi test là 0,5 điểm). 
Bài 4 (5,0 điểm): Tối ưu năng lực 
- Có 30% số điểm tương ứng với số test có 퐾 = 1 và ≤ 106; 
- Có 30% số điểm tương ứng với số test có 퐾 ≤ ≤ 103; 
- Có 40% số điểm tương ứng với số test có 퐾 ≤ ≤ 106. 
 De-Thi.com