Ổ Điện | Đề thi HSG tin 12 Nghệ An | năm học 2022-2023

     Đức cùng nhóm bạn của mình được thầy giáo giao nhiệm vụ hỗ trợ chuẩn bị phòng máy cho kì thi lập trình danh giá được tổ chức sắp tới. Phòng máy có m máy tính, công việc của nhóm Đức là sử dụng các ổ cắm điện có dây để cung cấp nguồn điện cho m máy tính. Phòng máy chỉ có một ổ điện có một khe cắm ở trên tường là đang có điện, và được gọi là ổ điện nguồn. Hiện tại trong nhà kho có n ổ cắm điện có dây, mỗi ổ điện có một số khe cắm và một đường dây nối có phích cắm để có thể cắm đến ổ điện khác. Ta gọi các ổ điện này là ổ điện rời. Một ổ điện rời có điện chi khi phích cắm của nó được cắm vào ổ điện nguồn hoặc cắm vào một khe của ổ điện rời đang có điện. Chú ý là chỉ có một ổ điện rời được cắm vào ổ điện nguồn và mỗi khe có nhiều nhất một phích cắm được cắm vào. Để cung cấp nguồn điện cho m máy tính, mỗi máy tính cần được cắm vào một khe của ổ điện rời đang có điện. Cho biết số khe cắm của ổ điện rời thứ i là ai (1 sai <10; i = 1, 2, 3, ...,n). Nhóm của Đức muốn sử dụng số ổ điện rời với số lượng ít nhất nhưng vẫn có thể cung cấp nguồn điện cho m máy tính.

 Yêu cầu: 

Dữ liệu

 cho trong tệp văn bản ODien.Inp gồm:
• Dòng 1 ghi 2 số nguyên dương n và m tương ứng là số ổ điện rời và số máy tính.
• Dòng 2 ghi n số nguyên dương a.i ( 1<= a.i <= 10) lần lượt là số khe cắm của n ổ điện rời.

Kết quả:

 ghi ra tệp văn bản ODien.Out gồm một số nguyên duy nhất là số ổ điện rời ít nhất cần sử dụng để cung cấp nguồn điện cho m máy tính. Nếu không thể cung cấp nguồn điện cho m máy tính khi sử dụng cả n ổ điện rời thì ghi ra −1.

Ví dụ    

Giải:

• Sau đó ta duyệt vòng lặp for qua từng ổ điện. Trong vòng lặp for ta kiểm tra nếu số máy tính còn lại <= 0 thì ta thoát khỏi vòng lặp for. Tiếp tục kiểm tra số máy tính còn lại > Khe cắm của ổ điệm đang xét thì số máy tính sẽ giảm đi số khe cắm trừ 1 (Vì trừ một chỗ để cắm ổ tiếp theo), đồng thời tăng biến cout, ngược lại số máy tính còn lại bé hơn hoặc bằng khe cắm của ổ đang xét thì số máy tính còn lại  thì số máy tính còn lại giảm đúng bằng số khe cắm của ổ đang xét, đồng thời ta tăng biến cout và thoát khỏi vòng for.
•  Sau khi thoát khỏi vòng for ( Có 2 trường hơp: TH1: đã duyệt hết vòng for; TH2 chưa duyệt hết vòng for nhưng số máy tính còn lại là đã hết. Lúc này ta kiểm tra xem nếu số máy tính còn lại mà > 0 thì gán biến cout = -1.
• Đến đấy chỉ việc ghi biến cout vào tếp OUT là xong.

Bài mẫu bằng Python: (Đã chủ thích trong code)

with open("ODien.Inp", "r") as f_in:
    n, m = map(int, f_in.readline().split())
    a = list(map(int, f_in.readline().split()))

# Sắp xếp giảm dần các ổ điện rời theo số khe cắm
a.sort(reverse=True)

# Tính số máy tính còn thiếu nguồn điện
so_may_con_lai = m

# Tính số ổ điện rời đã sử dụng
count = 0

# Duyệt qua từng ổ điện rời để cố gắng cung cấp nguồn điện cho số máy tính còn thiếu
for khe_cam in a:
    if so_may_con_lai <= 0:
        break
    if so_may_con_lai > khe_cam:
        so_may_con_lai -= (khe_cam-1)
    else: so_may_con_lai -= khe_cam
    count += 1

# Nếu vẫn còn máy tính cần nguồn điện thì không thể cung cấp được
if so_may_con_lai > 0:
    count = -1

# Xuất kết quả ra tệp văn bản ODien.Out
with open("ODien.Out", "w") as f_out:
    f_out.write(str(count))

Để nắm được thông tin cập nhật mới cũng như phản hồi về trang, các bạn tham gia nhóm facebook: