Лодки на Иссык-Куле
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
На берегу ждут n туристов, вес i-го равен aᵢ. Лодка вмещает не более двух человек, и их суммарный вес не должен превышать W. Вес каждого туриста не больше W. Какое наименьшее число рейсов потребуется, чтобы перевезти всех?
Формат ввода
В первой строке даны n и W. Во второй — веса.
Формат вывода
Выведите наименьшее число лодок.
Ограничения
1 ≤ n ≤ 2 · 10⁵, 1 ≤ aᵢ ≤ W ≤ 10⁹.
Примеры
Пример 1
Ввод:
4 10
3 5 5 9
Вывод:
3
Пример 2
Ввод:
3 4
4 4 4
Вывод:
3
Комментарии