Esconder caixas
Dado que temos
n caixas, o objetivo é colocar o maior número possível de caixas dentro de outras. Existem algumas regras que devemos seguir:- Só é possível colocar uma caixa pequena dentro de outra maior se a maior tiver pelo menos o dobro do tamanho da menor.
- Cada caixa grande só pode conter 1 caixa dentro (nenhuma caixa pode conter 2 ou mais caixas).
Qual seria o número mínimo possível de caixas visíveis ao final?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ), que representa o número de caixas.A linha seguinte contém
n inteiros separados por espaços (1 ≤ ≤ ), indicando o tamanho de cada caixa.Saída
O programa deve imprimir o menor número possível de caixas visíveis ao final.
Exemplos
Entrada | Saída |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
Explicação
- 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