[Buổi 4] Trực nhật, Diện tích hình chữ nhật, Xin chào, Mua quà lưu niệm

 

Bài 1. Trực nhật

Đề bài

Phân tích

- An trực nhật mỗi x1 ngày.
- Bình trực nhật mỗi x2 ngày.
- Ban đầu cả hai đều trực ngày đầu tiên.
- Cần tìm: Sau bao nhiêu ngày cả hai lại trực cùng ngày lần tiếp theo, Khi đó mỗi bạn đã trực nhật bao nhiêu lần.
- Đây là bài toán tìm Bội chung nhỏ nhất (BCNN) của x1 và x2.

- Tìm BCNN: Dùng công thức

- Số lần trực của mỗi người: An: LCM // x1; Bình: LCM // x2

Code tham khảo

import math
fi=open("TN.INP")
fo=open("TN.OUT","w")
x1, x2 = map(int, fi.readline().split())
ngay_truc_chung =x1 * x2//math.gcd(x1, x2)
lan_truc_an = ngay_truc_chung // x1
lan_truc_binh = ngay_truc_chung // x2
fo.write(f"{ngay_truc_chung}\n")
fo.write(f"{lan_truc_an} {lan_truc_binh}\n")
fi.close()
fo.close()

Bài 2. Diện tích hình chữ nhật

Đề bài

Phân tích

-  HCN1: góc trái dưới (x1, y1) và góc phải trên (x2, y2)
-  HCN2: góc trái dưới (u1, v1) và góc phải trên (u2, v2)
- Yêu cầu: Tìm diện tích phần giao nhau (nếu có).
-  Chiều ngang giao khi: max(x1, u1) < min(x2, u2)
- Tính chiều ngang phần giao: w = max(0, min(x2, u2) - max(x1, u1))
- Tính chiều dọc phần giao: h = max(0, min(y2, v2) - max(y1, v1))

Code tham khảo

fi=open("HCN.INP")
fo=open("HCN.OUT","w")
x1, y1, x2, y2 = map(int, fi.readline().split())
u1, v1, u2, v2 = map(int, fi.readline().split())

w = max(0, min(x2, u2) - max(x1, u1))
h = max(0, min(y2, v2) - max(y1, v1))

fo.write(f"{w*h}")

fi.close()
fo.close()

Bài 3. Xin chào 

Đề bài

Phân tích

• Xác định xem mỗi câu chào có thể biến đổi (bằng cách xóa chữ cái) thành từ khóa Key hay không.

Ví dụ:

• Key: hello

• Câu: ahhellllloou → Có thể bỏ bớt ký tự để được hello → YES

• Câu: hlelo → Không thể xóa để được hello theo đúng thứ tự → NO

Duyệt tuần tự từ trái qua phải:

• Với mỗi ký tự trong câu chào, so sánh với ký tự hiện tại trong Key.

• Nếu trùng: tăng chỉ số trong Key.

• Nếu đến hết Key: trả về "YES", ngược lại "NO".

Code tham khảo

def Ss_key(key, s):
    i = 0
    for c in s:
        if i < len(key) and c == key[i]:
            i += 1
        if i == len(key):
            return "YES"
    return "NO"
fi=open("XINCHAO.INP")
fo=open("XINCHAO.OUT","w")
dong = fi.read().splitlines()
n = int(dong[0])
key = dong[1]
a = dong[2:2+n]
kq = [Ss_key(key, ai) for ai in a]
s='\n'.join(kq)
fo.write(f"{s}")
fi.close()
fo.close()

Bài 4: Mua quà lưu niệm

Đề bài

Phân tích

- An chọn mua m món quà trong n món (biết giá từng món).

- Sao cho độ chênh lệch nhỏ nhất giữa giá lớn nhất và nhỏ nhất trong m món được chọn.

 Ý tưởng:

- Sắp xếp danh sách giá.

- Khi sắp xếp xong, các phần tử gần nhau có giá gần nhau nhất, nên việc chọn m món liên tiếp sẽ dễ tạo ra chênh lệch nhỏ.

- Đoạn con là một dãy con liên tiếp dài đúng m phần tử trong danh sách đã sắp xếp

- Duyệt qua tất cả các dãy con này (tổng cộng n - m + 1 dãy con).

- Vì danh sách đã sắp xếp, ta chỉ cần tính: a[i + m - 1] - a[i]

                                      a[i]: phần tử nhỏ nhất trong cửa sổ

                                      a[i + m - 1]: phần tử lớn nhất trong cửa sổ

- Ta tìm chênh lệch nhỏ nhất

Code tham khảo

fi=open("MUAQUA.INP")
fo=open("MUAQUA.OUT","w")
m, n = map(int, fi.readline().split())
a = list(map(int, fi.readline().split()))
a.sort()
#Khởi tạo giá trị chênh lệch vô cùng lớn
min_cl= float('inf')

# Duyệt qua từng đoạn liên tiếp dài m
for i in range(n - m + 1):
    cl = a[i + m - 1] - a[i]
    if cl < min_cl:
        min_cl = cl
print(min_cl)
fi.close()
fo.close()