Đề 1:  Đề THCS – Bà Rịa Vũng Tàu 2022 – 2023

Đề 2 thi học sinh giỏi lớp 9 môn Tin học – Tỉnh Bình Định năm 2022

50 Đề thi học sinh giỏi Tin học trên cả nước Việt Nam (Có đáp án và lời giải chi tiết)

Cập nhật mới nhất 2025:
Tổng hợp 50 đề thi học sinh giỏi môn Tin học lớp 9 và THCS của các tỉnh, thành phố trên cả nước Việt Nam, kèm lời giải chi tiết bằng Python hoặc Pascal. Bộ sưu tập này giúp học sinh ôn luyện toàn diện, chuẩn bị tốt nhất cho kỳ thi HSG cấp huyện, cấp tỉnh và thi vào lớp 10 chuyên Tin.

Tài liệu của PHA – THCS Trần Thị Vũ Thư – TB

(Lưu ý: Nếu link lỗi, vui lòng để lại bình luận phía dưới để admin cập nhật ngay lập tức).

1. Giới thiệu bộ 50 đề thi Tin học trên cả nước

Môn Tin học là môn học đòi hỏi tư duy logic, kỹ năng lập trình và khả năng giải quyết vấn đề.
Bộ “50 Đề thi học sinh giỏi Tin học trên cả nước Việt Nam” được tổng hợp từ nhiều năm của các tỉnh như:
Hà Nội, TP. Hồ Chí Minh, Bình Định, Tiền Giang, Nghệ An, Đà Nẵng, Hải Phòng, Lâm Đồng, Cần Thơ, Thái Bình, Nam Định, Đồng Tháp,…

Mỗi đề đều gồm 5 bài lập trình, được sắp xếp từ dễ đến khó, giúp học sinh:

• Ôn tập cấu trúc ngôn ngữ (Python hoặc Pascal)

• Củng cố kỹ năng thuật toán cơ bản

• Phát triển khả năng tư duy giải quyết bài toán thực tế

2. Nội dung và dạng bài thường gặp trong các đề thi

Sau khi tổng hợp 50 đề thi, có thể chia các dạng bài Tin học học sinh giỏi phổ biến như sau:

Dạng 1: Xử lý mảng 1 chiều

• Tìm số lớn nhất, nhỏ nhất, tổng, trung bình, phần tử thỏa điều kiện.

• Sắp xếp, đếm, lọc phần tử.
  Rèn kỹ năng duyệt mảng, sử dụng vòng lặp và điều kiện.

Dạng 2: Ma trận (mảng 2 chiều)

• Tính tổng hàng, cột, đường chéo.

• Xoay ma trận, phản chiếu, tìm phần tử đặc biệt.
  Kiểm tra khả năng làm việc với cấu trúc dữ liệu hai chiều.

Dạng 3: Xử lý chuỗi ký tự

• Đếm từ, tách chữ, đếm nguyên âm – phụ âm.

• Loại bỏ ký tự, viết hoa chữ cái đầu, so sánh chuỗi.
  Củng cố kỹ năng làm việc với string trong Python.

⚙️ Dạng 4: Thuật toán và quy hoạch động (Dynamic Programming)

• Bài toán con ếch, chia kẹo, dãy con tăng dài nhất, ba lô,…
  Đòi hỏi tư duy phân tích và tối ưu thuật toán.

Dạng 5: Đồ thị và đường đi ngắn nhất

• Duyệt đồ thị bằng DFS, BFS, tìm cây khung nhỏ nhất (Prim, Kruskal), hoặc đường đi ngắn nhất (Dijkstra, Floyd).
  Đây là phần khó, thường xuất hiện ở đề cấp tỉnh và chuyên Tin.

3. Lợi ích khi luyện 50 đề thi Tin học HSG

Học sinh khi luyện bộ đề này sẽ đạt được nhiều kỹ năng quan trọng:

✅ Nắm chắc cấu trúc lập trình cơ bản: vòng lặp, điều kiện, hàm, mảng, chuỗi.
✅ Hiểu rõ tư duy thuật toán: cách phân tích đề, chia bài toán nhỏ, tìm hướng tối ưu.
✅ Làm quen với phong cách ra đề của các tỉnh – chuẩn bị tốt cho kỳ thi thật.
✅ Tăng tốc độ lập trình và tư duy khi viết code.

Kết luận

Bộ 50 Đề thi học sinh giỏi Tin học trên cả nước Việt Nam là tài liệu không thể thiếu cho những ai đam mê lập trình và mong muốn đạt giải cao trong các kỳ thi học sinh giỏi.
Mỗi đề là một thử thách thú vị, giúp bạn nâng cao tư duy thuật toán, khả năng lập trình và tốc độ xử lý vấn đề.

Hãy tải về, luyện tập hằng ngày và chinh phục ước mơ trở thành học sinh chuyên Tin giỏi nhất!

ĐÁP ÁN BÀI 1:

🧠 Ý tưởng

• Duyệt tất cả cặp $(i,j)$ với $i<j$

• Tính:

  gcd(a[i],a[j])

• Lưu lại giá trị lớn nhất

import sys
import math

sys.stdin = open("CDIV.INP", "r")
sys.stdout = open("CDIV.OUT", "w")

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

max_gcd = 0

# duyệt mọi cặp
for i in range(n):
    for j in range(i + 1, n):
        g = math.gcd(a[i], a[j])
        if g > max_gcd:
            max_gcd = g

print(max_gcd)

📊 Độ phức tạp

• Có ~ n(n−1)2\frac{n(n-1)}{2}2n(n−1)​ cặp
  👉 Độ phức tạp: O(N² log A)

⚠️ Với:

• $N\le 200,000$ ❌ → TLE chắc chắn
• Chỉ dùng khi:
  • $N\le 2000$ ✔

🧪 Ví dụ

Input:

Xét:

• gcd(12,6) = 6 (lớn nhất)

👉 Output:

ĐÁP ÁN BÀI 2:

Đây là bài quy hoạch động + dãy tăng có điều kiện (giống LIS nhưng có thêm K) 🔥

🧠 Phân tích

Ta cần chọn dãy chỉ số tăng:

• i1<i2<i3<…..
• Và:

a[j]≥a[i]+K

👉 Tức là:

• Vẫn giữ thứ tự ban đầu
• Nhưng mỗi bước phải tăng ít nhất K

💡 Ý tưởng (Greedy cực hay)

👉 Ta không cần DP nặng, chỉ cần:

• Duyệt từ trái → phải
• Giữ giá trị cuối cùng đã chọn (last)
• Nếu phần tử tiếp theo ≥ last + K thì chọn

import sys

sys.stdin = open("GIFT.INP", "r")
sys.stdout = open("GIFT.OUT", "w")

n, k = map(int, sys.stdin.readline().split())

a = []
for _ in range(n):
    a.append(int(sys.stdin.readline()))

# Bắt đầu
dem = 1
cuoi = a[0]

for i in range(1, n):
    if a[i] >= cuoi + k:
        dem += 1
        cuoi= a[i]

print(dem)

🧪 Ví dụ

Input:

Chọn:

• 4 → 6 → 8 ✅

👉 Output:

⚡ Độ phức tạp

• Thời gian: O(N)
• Bộ nhớ: O(1)

🔥 Vì sao Greedy đúng?

• Luôn chọn phần tử nhỏ nhất có thể để mở rộng chuỗi
• Giữ cơ hội chọn được nhiều phần tử hơn phía sau

🚀 Nếu muốn nâng cấp

Bài này có thể nâng lên:

• Dùng DP + Segment Tree (khi đổi điều kiện)
• Hoặc biến thể LIS nâng cao thi HSG

🔥 1. Thuật toán Greedy là gì?

Greedy (tham lam) là cách giải bài toán bằng việc:

👉 Luôn chọn phương án tốt nhất tại thời điểm hiện tại
👉 Không cần xét lại các bước trước

💡 Hiểu đơn giản:

“Thấy cái nào lợi nhất trước → chọn luôn”

⚡ 2. Đặc điểm nhận biết bài Greedy

Bài toán dùng Greedy khi có:

✅ 1. Tính chất tham lam

• Chọn tốt nhất trước → vẫn ra kết quả tối ưu

✅ 2. Tính chất con tối ưu

• Lời giải lớn = lời giải nhỏ tốt nhất

🧠 3. Các bài Greedy kinh điển

📌 Bài 1: Chọn nhiều hoạt động nhất (Activity Selection)

👉 Có các khoảng thời gian, chọn nhiều nhất không bị trùng

Ý tưởng:

• Sắp xếp theo thời gian kết thúc tăng dần
• Chọn hoạt động kết thúc sớm nhất trước

Code Python:

import sys

n = int(input())
a = []

for _ in range(n):
    s, e = map(int, input().split())
    a.append((s, e))

# sắp xếp theo thời gian kết thúc
a.sort(key=lambda x: x[1])

dem = 0
last_end = 0

for s, e in a:
    if s >= last_end:
        dem += 1
        last_end = e

print(dem)

📌 Bài 2: Đổi tiền (Coin Change – Greedy)

👉 Dùng ít số tờ tiền nhất

Ví dụ: 1, 2, 5, 10, 20…

Ý tưởng:

• Lấy tờ lớn nhất trước

Code:

import sys

n = int(input())
coins = [20, 10, 5, 2, 1]

dem = 0

for c in coins:
    dem += n // c
    n %= c

print(dem)

⚠️ 4. Khi nào KHÔNG dùng Greedy?

Greedy sai khi:

• Quyết định hiện tại ảnh hưởng tương lai
• Không đảm bảo tối ưu toàn cục

👉 Ví dụ sai:

• Balo 0/1 → phải dùng Quy hoạch động (DP)

🚀 5. So sánh nhanh

🎯 6. Mẹo thi HSG

Khi gặp bài → hỏi ngay:

1. Có thể sắp xếp + chọn dần không?
2. Có thể chọn từng bước mà không cần quay lại không?
3. Có bài mẫu giống:
   • Activity
   • Coin Change
   • Interval

👉 Nếu có → 90% là Greedy

• Hotline: 093.717.9278 ( Gặp Tấn Dân Cử Nhân Công Nghệ Thông Tin)