[Buổi 3] Số đẹp, Xóa ký tự, Sắp xếp dãy số, Phần quà may mắn

 

Bài 1. Số đẹp

Đề bài

Phân tích

Cấu trúc dữ liệu, thuật toán

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

def tong_chu_so(n):
    return sum(int(i) ** 2 for i in str(n))

def Day_so_dep(maxi):
    #beautiful_numbers = []
    DS_dep=[]
    i = 1
    while len(DS_dep) < maxi:
        ssd = tong_chu_so(i)
        if kt_nguyen_to(ssd):
            DS_dep.append(i)
        i += 1
    return DS_dep
fi=open("BEAUTY.INP")
fo=open("BEAUTY.OUT","w")

a = [int(line.strip()) for line in fi if line.strip()]
max_ai=max(a)

# Sinh danh sách số đẹp
DS_so_dep = Day_so_dep(max_ai)

for ai in a:
    fo.write(str(DS_so_dep[ai - 1]) + '\n')

fi.close()
fo.close()

Bài 2. Xóa ký tự

Đề bài

Phân tích

Cấu trúc dữ liệu, thuật toán

Code mẫu

from collections import Counter
fi=open("LCS.INP")
fo=open("LCS.OUT","w")
s1 = fi.readline().strip()
s2 = fi.readline().strip()
# Đếm tần suất ký tự
tan_suat1 = Counter(s1)
tan_suat2 = Counter(s2)
# Tổng ký tự giữ lại (tối đa giao)
sl_giu = 0
for kt in tan_suat1:
    if kt in tan_suat2:
        sl_giu += min(tan_suat1[kt], tan_suat2[kt])

sl_xoa=len(s1) + len(s2) - 2 * sl_giu

fo.write(f"{sl_xoa}")
fi.close()
fo.close()

Bài 3. Sắp xếp dãy số

Đề bài

Phân tích

Cấu trúc dữ liệu, thuật toán

Code mẫu

def Tim_phan_tu_t(n, m, t):
    for r in range(m):  # r = 0 to m-1
        # Phần tử đầu tiên của nhóm
        rf = m if r == 0 else r
        if rf > n:
            continue
        # Số lượng phần tử trong nhóm x ≡ r (mod m)
        cnt = (n - r) // m +1 if r!=0 else n // m

        if t <= cnt:
            return r + (t - 1) * m
        t -= cnt

fi=open("SORT.INP")
fo=open("SORT.OUT","w")
n, m, t = map(int, fi.readline().split())

kq=Tim_phan_tu_t(n, m, t)

fo.write(f"{kq}")
fi.close()
fo.close()

Bài 4. Phần quà may mắn

Đề bài

Phân tích

Cấu trúc dữ liệu, thuật toán

Code mẫu

from collections import defaultdict
def dem_cap_k(a, K):
    ts = defaultdict(int)
    dem = 0

    for x in a:
        y1 = K - x
        y2 = -K - x
        dem += ts[y1]
        if y1 != y2:  # Tránh đếm 2 lần nếu y1 == y2 (trường hợp K == 0)
            dem += ts[y2]
        ts[x] += 1

    return dem

fi=open("LUCKY.INP")
fo=open("LUCKY.OUT","w")
n, K = map(int, fi.readline().split())
a = list(map(int, fi.readline().split()))

dem = dem_cap_k(a, K)
fo.write(f"{dem}")
fi.close()
fo.close()