[Buổi 1] THẦN TƯỢNG, SỐ ĐẸP, LÌ XÌ ĐẦU NĂM

 

Bài 1: THẦN TƯỢNG

Đề bài

Phân tích

- Có N khán giả, mỗi người bình chọn 1 thí sinh (thí sinh có số báo danh từ 1 đến 1000)

- Tìm số báo danh của thí sinh được bình chọn nhiều nhất.

Nếu có nhiều thí sinh có lượng bình chọn cao nhất bằng nhau → in ra tất cả, theo thứ tự tăng dần.

Cấu trúc dữ liệu sử dụng

- Mảng đếm độ dài 1001 để thống kê số lượt bình chọn của từng thí sinh.
- Tìm giá trị lớn nhất.

Code mẫu

fi=open("THANTUONG.INP")
fo=open("THANTUONG.OUT","w")
#Đọc dữ liệu
doc = fi.readlines() 
n = int(doc[0])  
binh_chon = list(map(int, doc[1:n+1]))

#Đếm bình chọn cho mỗi số báo danh
dem = [0] * 1001  
for v in binh_chon:
        dem[v] += 1
        
#Tìm bình chọn nhiều nhất
max_bc = max(dem)

#Tìm bình chọn lớn nhất bằng nhau
ket_qua = [i for i in range(1, 1001) if dem[i] == max_bc]

#Ghi ra file
fo.write("\n".join(map(str, ket_qua)))

fi.close()
fo.close()

Bài 2: SỐ ĐẸP

Đề bài

Phân tích

- Một số đẹp là số nguyên tố, và khi ta xóa dần các chữ số bên phải, phần còn lại vẫn là số nguyên tố.

- Ví dụ: 7331 → 733 → 73 → 7 đều là nguyên tố → số đẹp.

- Ta cần kiểm tra với từng số trong dãy A, xem có phải là số đẹp không.

Cấu trúc dữ liệu sử dụng

- Duyệt tuần tự dãy A.

- Hàm kiểm tra nguyên tố

- Với mỗi số, ta cắt dần từ phải sang trái và kiểm tra từng phần có phải là nguyên tố không

Code mẫu

# Hàm kiểm tra số nguyên tố
def kt_nguyen_to(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True
# Hàm kiểm tra số đẹp
def So_dep(x):
    s = str(x)
    for i in range(1, len(s)+1):
        if not kt_nguyen_to(int(s[:i])):
            return False
    return True

fi=open("SODEP.INP")
fo=open("SODEP.OUT","w")
#Đọc dữ liệu
n=int(fi.readline())
a = list(map(int, fi.readline().split()))
#Tìm số đẹp
day_sd = [ai for ai in a if So_dep(ai)]
# Ghi ra file
fo.write("\n".join(map(str, day_sd)))

fi.close()
fo.close()

Bài 3: LÌ XÌ ĐẦU NĂM

Đề bài

Phân tích

- Một số lớn n (dưới dạng chuỗi vì có thể dài tới 10⁵ chữ số).

- Một số nguyên k là số chữ số cần xóa khỏi n.

- Xóa đúng k chữ số ở bất kỳ vị trí nào, sao cho số còn lại lớn nhất có thể.

Cấu trúc dữ liệu sử dụng

- Duyệt tuần tự chữ số n từ trái sang phải.

- Dùng ngăn xếp (stack) để xây dựng dãy chữ số kết quả.

- Loại bỏ các chữ số nhỏ hơn chữ số hiện tại nếu còn quyền xóa (k > 0) để tạo số lớn hơn.

Code mẫu

def Xoa_so(n: str, k: int) -> str:
    stack = []
    for so in n:
        # Loại bỏ các chữ số nhỏ hơn so hiện tại
        while k > 0 and stack and stack[-1] < so:
            stack.pop()
            k -= 1
        stack.append(so)
    
    # Nếu còn dư k, xóa từ cuối
    while k > 0:
        stack.pop()
        k -= 1

    return ''.join(stack)

fi=open("LIXI.INP")
fo=open("LIXI.OUT","w")
n = fi.readline().strip()
k = int(fi.readline())

ket_qua = Xoa_so(n, k)

fo.write(ket_qua)

fi.close()
fo.close()