У Васи есть n альбомов для спичечных этикеток, каждый с вместимостью k1, k2, ..., kn этикеток. Вася хочет, чтобы даже

Aleksandrovich

1

python

def check_albums(albums):

    # Проверяем, имеет ли Вася достаточно этикеток для каждого альбома

    for album in albums:

        if sum(albums) - album < album:

            return False

    return True



def find_minimum_labels(albums):

    # Используем метод двоичного поиска для определения минимального количества элементов

    # Устанавливаем нижнюю и верхнюю границы для двоичного поиска

    left = 1

    right = sum(albums)

    

    while left < right:

        mid = (left + right) // 2

        

        # Проверяем, может ли Вася сохранить все этикетки при потере альбома с емкостью mid

        if check_albums([album if album <= mid else mid for album in albums]):

            right = mid

        else:

            left = mid + 1

    

    return left



# Пример использования

n = int(input("Введите количество альбомов: "))

albums = []

for i in range(n):

    album_capacity = int(input(f"Введите вместимость альбома {i + 1}: "))

    albums.append(album_capacity)



minimum_labels = find_minimum_labels(albums)

print(f"Минимальное количество этикеток для сохранения хотя бы одной копии после потери любого альбома: {minimum_labels}")