printРабочее место участника

printЗадачи

2428. Рамки

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Имеется несколько планок разной длины, из которых нужно сделать рамки для фотографий. При изготовлении рамки планки нельзя разрезать на части или соединять несколько планок в одну длинную планку. Рамка должна быть прямоугольной (в т.ч. квадратной), при этом длинная сторона должна быть не более чем в два раза длиннее короткой.
Напишите программу, которая определяет, какое максимальное количество рамок можно сделать из заданного набора планок.
Первая строка ввода содержит одно целое число `N` — количество планок. Следующая строка содержит `N` целых чисел — длины рамок.
Вывести одно целое число — максимальное количество рамок.

Пример ввода

10
5 5 10 5 8 8 10 7 25 25

Пример вывода

1
Пояснение к примеру: делаем одну рамку из планок 5,5,8,8. Планки 10,10 и 25,25 для рамки не подойдут, так как планка длиной 25 длиннее более чем в 2 раза планки длиной 10.
Описание подзадач и системы оценивания
Подзадача 1 (10 баллов)
`1\ ≤\ N\ ≤\ 100`, длины планок от 1 до 100.
В этой подзадаче 2 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ N\ ≤\ 100000`, длины планок от 1 до 1000.
В этой подзадаче 5 тестов, каждый тест оценивается в 6 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (30 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ N\ ≤\ 1000`, длины планок от `5*10^8` до `10^9`.
В этой подзадаче 5 тестов, каждый тест оценивается в 6 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 4 (30 баллов)
Необходимые подзадачи: 1,2,3.
`1\ ≤\ N\ ≤\ 100000`, длины планок от `1` до `10^9`.
В этой подзадаче 5 тестов, каждый тест оценивается в 6 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
loading