electicode
ГлавнаяКурсыРесурсыЗадачи
...

Бит-дни

Ограничение времени: 1500msОграничение памяти: 512MB
Все решения

Описание задачи

В мастерской есть nnn станков. Станок iii должен быть отремонтирован ровно aia_iai​ раз.

Мастерская работает по дням, пронумерованным 1,2,3,…1, 2, 3, \ldots1,2,3,….

В каждый день можно выполнить не более одного ремонта. Однако не каждый станок доступен в каждый день.

Для положительного целого числа ddd запишем ddd в двоичном виде. Станок iii доступен в день ddd, если (i−1)(i-1)(i−1)-й бит числа ddd равен 11.

Здесь биты нумеруются с 000, начиная с младшего бита.

Например:

  • в день 111 двоичное представление равно 111, поэтому доступен только станок 111;
  • в день 222 двоичное представление равно 101010, поэтому доступен только станок 222;
  • в день 333 двоичное представление равно 1111, поэтому доступны станки и ;

Ваша задача — найти минимальное число дней, после которого возможно завершить все ремонты.

Иными словами, найдите наименьшее целое число DDD такое, что ремонты можно запланировать на дни 1,2,…,D1, 2, \ldots, D1,2,…,D, выполняя не более одного ремонта в день, и каждый станок iii отремонтирован ровно aia_iai​ раз.

Формат ввода

Первая строка содержит одно целое число nnn (1≤n≤201 \le n \le 201≤n≤20) --- количество станков.

Вторая строка содержит nnn целых чисел a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​ () --- требуемое число ремонтов для каждого станка.

Формат вывода

Выведите одно целое число --- минимально возможное значение DDD.

Оценивание

ПодзадачаБаллыОграничения
111101010n≤5n \leq 5n≤5, ai≤5a_i \leq 5a

Примеры

Пример 1
Ввод
2
1 1
Вывод
2
Объяснение

В первом примере машина 111 доступна в день 111, а машина 222 доступна в день 222.

Таким образом, мы можем отремонтировать машину 111 в день 111 и машину в день .

© 2026 Electicode. All rights reserved.

1
11
111
222
  • в день 555 двоичное представление равно 101101101, поэтому доступны станки 111 и 333.
    • 1≤ai≤10151 \le a_i \le 10^{15}
    1≤ai​≤1015
    i
    ​
    ≤
    5
    222151515n≤10n \leq 10n≤10, ∑ai≤2000\sum a_i \leq 2000∑ai​≤2000
    333202020n≤12n \leq 12n≤12, ai≤106a_i \leq 10^6ai​≤106
    444202020n≤20n \leq 20n≤20, ai≤106a_i \leq 10^6ai​≤106
    555353535Без дополнительных ограничений.
    222
    222
    Пример 2
    Ввод
    2
2 1
    Вывод
    3
    Объяснение

    Во втором примере первые три дня таковы:

    • день 111: доступен только станок 111;
    • день 222: доступен только станок 222;
    • день 333: доступны станки 111 и 222.

    Одно оптимальное расписание:

    • ремонтировать станок 111 в день 111;
    • ремонтировать станок 222 в день 222;
    • ремонтировать станок 111 в день 333.

    Таким образом, все ремонты завершены через 333 дня.

    Пример 3
    Ввод
    3
3 1 1
    Вывод
    5
    Объяснение

    В третьем примере первые пять дней таковы:

    ДеньДвоичноеДоступные машины
    111111111
    222101010222
    3331111111,21, 21,2
    444100100100333
    5551011011011,31, 31,3

    Один из возможных оптимальных графиков:

    • ремонтировать машину 111 в день 111;
    • ремонтировать машину 222 в день 222;
    • ремонтировать машину 111 в день 333;
    • ремонтировать машину 333 в день 44;

    Итак, ответ — 555.

    4
  • ремонтировать машину 111 в день 555.