Задача C. Выдача премий ≡

Условие

В компании работает N человек. Зарплата i-о сотрудника составляет a_i бурлей.

Близится новый год, пора решать кто из сотрудников получит премию. Если на премию будет представлено k человек, то первому будет назначена премия в k бурлей, второму — в k − 1 бурлей и т.д. Порядок назначения на премии совпадает с порядком сотрудников, в котором они перечислены.

Но назначение премии и её выплата не одно и тоже. Дело в том, что размер выплачиваемой премии не может превышать половину зарплаты. То есть, если у сотрудника зарплата 9 бурлей, а назначена премия в 100 бурлей, то он получит лишь 4 бурля (выплата не целого числа бурлей не осуществляется).

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

Помогите руководству компании определить максимальное количество человек, которым можно выплатить премию, так, чтобы это не оказало большего влияния на капитал компании.

Требуется написать программу, которая считает количество сотрудников и их зарплаты, и вычислит максимальное количество сотрудников, которые смогут получить премию.

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

Первая строка содержит одно целое число N — количество работников.

Далее следует N строк, в каждой из которых находится по одному целому числу a_i — зарплата i-го работника.

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁶

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примерам

В первом примере суммарная зарплата двух последних сотрудников равна 5. Этого не хватит, чтобы выдать премию трём другим сотрудникам, так как их премия составит 6 = 3 + 2 + 1.

Во втором примере суммарная зарплата двух последних сотрудников будет равна премии первых двух: 5 = 2 + 2 + 1, так как первый сотрудник не может получать премию больше, чем 5 / 2 = 2.

Примеры тестов

5
6
4
7
3
2

2

5
5
4
7
3
2

3

5 
1
2
1
1
1

4

Разбор

Решить данную задачу линейно очень сложно. При увеличении количества сотрудников на один может быть очень сложно определить на сколько изменится сумма выплаченных премий.

Поэтому следует решать эту задачу методом бинарного поиска.

Метод бинарного поиска

Имеется неубывающая или невозрастающая функция. На определенном отрезке требуется найти точку, значение функции в которой не превосходит какого-то фиксированного значения. Проверим середину отрезка поиска: если значение в ней удовлетворяет условию, то на середину сдвигается одна граница отрезка, иначе другая. После процесс повторяется для нового отрезка. И так до тех пор, пока отрезок не станет точкой, которая и будет ответом. Известно, что бинарный поиск имеет логарифмическое время работы, так как после каждой проверки отрезок поиска уменьшается в два раза.

Полное решение

В данной задаче бинарным поиском будем искать количество сотрудников с премией. Проверка заключается в следующем: в цикле посчитаем сумму премий и сумму зарплат сотрудников без премии. Если первое значение не превосходит второе, то такое количество сотрудников могло получить премии.

Частичные решения

Первую подзадачу можно решить каким-нибудь неэффективным кубическим решением. Автор задачи не смог придумать ни одного такого решения.

Вторую и третью подзадачи можно решить квадратичным решением. Суть решения: первым циклом переберем количество сотрудников с премией, а вторым циклом посчитаем сумму премий и сумму зарплат сотрудников без премии. Если такое решение не учитывает то, что суммы могут быть большими и следует использовать 64-х битный тип данных, то будет зачтена только вторую подзадачу (тоже самое касается и полного решения). Если же решение учитывает данную особенность, то будет зачтена и третья подзадача.