5 Đề Bí Quyết Trọn Bộ Thi HSG Tin Học Tỉnh Bình Phước 2018 – 2019

Bài 1: Chu Vi Tam Giác (CHUVI.INP / CHUVI.OUT)

1. Tóm tắt đề bài

Cho độ dài ba cạnh của một tam giác lần lượt là a, b, c (1 <= a, b, c <= 1000).

Yêu cầu: Hãy tính chu vi của tam giác đó và ghi kết quả ra file.

2. Phân tích thuật toán & Độ phức tạp

• Giải pháp:

  • Chu vi tam giác có công thức đơn giản: P = a + b + c.

  • Đọc trực tiếp 3 số nguyên a, b, c từ file CHUVI.INP và ghi tổng a + b + c vào file CHUVI.OUT.

• Độ phức tạp:

  • Thời gian (Time Complexity): O(1), thực hiện trong 0.001 giây.

  • Không gian (Space Complexity): O(1).

3. Code Python Chuẩn

import sys

sys.stdin = open('CHUVI.INP', 'r')
sys.stdout = open('CHUVI.OUT', 'w')

du_lieu = sys.stdin.read().split()
a, b, c = map(int, du_lieu[:3])

chu_vi = a + b + c
print(chu_vi)

Bài 2: Số Lượng Chữ Số (SOCHUSO.INP / SOCHUSO.OUT)

1. Tóm tắt đề bài

Cho một xâu ký tự S gồm các chữ cái tiếng Anh in thường và các chữ số. Độ dài xâu S không quá 200 ký tự.

Yêu cầu: Đếm xem có bao nhiêu chữ số trong xâu S.

2. Phân tích thuật toán

• Giải pháp:

  • Duyệt qua từng ký tự c trong xâu S.

  • Kiểm tra xem c có phải là chữ số hay không bằng phương thức c.isdigit().

  • Nếu đúng là chữ số, tăng biến đếm lên 1.

• Độ phức tạp:

  • Thời gian (Time Complexity): O(|S|), với |S| <= 200 thì chương trình chạy tức thì.

  • Không gian (Space Complexity): O(|S|) để lưu trữ xâu S.

3. Code Python Chuẩn

import sys

sys.stdin = open('SOCHUSO.INP', 'r')
sys.stdout = open('SOCHUSO.OUT', 'w')

s = sys.stdin.read().strip()

dem_chu_so = sum(1 for ky_tu in s if ky_tu.isdigit())
print(dem_chu_so)

Bài 3: Đếm Số Nguyên Tố (DEMNT.INP / DEMNT.OUT)

1. Tóm tắt đề bài

Cho số nguyên dương N (N <= 10^6).

Yêu cầu: Xác định xem trong đoạn [1, N] có bao nhiêu số nguyên tố.

2. Phân tích thuật toán & Tối ưu hóa

• Nhận xét:

  • Nếu dùng thuật toán kiểm tra từng số xem có phải số nguyên tố hay không (với độ phức tạp O(căn(X)) cho mỗi số X), tổng thời gian sẽ là O(N * căn(N)), khi N = 10^6 sẽ thực hiện khoảng 10^9 phép tính -> Bị TLE (vượt quá thời gian cho phép).

• Giải pháp tối ưu – Sàng Eratosthenes:

  1. Khởi tạo mảng đánh dấu is_prime độ dài N + 1 với tất cả giá trị là True.

  2. Gán is_prime[0] = is_prime[1] = False.

  3. Duyệt i từ 2 đến căn(N):

     • Nếu is_prime[i] là True, đánh dấu tất cả các bội số của i từ i * i đến N là False.

  4. Đếm số lượng giá trị True còn lại trong mảng is_prime từ 1 đến N.

• Độ phức tạp:

  • Thời gian (Time Complexity): O(N * log(log N)), với N = 10^6 chỉ tốn chưa đến 0.1 giây trong Python.

  • Không gian (Space Complexity): O(N) lưu mảng boolean.

3. Code Python Chuẩn

import sys

sys.stdin = open('DEMNT.INP', 'r')
sys.stdout = open('DEMNT.OUT', 'w')

n = int(sys.stdin.read().split()[0])

if n < 2:
    print(0)
else:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False

    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1

    so_luong_nt = sum(is_prime)
    print(so_luong_nt)

Bài 4: Xuất Hiện Nhiều Nhất (XUATHIEN.INP / XUATHIEN.OUT)

1. Tóm tắt đề bài

Cho dãy A gồm N số nguyên a1, a2, …, an.

Yêu cầu: Tìm giá trị xuất hiện nhiều lần nhất trong dãy A và số lần xuất hiện của giá trị đó. Nếu có nhiều giá trị có cùng số lần xuất hiện nhiều nhất, hãy đưa ra giá trị nhỏ nhất trong số các giá trị đó.

Ràng buộc dữ liệu:

• 60% số test: N <= 10^3, ai <= 10^3.

• 20% số test: N <= 10^5, ai <= 10^4.

• 20% số test: N <= 10^6, ai <= 10^9.

2. Phân tích thuật toán & Xử lý Ràng buộc

• Thách thức: Do ai <= 10^9, ta không thể dùng mảng đếm tần suất thông thường count[ai] vì sẽ tràn bộ nhớ.

• Giải pháp tối ưu – Sử dụng Dictionary (Hash Map):

  1. Dùng dict trong Python để lưu tần suất xuất hiện: tan_suat[val] = số_lần_xuất_hiện.

  2. Tìm tần suất xuất hiện lớn nhất: max_freq = max(tan_suat.values()).

  3. Tìm giá trị $x$ nhỏ nhất thỏa mãn tan_suat[x] == max_freq.

  4. In ra giá trị min_val ở dòng 1 và max_freq ở dòng 2.

• Độ phức tạp:

  • Thời gian (Time Complexity): O(N) để duyệt và xây dựng dictionary. Với N = 10^6, Python xử lý trong khoảng 0.3 – 0.5 giây.

  • Không gian (Space Complexity): O(N) lưu dictionary.

3. Code Python Chuẩn

import sys

sys.stdin = open('XUATHIEN.INP', 'r')
sys.stdout = open('XUATHIEN.OUT', 'w')

du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])

tan_suat = {}
for i in range(1, n + 1):
    val = int(du_lieu[i])
    tan_suat[val] = tan_suat.get(val, 0) + 1

max_freq = max(tan_suat.values())

gia_tri_thoaman = min(val for val, freq in tan_suat.items() if freq == max_freq)

print(gia_tri_thoaman)
print(max_freq)

Câu Hỏi Thường Gặp (FAQ)

Tại sao lại dùng dict.get(val, 0) + 1 thay vì mảng danh sách trong Bài 4?

Giá trị phần tử ai có thể lên tới 10^9. Tạo một danh sách độ dài 10^9 trong Python sẽ tốn hàng GB RAM và gây ra lỗi tràn bộ nhớ (Memory Limit Exceeded). Dictionary trong Python hoạt động theo cơ chế Bảng băm (Hash Table), chỉ lưu các giá trị thực sự xuất hiện nên cực kỳ tiết kiệm bộ nhớ.

Thuật toán Sàng Eratosthenes trong Bài 3 chạy tốt đến phạm vi nào?

Sàng Eratosthenes hoạt động hiệu quả nhất trong phạm vi N <= 10^7. Với N = 10^6, thuật toán chỉ mất chưa đến 0.1 giây để chạy xong.

giải đề thi hsg tin học lớp 9 bình phước, đề thi hsg tin học bình phước 2018 2019, sàng nguyên tố python hsg tin, đếm số xuất hiện nhiều nhất python, đề thi hsg tin học thcs python, luyện thi học sinh giỏi tin học

Hashtags

#HSGTinHoc #PythonHSG #LuyenThiTinHoc #GiaiDeTinHoc #SieveOfEratosthenes #PythonProgramming #Algorithm