Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2428. Рамки
Жадные алгоритмыБыстрая сортировка
Олимпиадные задачи на русском языке
| 02/11/2018 | Муниципальный этап 7-8 классы (4) |
| 14/07/2021 | Лето 2021-8 (C) |
| 13/07/2022 | Лето 2022-8 (B) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
