Nascondere scatole
Date n scatole, l’obiettivo è quello di nascondere il maggior numero possibile di scatole all’interno di altre. Ci sono alcune regole da seguire:
È possibile collocare una scatola più piccola dentro un’altra più grande soltanto se quest’ultima ha dimensioni almeno doppie rispetto alla prima.
In ogni scatola può essere inserita al massimo un’unica scatola (nessuna scatola può contenerne due o più).
Alla fine, qual è il numero minimo di scatole visibili?
Dati in ingresso
La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ ), che rappresenta il numero di scatole.
La riga successiva contiene n interi separati da spazio (1 ≤ ≤ ), che indicano la dimensione di ciascuna scatola.
Dati in uscita
Il programma deve stampare il numero minimo possibile di scatole visibili alla fine.
Esempi
Ingresso | Uscita |
|---|---|
8 | 5 |
8 | 5 |
Spiegazione
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