37ος ΠΔΠ Α' Φάση
Όμοιες πίτσες (samepizzas)
Σας παρουσιάζουμε τον πρωταγωνιστή μας τον Τάκη, έναν νεαρό Έλληνα που το όνειρό του από μικρό παιδί είναι να ανοίξει την δική του πιτσαρία. Σήμερα, βρίσκεται πολύ κοντά στο να κάνει αυτό το όνειρό του πραγματικότητα.
Για να εξοικονομήσει όσο γίνεται περισσότερα χρήματα, το πλάνο του Τάκη είναι να μην προσλάβει προσωπικό, αλλά να φτιάχνει και να σερβίρει ο ίδιος τις πίτσες του. Στην αποθήκη του διαθέτει \(N\) υλικά. Οι ποσότητες των διάφορων υλικών συμβολίζονται με τους θετικούς ακέραιους \(a_1, a_2, \ldots , a_N\). Ο σκοπός του Τάκη είναι να δημιουργήσει όσο το δυνατόν περισσότερες όμοιες πίτσες μπορεί. Λέμε ότι κάποιες πίτσες είναι όμοιες όταν όλες:
- αποτελούνται από τα ίδια υλικά και
- διαθέτουν την ίδια (θετική ακέραια) ποσότητα από καθένα από αυτά τα υλικά.
Προκειμένου οι πίτσες του να μην είναι “βαρετές”, ο Τάκης έθεσε ακόμα έναν περιορισμό: πρέπει κάθε πίτσα να περιέχει τουλάχιστον \(K\) διαφορετικά υλικά. Να υπολογίσετε ποιο είναι το μέγιστο πλήθος από όμοιες πίτσες που μπορεί να δημιουργήσει ο Τάκης, τηρώντας ταυτόχρονα αυτόν τον περιορισμό.
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο samepizzas.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο samepizzas.out.
Δεδομένα εισόδου (samepizzas.in)
Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει δύο ακέραιους αριθμούς \(N\) και \(K\), χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των υλικών που διαθέτει ο Τάκης και το ελάχιστο δυνατό πλήθος διαφορετικών υλικών που μπορεί να περιέχει κάθε πίτσα του. Η τρίτη γραμμή αποτελείται από \(N\) ακέραιους αριθμούς \(a_1, a_2, \ldots , a_N\), χωρισμένους ανά δύο με κενό διάστημα: τις ποσότητες των υλικών.
Δεδομένα ειξόδου (samepizzas.out)
Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το μέγιστο πλήθος από όμοιες πίτσες που μπορεί να δημιουργήσει ο Τάκης πληρώντας τον παραπάνω περιορισμό.
Παράδειγμα αρχείων εισόδου-εξόδου
| samepizzas.in | samepizzas.out |
|---|---|
| 4 5 3 12 6 7 6 4 |
6 |
Εξήγηση παραδείγματος:
Ο Τάκης μπορεί να φτιάξει \(6\) όμοιες πίτσες, που καθεμία περιέχει δύο μονάδες από το πρώτο, μία μονάδα από το δεύτερο και μία μονάδα από το τέταρτο υλικό. Μπορεί επίσης να κάνει και άλλους συνδυασμούς υλικών που δίνουν \(6\) όμοιες πίτσες, δεν μπορεί όμως με κανέναν τρόπο να φτιάξει περισσότερες.
Περιορισμοί
- \(1 \leq K \leq N \leq 200.000\),
- \(1 \leq a_i \leq 1.000.000.000\).
Υποπροβλήματα
- (10 βαθμοί) \(N = 2\)
- (15 βαθμοί) \(K = N\)
- (25 βαθμοί) \(K = 1\)
- (10 βαθμοί) \(N \leq 10.000\)
- (40 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί
Παρατηρήσεις
Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.