BÀI TẬP Ở NHÀ

https://www.baitaponha.com

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

Giải câu 2: Ổ Điện (Đề thi HSG tỉnh lớp 12 Nghệ An năm học 2022-2023)

Giải câu 2: Ổ Điện (Đề thi HSG tỉnh lớp 12 Nghệ An năm học 2022-2023)

Câu 2, Ổ điện - Đề thi HSG tin 12 tỉnh Nghệ An năm 2022-2023

Đây là một bài xử lý mảng một chiều cũng khá hay, bài này cũng tương đối dễ lấy điểm cho học sinh. Tuy nhiên đề thực hiện được bài này phải biết tư duy thực tế kết hợp với cách xử lý vòng lặp khi duyệt mảng. Mời thầy cô và các bạn tham khảo cách giải bài này với ngôn ngữ Python.

     Đứ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: 

Tính xem, số lượng ổ điện rời ít nhất cần dùng là bao nhiê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ụ    

  Odien.Inp  

   Odien.Out   

Giải thích

3  4

3  2  2

2

Có 3 ổ điện rời và 4 máy tính.

Có thể chọn 2 ổ điện là ổ điện 1 và 2:

  • Ổ điện 1 cắm vào ổ điện nguồn.

  • Ổ điện 2 cắm vào 1 khe cắm của ổ điện 1.

Như vậy cả 2 ổ điện đều có điện. Ô điện 1 còn 2 khe cắm chưa sử dụng, ổ điện 2 còn 2 khe cắm chưa sử dụng. Tổng số khe cắm có điện chưa sử dụng là 4. Sử dụng 4 khe cắm này để cung cấp điện cho 4 máy tính bằng cách mỗi máy tính được cắm vào 1 khe.

5  5

1  3  1  2  1

 

Có 5 ổ điện rời và 5 máy tính. Không thể sử dụng 5 ở điện rời để cung cấp điện cho 5 máy tính.

Giải:

Cách giải bài này như sau: Ta phải sắp xếp dãy ổ cắp điện theo thứ tự giảm dần của lỗ cắm của ổ.
  • 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:

Nhóm facebook: f / BAITAPONHA
Trang facebook: f / HỌC MÃI

Tác giả: admin

Bạn đã không sử dụng Site, Bấm vào đây để duy trì trạng thái đăng nhập. Thời gian chờ: 60 giây