Boxen verstecken
Angenommen, Sie haben
n Boxen und möchten so viele davon wie möglich in anderen Boxen verstecken. Dabei gelten folgende Regeln:- Eine kleinere Box darf nur in eine größere Box gelegt werden, wenn die größere mindestens doppelt so groß ist wie die kleinere.
- In jede Box darf nur eine (1) weitere Box gelegt werden (keine Box darf zwei oder mehr Boxen enthalten).
Wie viele Boxen sind am Ende mindestens noch sichtbar?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ), die für die Anzahl der Boxen steht.Die zweite Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ ), die die Größe jeder Box angeben.Ausgabe
Das Programm soll die kleinstmögliche Anzahl sichtbarer Boxen ausgeben.
Beispiele
Eingabe | Ausgabe |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
Erklärung
- 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