Ổ cắm

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong nhà Nam hiện đang có n ổ cắm điện rời. Số lượng chỗ cắm trên mỗi ổ cắm điện này lần lượt là \(a_1,a_2,a_3,…,a_n\) chỗ cắm. Trên tường nhà Nam có một chỗ cắm cố định đang có điện. Vậy để cho một ổ cắm điện rời có điện thì phải cắm ổ cắm đó vào chỗ cắm cố định trên tường. Chúng ta cũng có thể cắm ổ cắm điện rời này vào một ổ cắm điện rời khác đang có điện.

Nam có m thiết bị sử dụng điện, để sử dụng thì các thiết bị này cần được cắm vào ổ cắm trên tường hoặc ổ cắm rời đang có điện. Bạn hãy giúp Nam tìm ra số ổ cắm rời ít nhất cần dùng để có thể sử dụng tất cả m thiết bị điện này.

Input

Dòng thứ nhất gồm 2 số nguyên n,m cách nhau một khoảng trắng, dữ liệu vào đảm bảo \(1 ≤ n,m ≤ 10000, n\) là số lượng ổ cắm và \(m\) là số lượng thiết bị.
Dòng thứ hai gồm n số nguyên \(a_1,a_2,a_3,…,a_n\) là số chỗ cắm trên các ổ cắm rời tương ứng, mỗi số cách nhau một khoảng trắng, dữ liệu vào đảm bảo \(1 ≤ a_i ≤ 50\).

Output

Là số nguyên cho biết số ổ cắm rời ít nhất cần sử dụng là bao nhiêu. Nếu đã sử dụng hết tất cả ổ cắm rời mà vẫn không đủ, in ra \(−1\).

Example

Test 1

Input

3 4
3 2 2

Output

Test 2

Input

4 7
3 3 2 4

Output

Bình luận

-1

def min_power_strips_needed(n, m, outlets):
# Sắp xếp các ổ cắm theo số lượng cổng cắm giảm dần
outlets.sort(reverse=True)

# Khởi tạo số cổng cắm hiện có từ ổ cắm trên tường
current_available = 1  # Bắt đầu với 1 cổng cố định trên tường
used_strips = 0

# Tính số cổng cắm cần thiết
required_outlets = m

for outlets_count in outlets:
    if current_available >= required_outlets:
        return used_strips

    # Sử dụng thêm ổ cắm
    current_available += (outlets_count - 1)
    used_strips += 1

# Kiểm tra lần cuối nếu đã sử dụng tất cả ổ cắm
if current_available >= required_outlets:
    return used_strips
else:
    return -1

Đọc dữ liệu đầu vào

n, m = map(int, input().split())
outlets = list(map(int, input().split()))

Tính toán và in kết quả

print(min_power_strips_needed(n, m, outlets))

3 bình luận nữa