12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS

 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
dài của tất cả các thanh 푛 + 2 . Hơn nữa mỗi cạnh hình chữ nhật có độ dài lẻ phải chứa ít 
nhất một thanh có độ dài 1, tức là số cạnh độ dài lẻ của hình chữ nhật (số các số lẻ trong các 
số , , , ) phải nhỏ hơn hoặc bằng 푛.
long long ans = 0;
int mx = (n + 2LL * m) / 2;
for (int a = 1; a <= mx; a++)
 for (int b = a; b <= mx - a; b++)
 if (2 * (a % 2 + b % 2) <= n)
 ans = max(ans, 1LL * a * b);
cout << ans << "\n";
 푛 2 
Độ phức tạp thuật toán là ( 2) với = .
 ⌊ 2 ⌋
Subtask 4 (20%): 풏, ≤ × 
 푛 2 
Trong subtask này, ta chỉ duyệt độ dài của một cạnh hình chữ nhật 1 ≤ ≤ . Khi 
 ⌊ 2 ⌋
đó ta sẽ có hai cạnh có độ dài là . Hãy kiểm tra điều kiện 푛 không nhỏ hơn 2( mod 2), 
nghĩa là nếu lẻ thì sẽ có ít nhất hai thanh có độ dài là 1.
Bây giờ chúng ta xác định giá trị thích hợp lớn nhất của với một giá trị cho trước. Nhận 
 푛 2 2 푛 2 2 
thấy rằng ≤ . Đầu tiên ta giả sử = . Nếu 푛 < 2( mod 2 + mod 2), 
 ⌊ 2 ⌋ ⌊ 2 ⌋
tức là 푛 nhỏ hơn số các số lẻ trong các giá trị , , , , thì chúng ta sẽ không có đủ các thanh 
độ dài 1 để xếp thành các cạnh độ dài lẻ trong các cạnh , , , . Nhưng trước đó chúng ta đã 
xếp được các thanh có độ dài lẻ trong các thanh và , vì vậy điều này xảy ra với là số lẻ. 
Tức là không đủ thanh độ dài 1 để xếp cạnh độ dài lẻ và , vì vậy cần giảm giá trị của đi 
1. Theo cách này, chúng ta xác định giá trị lớn nhất của cạnh thứ hai ứng với cạnh đã 
chọn trước đó. Trong quá trình duyệt, lưu giá trị lớn nhất của diện tích hình chữ nhật × .
long long ans = 0;
int mx = (n + 2LL * m) / 2;
for (int a = 1; a <= mx; a++) {
 if (n < 2 * (a % 2))
 continue;
 int b = (mx - a);
 if (n < 2 * (a % 2 + b % 2))
 b--;
 ans = max(ans, 1LL * a * b);
}
cout << ans << "\n";
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
 푛 2 
Độ phức tạp thuật toán là .
 ⌊ 2 ⌋
Subtask 5 (30%): Không có thêm ràng buộc nào
Chú ý rằng trong tất cả các hình chữ nhật có cùng chu vi, diện tích lớn nhất sẽ là diện tích 
của hình vuông hoặc hình chữ nhật có các cạnh chênh lệch nhau 1. Thật vậy, giả sử hình chữ 
nhật có các cạnh là và , trong đó + 1 < . Xét một hình chữ nhật có các cạnh + 1 và 
 ― 1 có cùng chu vi. Diện tích của nó sẽ bằng + ― ― 1, tức là lớn hơn diện tích 
của hình chữ nhật ban đầu.
 1
Do đó để tối ưu, ta chọn của chu vi lớn nhất có thể làm giá trị của một trong các cạnh. Để 
 4
 푛 2 
thực hiện điều này, ta lấy giá trị làm giá trị của cạnh nhỏ nhất và chọn giá trị phù 
 ⌊ 4 ⌋
hợp lớn nhất cho , như trong thuật toán trước. Nhưng nếu là số lẻ, thì để tạo thành các 
cạnh có độ dài , chúng ta sẽ cần ít nhất 2 thanh độ dài 1 và chúng ta có thể không có đủ số 
thanh có độ dài 1 để đạt được giá trị lớn nhất có thể của . Do đó, cần xét cả giá trị chẵn và 
 푛 2 푛 2 
lẻ của , nghĩa là cần lấy không chỉ = mà còn lấy giá trị ―1, vì một trong 
 ⌊ 4 ⌋ ⌊ 4 ⌋
hai số đó sẽ là số chẵn. Với mỗi giá trị này, ta chọn một giá trị thích hợp và tìm giá trị 
lớn nhất của × .
long long ans = 0;
int mx = (n + 2LL * m) / 2, side = (n + 2LL * m) / 4;
for (int a = side - 1; a <= side; a++) {
 if (n < 2 * (a % 2))
 continue;
 int b = mx - a;
 if (n < 2 * (a % 2 + b % 2))
 b--;
 ans = max(ans, 1LL * a * b);
}
cout << ans << "\n";
}
Độ phức tạp thuật toán là (1).
Bài 4. Dãy số bitonic (3 điểm)
Phân bổ điểm
 • Có 40% số test ứng với 40% số điểm thỏa mãn: 푛 ≤ 500;
 • 30% số test khác ứng với 30% số điểm thỏa mãn: 푛 ≤ 5000;
 • 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
Cấu hình bài thi
Hướng dẫn giải
Subtask 1 (40%): 풏 ≤ 
Chúng ta hãy xem xét tất cả những cặp (푙, ) sao cho 1 ≤ 푙 ≤ ≤ 푛 và kiểm tra dãy 푙, 푙+1
,, có là dãy bitonic hay không.
Độ phức tạp thuật toán (푛3).
Subtask 2 (30%): 풏 ≤ 
Lưu ý rằng với mọi 푙 < sao cho dãy các phần tử từ chỉ số 푙 đến là bitonic, thì dãy các 
phần tử từ chỉ số 푙 đến ― 1 cũng là bitonic. Điều này có nghĩa là chúng ta có thể cố định 
chỉ số bên trái 푙 và tìm chỉ số bên phải lớn nhất sao cho dãy các phần tử từ chỉ số 푙 đến là 
bitonic. Khi đó số lượng dãy bitonic có phần tử bắt đầu ở chỉ số 푙 là ― 푙 + 1. Duyệt mọi chỉ 
số 푙 = 1, 2,,푛, rồi tính tổng các dãy bitonic ta sẽ tìm được câu trả lời của bài toán.
Độ phức tạp thuật toán là (푛2).
Subtask 3 (30%): Không có thêm ràng buộc nào
Gọi [푖] là số phần tử mảng tăng liên tiếp bắt đầu từ phần tử chỉ số 푖. Ta có công thức 
tính [푖] như sau:
 • [푛] = 1;
 • Với mọi 푖 chạy lần lượt từ 푛 ― 1 về 1: 
 [푖 + 1] + 1 nếu < 
 [푖] = 푖 푖+1
 1 nếu 푖 ≥ 푖+1
Tương tự, gọi 표푤푛[푖] là số phần tử mảng giảm liên tiếp bắt đầu từ phần tử chỉ số 푖. Ta có 
công thức tính 표푤푛[푖] như sau:
 • 표푤푛[푛] = 1;
 • Với mọi 푖 chạy lần lượt từ 푛 ― 1 về 1: 
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
 표푤푛[푖 + 1] + 1 nếu > 
 표푤푛[푖] = 푖 푖+1
 1 nếu 푖 ≤ 푖+1
Nhận thấy rằng độ dài dãy bitonic dài nhất bắt đầu từ chỉ số 푖 là [푖] + 표푤푛[푖 + [푖] ― 1]
―1 và nó cũng là số dãy bitonic có phần tử đầu ở chỉ số 푖. Vì vậy số dãy bitonic cần tìm là:
 푛
 [푖] + 표푤푛[푖 + [푖] ― 1] ― 1 
 푖=1
Độ phức tạp thuật toán là (푛).
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
 ĐỀ SỐ 3
 SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ THI CHỌN HỌC SINH GIỎI 
 HẢI PHÒNG THÀNH PHỐ CẤP THCS
 MÔN: TIN HỌC
 Thời gian: 150 phút (không kể thời gian giao đề)
 TỔNG QUAN ĐỀ THI
 File nguồn nộp File dữ liệu File kết quả Biểu điểm
 Bài 1 BAI1. ∗ BAI1.INP BAI1.OUT 6 điểm
 Bài 2 BAI2.* BAI2.INP BAI2.OUT 7 điểm
 Bài 3 BAI3.* BAI3.INP BAI3.OUT 8 điểm
 Bài 4 BAI4. ∗ BAI4.INP BAI4.OUT 9 điểm
Chú ý: 
- Dấu * là CPP, PY hoặc PAS tương đương với ngôn ngữ C++, Python hoặc Pascal.
- Học sinh cần đặt tên file chương trình theo đúng quy định của từng bài, không ghi bất kì 
thông tin cá nhân nào vào file bài làm. 
Hãy lập trình giải các bài toán sau:
Bài 1: Cho một số nguyên dương A. 
Yêu cầu: Viết chương trình kiểm tra xem A có phải là diện tích của một tam giác vuông có 
các cạnh là số nguyên hay không. Nếu có in ra 풀푬푺, nếu không in ra 푵푶. 
Dữ liệu vào từ tệp BAI1.INP gồm: 
- Dòng đầu chứa số nguyên T (T ≤ 1000) là số lượng số A cần kiểm tra. 
- T dòng tiếp theo mỗi dòng ghi một số A ( ≤ 106). 
Kết quả ghi ra tệp BAI1.OUT gồm T dòng mỗi dòng là một chữ 풀푬푺 hoặc 푵푶 tương ứng 
với dữ liệu đề bài. 
Ví dụ:
 BAI1.INP BAI1.OUT
 3 YES
 6 YES
 24 NO
 50
Giải thích:
Với A = 6, tam giác vuông thỏa mãn yêu cầu đề bài có các cạnh lần lượt là: 3;4;5.
Với A = 24, tam giác vuông thỏa mãn yêu cầu đề bài có các cạnh lần lượt là: 6;8;10.
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
Với A = 50, không có tam giác vuông nào thỏa mãn yêu cầu đề bài.
Subtasks:
 Subtasks Điểm Giới hạn
 1 20% T = 2 và A ≤ 100;
 2 30% 2 < T ≤ 100 và A ≤ 100;
 3 50% Theo dữ liệu đề bài.
Bài 2. Cho một xâu S chỉ gồm các ký tự chữ cái trong bảng chữ cái tiếng Anh và các chữ số 
từ " 0 " đến " 9 ". Một số trong xâu S được định nghĩa là một ký tự chữ số hoặc là các kí tự 
số liên tiếp và không bao gồm các chữ số " 0 " không có nghĩa.
Ví dụ với xâu S = "05aAb21bc3956cDe488a" các số có trong xâu là 5,21,3956,488.
Yêu cầu: Cho xâu S chỉ gồm các kí tự chữ cái tiếng Anh và các chữ số. Hãy viết chương 
trình tìm số chính phương lớn nhất có trong xâu S.
(Số chính phương là số bằng bình phương của một số nguyên, ví dụ 9 là số chính phương vì 
9 = 32).
Dữ liệu vào từ tệp văn bản BAI2.INP gồm xâu S chỉ chứa các ký tự chữ cái trong bảng chữ 
cái tiếng Anh và chữ số (dữ liệu đảm bảo xâu S có không quá 18 chữ số có nghĩa liền nhau 
và độ dài xâu không quá 105 ký tự).
Kết quả ghi ra tệp văn bản BAI2.OUT số chính phương lớn nhất tìm được hoặc số -1 nếu 
không tìm được số chính phương nào.
Ví dụ:
 BAI2.INP BAI2.OUT BAI2.INP BAI2.OUT
aBc2144gHf81Dgf09gf 81 dGaf21eac056Ude00132aV -1
Giải thích:
Test 1: Các số có trong xâu S là 2144; 81; 9. Số chính phương lớn nhất tìm được là 81.
Test 2: Các số có trong xâu S là 21; 56; 132 không có số chính phương.
Subtasks:
 Subtasks Điểm Giới hạn
 1 30% Xâu S có độ dài không quá 250 ký tự;
 2 30% Xâu S có độ dài không quá 103 ký tự;
 3 40% Theo dữ liệu đề bài.
Bài 3. Bạn An có một bộ sách hay và muốn chia sẻ với các bạn trong câu lạc bộ đọc sách của 
trường. Có N yêu cầu được mượn cuốn sách này từ các bạn trong câu lạc bộ, yêu cầu thứ i(1 
≤ i ≤ N) cho biết thời điểm mượn sách là ai và thời điểm trả là bi. Bạn An có thể chấp nhận 
hoặc từ chối đối với một yêu cầu.
Yêu cầu: Hãy lập trình giúp bạn An chọn các yêu cầu mượn sách của các bạn sao cho đáp 
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
ứng được nhiều yêu cầu nhất. Đảm bảo khoảng thời gian sử dụng của hai yêu cầu là không 
giao nhau.
Dữ liệu vào từ tệp văn bản BAI3.INP gồm:
 • Dòng đầu tiên chứa số nguyên dương N (N ≤ 104);
 • Dòng thứ i trong số N dòng tiếp theo chứa hai số nguyên dương ai, bi với (0 < ai < bi 
 ≤ 32 000)(1 ≤ i ≤ N).
Kết quả ghi ra tệp văn bản BAI3.OUT một số nguyên 퐊 là số các yêu cầu được chấp nhận.
Ví dụ:
 BAI3.INP BAI3.OUT
 5 3
 79
 24
 13
 16
 47
Giải thích:
Các yêu cầu được chấp thuận là: 13;47;79.
Subtask:
 Subtasks Điểm Giới hạn
 3
 1 30% N ≤ 100; ai < bi ≤ 10
 3 3
 2 30% 100 < N ≤ 10 ; ai < bi ≤ 10 ;
 3 40% Theo dữ liệu đề bài.
Bài 4. Số X được gọi là số đặc biệt nếu tất cả các chữ số của X đều thuộc tập hợp 
{1;3;5;7;9}. Người ta tạo ra các số đặc biệt, sau đó sắp xếp chúng theo thứ tự tăng dần để 
được một dãy số A.
Ví dụ 20 số đặc biệt đầu tiên:
1; 3; 5; 7; 9; 11; 13; " 15";17; 19; 31; 33; 35; 37; 39; 51; 53; 55; 57; 59.
Yêu cầu: Cho số nguyên dương N, hãy tìm số đặc biệt thứ N trong dãy số A.
Dữ liệu vào từ tệp văn bản BAI4.INP gồm 1 dòng duy nhất chứa số nguyên N (1 ≤ N ≤ 1018).
Kết quả ghi ra tệp BAI4.OUT số đặc biệt thứ N trong dãy số A.
Ví dụ:
 BAI4.INP BAI4.OUT BAI4.INP BAI4.OUT
 8 15 29 97
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
Giải thích: 
Test 1: Số đặc biệt thứ 8 trong dãy là: 15 
1; 3; 5; 7; 9; 11; 13; 15; 
Test 2: Số đặc biệt thứ 29 trong dãy là: 97 
1; 3; 5; 7; 9; 11; 13; 15 ;17; 19; 31; 33; 35; 37; 39; 51; 53; 55; 57; 59; ... ;97;
 Subtasks Điểm Giới hạn
 1 50% N ≤ 106;
 2 30% 106 < N ≤ 109;
 3 20% Theo dữ liệu đề bài.
 ----------HẾT----------
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
 ĐÁP ÁN
Bài 1: Cho một số nguyên dương A. 
C++
#include 
#include 
#include 
using namespace std;
// Hàm kiểm tra xem một số có phải là số chính phương hay không
bool isPerfectSquare(long long n) {
 if (n < 0) return false;
 long long root = round(sqrt(n));
 return (root * root == n);
}
void solve() {
 long long A;
 if (!(cin >> A)) return;
 long long target = 2 * A;
 bool found = false;
 // Duyệt qua các ước a của 2A
 for (long long a = 1; a * a <= target; ++a) {
 if (target % a == 0) {
 long long b = target / a;
 // Kiểm tra điều kiện Pythagoras: a^2 + b^2 = c^2
 if (isPerfectSquare(a * a + b * b)) {
 found = true;
 break;
 }
 }
 }
 if (found) cout << "YES" << endl;
 DeThiHay.net 12 Đề thi và Đáp án kỳ thi chọn học sinh giỏi Tin học cấp THCS - DeThiHay.net
 else cout << "NO" << endl;
}
int main() {
 // Tối ưu nhập xuất cho file .INP và .OUT
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // Mở file nếu chạy trong môi trường thi đấu
 // freopen("BAI1.INP", "r", stdin);
 // freopen("BAI1.OUT", "w", stdout);
 int T;
 if (cin >> T) {
 while (T--) {
 solve();
 }
 }
 return 0;
}
Bài 2:
C++
#include 
#include 
#include 
#include 
#include 
using namespace std;
// Hàm kiểm tra số chính phương cho kiểu long long
bool isPerfectSquare(long long n) {
 if (n < 0) return false;
 if (n == 0) return false; // Dựa trên ví dụ 2, số "00" không được tính
 long long root = round(sqrt(n));
 DeThiHay.net