COCI-16 (2016) - Γύρος #6 - 1 (Hindeks)

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Hindeks

Πώς αξιολογούμε την επιτυχία ενός επιστήμονα; Με τον αριθμό των δημοσιευμένων εργασιών ή με τον αντίκτυπό τους - πιο συγκεκριμένα, τον αριθμό των αναφορών; Και τα δύο στοιχεία έχουν σημασία. Λέμε ότι μια επιστημονική εργασία έχει βαθμολογία αναφοράς C εάν άλλοι επιστήμονες παρέθεσαν την εν λόγω εργασία στην εργασία τους (αναφέρθηκαν σε αυτήν) συνολικά C φορές. Μία από τις πιθανές μετρήσεις της επιτυχίας των επιστημόνων είναι ο δείκτης h που λαμβάνει υπόψη τόσο την ποσότητα των εργασιών όσο και τις βαθμολογίες των παραπομπών τους.

Ο δείκτης h ενός επιστήμονα ορίζεται ως ο μεγαλύτερος αριθμός H με τις ακόλουθες ιδιότητες: ο επιστήμονας μπορεί να επιλέξει H εργασίες έτσι ώστε η βαθμολογία τους να είναι τουλάχιστον H. Για παράδειγμα, εάν ένας επιστήμονας έγραψε 10 εργασίες, έτσι ώστε καθεμία από αυτές να έχει αναφερθεί 10 ή περισσότερες φορές, ο δείκτης h του είναι (τουλάχιστον) 10.

Γράψτε ένα πρόγραμμα που εισάγει τις βαθμολογίες παραπομπών όλων των εργασιών ενός δεδομένου επιστήμονα και εξάγει τον δείκτη h αυτού.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό N\;(1 \le N \le 500\,000), τον αριθμό των εργασιών ενός δεδομένου επιστήμονα.
Η ακόλουθη γραμμή περιέχει N μη αρνητικούς ακέραιους που βρίσκονται στο διάστημα [0, 1\,000\,000], τις βαθμολογίες παραπομπών των αντίστοιχων εργασιών.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο δείκτη h.

Παραδείγματα

input

5
1 1 4 8 1

output

2
Επεξήγηση του 1ου παραδείγματος:

Ο επιστήμονας έχει δύο εργασίες με βαθμολογίες παραπομπών μεγαλύτερες από 2 ή ίσες με 2 (οι εργασίες με βαθμολογίες παραπομπών 4 και 8).


input

5
8 5 3 4 10

output

4
Επεξήγηση του 2ου παραδείγματος:

Ο επιστήμονας έχει τέσσερις εργασίες με βαθμολογίες παραπομπών μεγαλύτερες από 4 ή ίσες με 4 (οι εργασίες με βαθμολογίες παραπομπών 8, 5, 4 και 10).


Comments

There are no comments at the moment.