34ος ΠΔΠ Γ' Φάση
Οι ορχήστρες (orchestras)
[30 Μονάδες]
Σε μια ορχήστρα συμμετέχουν \(K\) διαφορετικά μουσικά όργανα. Για κάθε ένα από αυτά τα μουσικά όργανα έχουμε στη διάθεσή μας \(N\) μουσικούς, επομένως \(K\cdot N\) μουσικούς συνολικά. Μπορούμε έτσι να σχηματίσουμε \(N\) διαφορετικές ορχήστρες.
Για να συμμετάσχει ένας μουσικός σε μια ορχήστρα πρέπει να λάβει ένα χρηματικό ποσό ως αποζημίωση και, για κάθε μουσικό, γνωρίζουμε ποιο είναι αυτό το ποσό. Άλλοι μουσικοί είναι “ακριβότεροι”, δηλαδή ζητάνε μεγαλύτερο ποσό αποζημίωσης, και άλλοι “φθηνότεροι”, δηλαδή ζητάνε μικρότερο ποσό αποζημίωσης.
Ονομάζουμε “απόκλιση” μιας ορχήστρας τη διαφορά μεταξύ του ποσού αποζημίωσης που λαμβάνει ο ακριβότερος μουσικός που συμμετέχει σε αυτήν και του ποσού αποζημίωσης που λαμβάνει ο φθηνότερος μουσικός που συμμετέχει σε αυτήν. Θέλουμε να τοποθετήσουμε τους μουσικούς στις Ν ορχήστρες με τέτοιο τρόπο ώστε η μεγαλύτερη απόκλιση D που θα εμφανιστεί σε μία ή περισσότερες από τις σχηματιζόμενες ορχήστρες να είναι όσο γίνεται μικρότερη.
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις τιμές του N και του K, καθώς και τα ποσά αποζημίωσης που ζητούν οι μουσικοί και θα εκτυπώνει την ελάχιστη δυνατή τιμή του \(D\).
Αρχεία Εισόδου:
Το αρχείο εισόδου με όνομα orchestras.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή έχει δύο ακέραιους αριθμούς \(N\) και \(K\), χωρισμένους με ένα κενό διάστημα: το πλήθος των ορχηστρών και το πλήθος των οργάνων. Ακολουθούν \(K\) γραμμές, μία για κάθε μουσικό όργανο. Κάθε μία από αυτές περιέχει \(N\) θετικούς ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα: την επιθυμητή αποζημίωση καθενός μουσικού που παίζει το αντίστοιχο μουσικό όργανο.
Αρχεία Εξόδου:
Το αρχείο εξόδου με όνομα orchestras.out είναι αρχείο κειμένου που περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την ελάχιστη δυνατή τιμή του \(D\).
Παραδείγματα Αρχείων εισόδου - εξόδου:
1o
| orchestras.in | orchestras.out |
|---|---|
| 5 2 20 12 5 18 11 8 19 16 7 17 |
4 |
Εξήγηση: Έχουμε \(2\) μουσικά όργανα και καθένα από αυτά το παίζουν \(5\) μουσικοί. Μπορούμε να φτιάξουμε \(5\) ορχήστρες ως εξής:
- στην 1η να βάλουμε τους μουσικούς με αποζημίωση \(18\) και \(19\) (απόκλιση \(1\))
- στην 2η τους μουσικούς με αποζημίωση \(12\) και \(16\) (απόκλιση \(4\))
- στην 3η τους μουσικούς με αποζημίωση \(7\) και \(11\) (απόκλιση \(4\))
- στην 4η τους μουσικούς με αποζημίωση \(5\) και \(8\) (απόκλιση \(3\)) και
- στην 5η τους μουσικούς με αποζημίωση \(20\) και \(17\) (απόκλιση \(3\)).
Η μέγιστη απόκλιση \(D\) που πετυχαίνουμε έτσι είναι \(4\). Δεν υπάρχει τρόπος να σχηματίσουμε τις \(5\) ορχήστρες ώστε να πετύχουμε μικρότερη τιμή του \(D\).
2o
| orchestras.in | orchestras.out |
|---|---|
| 4 2 17 42 7 23 42 23 17 7 |
0 |
Εξήγηση: Μπορούμε να σχηματίσουμε \(4\) ορχήστρες στις οποίες και οι δύο μουσικοί να λαμβάνουν την ίδια αποζημίωση.
3o
| orchestras.in | orchestras.out |
|---|---|
| 2 3 25 48 27 16 7 15 |
33 |
Περιορισμοί:
- \(1 \leq N \leq 5.000\)
- \(2 \leq K \leq 200\)
- Η επιθυμητή αποζημίωση κάθε μουσικού δε θα υπερβαίνει το \(10^6\)
- Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(K = 2\)
- Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(1 \leq N \leq 10\)
Προσοχή:
Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.
Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με έναν χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.