Денис ушел на каникулы и решил освежить в памяти собрание «Искусство программирования» Дональда Кнута. Он хочет прочитать подряд как можно больше томов, начиная с первого, потом второй, третий и так далее.
Всего на его полке N томов из «Искусства программирования», но случилось так, что не все тома идут подряд — среди их номеров могут быть пропуски. Денис взялся за дело серьезно и поэтому хочет читать тома именно подряд, без пропусков. В случае нехватки какой-либо книги, он может пойти в местную библиотеку и поменять там два любых тома на один, нужный ему. Подобный обмен можно проводить сколько угодно раз, пока на руках у Дениса есть хотя бы две книги. Чтобы не терять время, Денис хочет поменять все необходимые книги до начала чтения первого тома. Помогите Денису — определите, какое максимальное количество томов он сможет прочесть.
1 Ответ
Объяснение:
volumes — сортируем номера томов
need — следующий нужный том (1, 2, 3…)
extra — количество «лишних» томов для обмена
Если том ≤ нужного — учитываем как лишний
Если том > нужного — проверяем, можем ли заполнить пропуск обменами
В конце need — 1 — количество полученных томов