Спрятать коробки
Имеется
n коробок, и вы хотите поместить как можно больше из них внутрь других коробок. При этом необходимо соблюдать несколько правил:- Маленькую коробку можно поместить в другую, большую коробку только в том случае, если большая коробка по размеру как минимум вдвое больше маленькой.
- В одну коробку можно положить только одну другую коробку (никакая коробка не может содержать две или более коробок).
Каково минимальное количество коробок, которые останутся видимыми в конце?
Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ ), обозначающее количество коробок.Следующая строка содержит
n целых чисел, разделенных пробелами: (1 ≤ ≤ ), где каждое число указывает размер соответствующей коробки.Выходные данные
Программа должна вывести минимально возможное количество коробок, которые останутся видимыми в итоге.
Примеры
Input | Output |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
Пояснение
- 7 5 2 6 4 8 9 2 → (2, 5) (2, 6) (7) (4, 8) (9)
- 3 1 8 2 6 5 6 9 → 1 2 3 5 6 6 8 9 → (1, 5) (2, 6) (3, 6) (8) (9)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB