COCI-18 (2018) - Γύρος #4 - 5 (Akvizna)

View as PDF

Submit solution

Points: 45 (partial)
Time limit: 1.5s
Memory limit: 256M

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

Το 1 εναντίον 100 (1 vs.100) είναι ένα κουίζ που θα μπορούσαμε να παρακολουθήσουμε στις τηλεοράσεις πριν από μερικά χρόνια. Για τους σκοπούς αυτού του προβλήματος, θα απλοποιήσουμε ελαφρώς τους κανόνες του κουίζ.

Ο διαγωνιζόμενος απαντά σε ερωτήσεις και πρέπει να βγάλει εκτός παιχνιδιού 100 άτομα, που αγωνίζονται εναντίον του. Όλοι απαντούν την ίδια ερώτηση σε κάθε γύρο και όσοι απαντούν λάθος στην ερώτηση βγαίνουν εκτός. Το χρηματικό ποσό που παίρνει ένας διαγωνιζόμενος που καταφέρνει να βγάλει εκτός και τους 100 αντιπάλους είναι ίσο με το χρηματικό ποσό που κέρδισε σε κάθε γύρο. Σε κάθε γύρο, όλοι οι αντίπαλοι αξίζουν το ίδιο και όλοι οι αντίπαλοι μαζί αξίζουν 100.000 kunas (κροατικό νόμισμα). Το ποσό που κερδίζεται σε έναν γύρο είναι ίσο με το άθροισμα των αξιών των ατόμων που έχουν βγει εκτός σε αυτό τον γύρο. Για παράδειγμα, αν υπάρχουν 10 αντίπαλοι κάποια στιγμή, ο καθένας από αυτούς αξίζει 10.000 kunas και ο διαγωνιζόμενος θα πάρει 30.000 kunas, εάν καταφέρει σε αυτόν τον γύρο να βγάλει εκτός 3 αντιπάλους.

Ας πούμε ότι το κουίζ ονομάζεται 1 εναντίον N (1 vs. N) (δηλαδή ο παίκτης αγωνίζεται εναντίον N ατόμων) και ότι ο Mirko M. κατάφερε να βγάλει εκτός όλους τους αντιπάλους του σε ακριβώς K γύρους. Ποιο είναι το μέγιστο ποσό που θα μπορούσε να κερδίσει;

Είσοδος

Στη μοναδική γραμμή εισόδου υπάρχουν οι ακέραιοι αριθμοί N\;(1 \le N \le 100\,000) και K\;(1 \le K \le N).

Έξοδος

Εκτυπώστε το μέγιστο δυνατό ποσό που θα μπορούσε να κερδίσει ο Mirko M., διαιρεμένο με το 100.000.
Η απάντησή σας θα θεωρηθεί σωστή εάν η σχετική ή απόλυτη διαφορά από την επίσημη απάντηση είναι το πολύ 10^{-8}.

Βαθμολογία

Σε περιπτώσεις δοκιμής συνολικής αξίας 20 πόντων θα ισχύει N \le 100.
Σε περιπτώσεις δοκιμής συνολικής αξίας επιπλέον 45 πόντων, θα ισχύει ότι N \le 3\,000.

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

input

5 3

output

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

Ο Mirko Μ. έπαιξε εναντίον πέντε παικτών, τους οποίους έβγαλε εκτός σε τρεις γύρους.
Για να κερδίσει το μέγιστο δυνατό ποσό, έπρεπε πρώτα να πετάξει έξω τρεις αντιπάλους και μετά, για άλλες δύο φορές, να βγάλει εκτός από έναν.
Σε αυτήν την περίπτωση, το κερδισμένο ποσό είναι ίσο με (3/5 + 1/2 + 1/1) \cdot 100\,000 = 2.1 \cdot 100\,000 = 210\,000 kunas.


input

10 10

output

2.928968254

input

100 10

output

4.590928516

Comments

There are no comments at the moment.