Đề thi Học sinh giỏi THCS môn Tin học tỉnh Yên Bái năm học 2022 – 2023

Đề 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

Loader Loading...
EAD Logo Taking too long?

Reload Reload document
| Open 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:

  1. 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)).
  2. 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)).
  3. 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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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:

  1. 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:

  1. 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

  1. 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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *