Вода
Недавно Сергей пошел к колодцу за водой, но так и не вернулся. Он взял с собой n канистр, каждую из которых он полностью наполнил водой. Теперь Сергей хочет доставить их в свой загородный дом. Вот в этом и заключается проблема. За один раз Сергей может унести не более 2 канистр — у него ведь всего две руки. Более того, он может нести не более k литров воды.
Теперь Сергей стоит у колодца и думает, за какое минимальное число раз он может отнести всю воду домой, и может ли вообще. Помогите ему решить эту задачу.
Технические условия
Входные данные
В первой строке входного файла два целых числа — n и k (1 ≤ n ≤ 105). Во второй строке n целых чисел — объемы канистр в литрах. Все числа во входном файле положительные и не превышают 109.
Выходные данные
Если Сергей не сможет унести всю воду домой, выведите «Impossible». Иначе выведите одно число — минимальное необходимое число раз.
Информация о задаче
Лимит времени: 2 секундыЛимит памяти: 64 MB
Баллы за пройденный тест: 3.7037
Сложность: 44% 70/126
Классификация: Жадный алгоритм
Пример
Пример входных данныхSample 1 4 4 1 2 3 3 Sample 2 4 2 1 2 3 3 |
Пример выходных данныхSample 1 3 Sample 2 Impossible |
| ← Герой гитары | Список задач | Древняя рукопись → |
