Ocultar cajas
Dadas
n cajas, deseas ocultar la mayor cantidad posible de esas cajas dentro de otras. Para ello, debes seguir varias reglas:- Puedes colocar una caja pequeña dentro de otra más grande solo si la caja más grande es al menos el doble de grande que la pequeña.
- Solo puedes colocar 1 caja dentro de otra (ninguna caja puede contener 2 o más cajas).
¿Cuál sería el número mínimo posible de cajas visibles al final?
Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ ), que representa el número de cajas.La siguiente línea contiene
n enteros separados por espacios (1 ≤ ≤ ), que indican el tamaño de cada caja.Salida
El programa debe imprimir el menor número posible de cajas visibles al final.
Ejemplos
Entrada | Salida |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
Explicación
- 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