NỘI DUNG
Đề thi học sinh giỏi môn Tin học khối THCS tỉnh Yên Bái năm học 2022-2023
Loading...
Reload document 
Open in new tab Đáp án tham khảo
Câu 1. Số phong phú
Để giải bài toán này, ta cần tính tổng các ước nguyên dương của mỗi số trong đoạn [a, b] và kiểm tra xem tổng đó có lớn hơn số đó không. Nếu có, thì số đó là số phong phú. Để tính tổng các ước nguyên dương của một số n, ta cần duyệt từ 1 đến căn bậc hai của n, kiểm tra xem i có phải là ước của n không, nếu có thì ta cộng thêm i và n/i vào tổng. Sau đó kiểm tra xem có cần trừ đi n không (vì không tính chính nó trong tổng ước), nếu cần thì trừ đi.
Dưới đây là code Python để giải bài toán này:
def sum_divisors(n):
s = 1
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
s += i
if i != n // i:
s += n // i
if int(n ** 0.5) ** 2 == n:
s -= int(n ** 0.5)
else:
s -= 1
return s
a, b = map(int, input().split())
count = 0
for i in range(a, b+1):
if sum_divisors(i) > i:
count += 1
with open("SOPP.OUT", "w") as f:
f.write(str(count))
Dưới đây là code giải bài toán trên bằng C++:
#include <bits/stdc++.h>
using namespace std;
int sum_divisors(int n) {
int s = 1;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
s += i;
if (i != n / i) {
s += n / i;
}
}
}
if (sqrt(n) == int(sqrt(n))) {
s -= sqrt(n);
}
else {
s -= 1;
}
return s;
}
int main() {
int a, b;
cin >> a >> b;
int count = 0;
for (int i = a; i <= b; i++) {
if (sum_divisors(i) > i) {
count++;
}
}
ofstream outfile("SOPP.OUT");
outfile << count;
outfile.close();
return 0;
}
Dưới đây là code giải bài toán trên bằng Pascal:
program SOPP;
var
a, b, i, s, count: longint;
f: text;
function sum_divisors(n: longint): longint;
var
i, s: longint;
begin
s := 1;
for i := 2 to trunc(sqrt(n)) do
begin
if n mod i = 0 then
begin
s := s + i;
if i <> n div i then
begin
s := s + n div i;
end;
end;
end;
if sqrt(n) = trunc(sqrt(n)) then
begin
s := s - trunc(sqrt(n));
end
else
begin
s := s - 1;
end;
sum_divisors := s;
end;
begin
assign(f, 'SOPP.OUT');
reset(f);
readln(a, b);
close(f);
count := 0;
for i := a to b do
begin
s := sum_divisors(i);
if s > i then
begin
count := count + 1;
end;
end;
assign(f, 'SOPP.OUT');
rewrite(f);
writeln(f, count);
close(f);
end.
Độ phức tạp của thuật toán này là O((b-a+1) sqrt(b)), vì ta cần duyệt từ a đến b, mỗi lần tính tổng ước nguyên dương của một số ta cần duyệt từ 1 đến căn bậc hai của số đó. Với cách giải trên các bạn không đạt được 100% số điểm của đề thi. Cùng nhau tham khảo một số thuật toán khác xử lý bài toán này dưới đây.
Để giải bài toán trên, chúng ta có thể sử dụng các thuật toán sau đây:
- Kiểm tra từng số trong đoạn [a, b] và tính tổng các ước nguyên dương của nó để xác định xem nó có phải là số phong phú hay không. Độ phức tạp của thuật toán này là O((b-a+1) sqrt(b)).
- Sử dụng tam giác Pascal để tính số ước nguyên dương của từng số trong đoạn [1, b]. Sau đó, duyệt qua các số trong đoạn [a, b] và tính tổng các ước nguyên dương của nó từ bảng số liệu đã tính trước đó. Nếu tổng này lớn hơn số đang xét thì đó là số phong phú. Độ phức tạp của thuật toán này là O(b log b + (b-a+1)).
- Sử dụng phân tích thừa số nguyên tố để tính số ước nguyên dương của mỗi số trong đoạn [a, b]. Sau đó, duyệt qua các số trong đoạn [a, b] và tính tổng các ước nguyên dương của nó từ các thừa số nguyên tố đã tính trước đó. Nếu tổng này lớn hơn số đang xét thì đó là số phong phú. Độ phức tạp của thuật toán này là O(b log log b + (b-a+1) log b).
Trong đó, thuật toán thứ 3 có độ phức tạp nhỏ nhất, tiếp đó là thuật toán thứ 2 và cuối cùng là thuật toán thứ 1. Vì vậy, để đạt điểm tối đa, bạn cần sử dụng thuật toán thứ 2 hoặc thứ 3 (cần kiểm tra các test đảm bảo độ chính xác).
Code Python tham khảo cho thuật toán tối ưu hơn:
def is_abundant(n):
divisors_sum = sum([i for i in range(1, int(n**0.5)+1) if n % i == 0])
divisors_sum += sum([n // i for i in range(2, int(n**0.5)+1) if n % i == 0 and n // i != i])
return divisors_sum > n
def count_abundant_numbers(a, b):
count = 0
for i in range(a, b + 1):
if is_abundant(i):
count += 1
return count
Code C++ tham khảo cho thuật toán tối ưu hơn:
#include <iostream>
#include <cmath>
using namespace std;
// Hàm kiểm tra số phong phú
bool isAbundant(int n) {
int s = 1;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
s += i;
if (i != n/i) {
s += n/i;
}
}
}
if (s > n) {
return true;
}
return false;
}
int main() {
int a, b;
cin >> a >> b;
int count = 0;
for (int i = a; i <= b; i++) {
if (isAbundant(i)) {
count++;
}
}
cout << count << endl;
return 0;
}
Câu 2. Nhanh trí
Với bài toán trên chúng ta có 5 thuật toán giải như sau:
-
Dùng kiểu số nguyên: Chia mỗi số cho 10 lần lượt để lấy từng chữ số của số đó và lưu vào một mảng, sau đó so sánh từng phần tử của mảng. Số nào có phần tử cuối cùng lớn hơn thì đó chính là số có số đảo ngược lớn hơn. Độ phức tạp của thuật toán này là O(log N), với N là số lượng chữ số của số lớn nhất trong 2 số A và B.
-
Dùng kiểu số nguyên: Chuyển số về dạng chuỗi và đảo ngược chuỗi đó, sau đó so sánh 2 chuỗi. Số nào có chuỗi đảo ngược lớn hơn thì đó chính là số có số đảo ngược lớn hơn. Độ phức tạp của thuật toán này là O(log N), với N là số lượng chữ số của số lớn nhất trong 2 số A và B.
-
Dùng kiểu số thực: Chuyển số về dạng chuỗi, sau đó đảo ngược chuỗi và chuyển về kiểu số thực để so sánh 2 số. Số nào lớn hơn thì đó chính là số có số đảo ngược lớn hơn. Độ phức tạp của thuật toán này là O(log N), với N là số lượng chữ số của số lớn nhất trong 2 số A và B.
-
Dùng kiểu chuỗi: Tách xâu S thành xâu a và xâu b. Sau đó đảo ngược 2 xâu và so sánh. Xâu nào lớn hơn thì đó chính là số có số đảo ngược lớn hơn. Độ phức tạp của thuật toán này là O(N), với N là độ dài của xâu lớn nhất trong 2 xâu a và b.
-
Dùng kiểu chuỗi: Tách xâu S thành xâu a và xâu b. Sau đó sử dụng hàm số đảo cho xâu a và b để so sánh. Xâu nào có số đảo lớn hơn thì đó chính là số có số đảo ngược lớn hơn. Độ phức tạp của thuật toán này là O(N log N), với N là độ dài của xâu lớn nhất trong 2 xâu a và b.
Dưới đây là code Python cho 5 thuật toán nêu trên:
- Sử dụng phép toán chia và lấy phần dư:
def reverse_number_1(n):
rev = 0
while n > 0:
rev = rev * 10 + n % 10
n //= 10
return rev
def find_larger_reverse_1(a, b):
rev_a = reverse_number_1(a)
rev_b = reverse_number_1(b)
if rev_a > rev_b:
return a
else:
return b
2. Sử dụng hàm đảo ngược chuỗi:
def reverse_number_2(n):
return int(str(n)[::-1])
def find_larger_reverse_2(a, b):
rev_a = reverse_number_2(a)
rev_b = reverse_number_2(b)
if rev_a > rev_b:
return a
else:
return b
3. Sử dụng hàm đảo ngược chuỗi và kiểm tra độ dài chuỗi:
def reverse_number_3(n):
return str(n)[::-1]
def find_larger_reverse_3(a, b):
rev_a = reverse_number_3(a)
rev_b = reverse_number_3(b)
if len(rev_a) > len(rev_b):
return a
elif len(rev_a) < len(rev_b):
return b
else:
if rev_a > rev_b:
return a
else:
return b
4. Sử dụng hàm đảo ngược chuỗi và so sánh từng kí tự của chuỗi:
def reverse_number_4(n):
return str(n)[::-1]
def find_larger_reverse_4(a, b):
rev_a = reverse_number_4(a)
rev_b = reverse_number_4(b)
for i in range(len(rev_a)):
if rev_a[i] > rev_b[i]:
return a
elif rev_a[i] < rev_b[i]:
return b
return a if len(rev_a) > len(rev_b) else b
5. Sử dụng hàm đảo ngược số và so sánh từng chữ số:
def reverse_number_5(n):
rev = 0
while n > 0:
rev = rev * 10 + n % 10
n //= 10
return rev
def find_larger_reverse_5(a, b):
len_a = len(str(a))
len_b = len(str(b))
if len_a > len_b:
return a
elif len_a < len_b:
return b
else:
rev_a = reverse_number_5(a)
rev_b = reverse_number_5(b)
for i in range(len_a):
if rev_a % 10 > rev_b % 10:
return a
elif rev_a % 10 < rev_b % 10:
return b
rev_a //= 10
rev_b //= 10
return a
Câu 3. Khiêu vũ
Để giải quyết bài toán này, chúng ta có thể sử dụng hai phương pháp sau:
- Thuật toán Brute Force:
Ta sử dụng hai vòng lặp để duyệt qua tất cả các cặp đôi và kiểm tra xem chiều cao của hai người đó có chênh lệch k như yêu cầu hay không. Độ phức tạp của thuật toán này là O(n^2).
count = 0
for i in range(n):
for j in range(i+1, n):
if abs(h[i] - h[j]) == k:
count += 1
return count
- Thuật toán sắp xếp và tìm kiếm nhị phân:
Ta sắp xếp danh sách chiều cao của n người tham gia và sau đó tìm kiếm tất cả các cặp đôi có chênh lệch chiều cao bằng k. Độ phức tạp của thuật toán này là O(nlogn) do sắp xếp.
sort(h)
count = 0
for i in range(n):
j = bisect_left(h, h[i]+k, i+1, n)
if j < n and h[j] == h[i] + k:
count += 1
return count
Thuật toán Brute Force đơn giản nhưng có độ phức tạp lớn với nên sẽ không thể xử lý được với các trường hợp lớn. Trong khi đó, thuật toán sắp xếp và tìm kiếm nhị phân có độ phức tạp thấp hơn và có thể xử lý được các trường hợp lớn hơn. Chính vì vậy, để đạt được điểm tối đa bạn nên sử dụng thuật toán sắp xếp và tìm kiếm nhị phân.
Câu 4. Dãy hình nón
Đây là bài toán chúng tôi đã đăng tải lên website. Xin mời quý độc giả tham khảo tại đây
Dưới đây là cài đặt bài toán theo thuật toán Quy hoạch động với 3 ngôn ngữ lập trình Python, C++ và Pascal
Code Python
def read_input_file(filename):
with open(filename, 'r') as f:
n = int(f.readline().strip())
A = list(map(int, f.readline().strip().split()))
return n, A
def write_output_file(filename, result):
with open(filename, 'w') as f:
f.write(str(result))
def longest_cone_subsequence(n, A):
# Tạo mảng L để lưu độ dài dãy con hình nón dài nhất kết thúc tại vị trí i
L = [1] * n
# Tính L[i] cho các vị trí i trong dãy A
for i in range(n):
for j in range(i):
if A[j] < A[i] and L[j] + 1 > L[i]:
L[i] = L[j] + 1
# Tạo mảng R để lưu độ dài dãy con hình nón dài nhất bắt đầu từ vị trí i
R = [1] * n
# Tính R[i] cho các vị trí i trong dãy A
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if A[j] < A[i] and R[j] + 1 > R[i]:
R[i] = R[j] + 1
# Tìm độ dài dãy hình nón dài nhất
max_len = 0
for i in range(n):
if L[i] + R[i] - 1 > max_len:
max_len = L[i] + R[i] - 1
return max_len
if __name__ == '__main__':
n, A = read_input_file('SPSEQ.INP')
result = longest_cone_subsequence(n, A)
write_output_file('SPSEQ.OUT', result)
Code C++
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int n, a[MAXN], f[MAXN][MAXN];
int main() {
ifstream inp("SPSEQ.INP");
ofstream out("SPSEQ.OUT");
inp >> n;
for (int i = 1; i <= n; i++) {
inp >> a[i];
f[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int l = 1, r = len; r <= n; l++, r++) {
int mid = l + r >> 1;
int cnt = 0, pre = 0;
for (int i = l; i <= mid; i++) {
if (a[i] > pre) {
cnt++;
pre = a[i];
}
}
pre = 0;
for (int i = mid + 1; i <= r; i++) {
if (a[i] < pre || !pre) {
cnt++;
pre = a[i];
}
}
if (cnt == len) f[l][r] = len;
for (int k = l; k < r; k++) {
f[l][r] = max(f[l][r], f[l][k] + f[k+1][r]);
}
}
}
out << f[1][n];
inp.close();
out.close();
return 0;
}
Code Pascal
program SPSEQ;
const
maxN = 100000;
var
n, res: longint;
a: array[1..maxN] of longint;
incDP, decDP: array[1..maxN] of longint;
f: text;
function max(x, y: longint): longint;
begin
if x > y then max := x
else max := y;
end;
procedure readInput;
var
i: longint;
begin
assign(f, 'SPSEQ.INP');
reset(f);
readln(f, n);
for i := 1 to n do read(f, a[i]);
close(f);
end;
procedure writeOutput;
begin
assign(f, 'SPSEQ.OUT');
rewrite(f);
writeln(f, res);
close(f);
end;
procedure solve;
var
i, j: longint;
begin
// tính mảng tăng dần
for i := 1 to n do begin
incDP[i] := 1;
for j := 1 to i - 1 do
if (a[j] < a[i]) and (incDP[i] < incDP[j] + 1) then
incDP[i] := incDP[j] + 1;
end;
// tính mảng giảm dần
for i := n downto 1 do begin
decDP[i] := 1;
for j := n downto i + 1 do
if (a[j] < a[i]) and (decDP[i] < decDP[j] + 1) then
decDP[i] := decDP[j] + 1;
end;
// tìm dãy hình nón dài nhất
res := 0;
for i := 1 to n do
if (incDP[i] + decDP[i] - 1 = n) and (incDP[i] mod 2 = 1) then
res := max(res, incDP[i]);
end;
begin
readInput;
solve;
writeOutput;
end.