25ος ΠΔΠ Καμπ (juniors)
Ενυδρείο (fishtank)

Σε ένα ενυδρείο θέλουμε να τοποθετήσουμε \(N\) ψάρια. Κάθε ψάρι χαρακτηρίζεται από το μέγεθός του το οποίο, χάριν απλότητας, το παριστάνουμε με ένα θετικό φυσικό αριθμό. Όμως, όπως όλοι ξέρουμε, το μεγάλο ψάρι τρώει το μικρό! Στο ενυδρείο μας, αυτό σημαίνει ότι ένα ψάρι με μέγεθος \(a\) τρώει κάθε άλλο ψάρι που έχει μέγεθος (αυστηρά) μικρότερο από \(a / 2\). Αν λοιπόν βάλουμε τα ψάρια στο ενυδρείο χωρίς να το πολυσκεφτούμε και τα αφήσουμε στην ησυχία τους, μετά από λίγη ώρα μάλλον θα έχουν μείνει πολύ λιγότερα!

Ο σκοπός μας είναι να βρούμε πόσα είναι τα περισσότερα ψάρια που μπορούμε να βάλουμε στο ενυδρείο χωρίς να αλληλοφαγωθούν.

Αρχεία Εισόδου (fishtank.in):

Η είσοδος θα αποτελείται από δύο γραμμές. Η πρώτη γραμμή θα περιέχει μόνο έναν φυσικό αριθμό, το \(N\). Η δεύτερη γραμμή θα περιέχει \(N\) θετικούς φυσικούς αριθμούς \(x_1, x_2, \ldots, x_N\), χωρισμένους ανά δύο με ένα κενό διάστημα: τα μεγέθη των ψαριών.

Αρχεία Εξόδου (fishtank.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει μόνο έναν φυσικό αριθμό \(K \leq N\): το μέγιστο πλήθος ψαριών που μπορούμε να βάλουμε στο ενυδρείο χωρίς κανένα από αυτά να μπορεί να φάει κάποιο άλλο.

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

fishtank.in	fishtank.out
7 5 9 8 4 2 4 6	5

2^o

fishtank.in	fishtank.out
3 1 5 10	2

3^o

fishtank.in	fishtank.out
6 5 8 7 7 4 6	6

Εξήγηση παραδειγμάτων: Σε κάθε παράδειγμα φαίνεται υπογραμμισμένο ένα δυνατό υποσύνολο των ψαριών, τα οποία μπορούν να τοποθετηθούν στο ενυδρείο χωρίς να αλληλοφαγωθούν. Το υποσύνολο αυτό έχει το μεγαλύτερο δυνατό πληθάριθμο. Προσέξτε ότι ίσως υπάρχουν και άλλα υποσύνολα με τον ίδιο πληθάριθμο, π.χ. στο 2^ο παράδειγμα θα μπορούσε να επιλεγεί οποιοδήποτε ψάρι για το ενυδρείο.

Περιορισμοί:

• \(1 \leq N \leq 1.000.000\).
• \(1 \leq x_i \leq 1.000.000.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(16\) MB.