Αρχική > 26ος ΠΔΠ

26ος ΠΔΠ Καμπ (κοινά)
Τηλεοπτική μετάδοση αγώνων (tvmatch)

Ένα τηλεοπτικό κανάλι έχει αγοράσει τα δικαιώματα προβολής των αγώνων του πρωταθλήματος ποδοσφαίρου. Επειδή πλήρωσε ένα σκασμό λεφτά, η διοργανώτρια αρχή επιτρέπει στο κανάλι να προσδιορίσει τον τρόπο διεξαγωγής του πρωταθλήματος που θα μεγιστοποιήσει την τηλεθέαση.

Μετά από αρκετή σκέψη, οι ιθύνοντες του καναλιού καταλήγουν στην εξής μορφή πρωταθλήματος. Το πρωτάθλημα ξεκινά με \(T\) ομάδες και αποτελείται από \(R\) γύρους. Σε κάθε γύρο, κάθε ομάδα παίζει μία φορά με όλες τις άλλες και, στο τέλος του γύρου, η ομάδα με τη χειρότερη βαθμολογία αποκλείεται από τη συνέχεια του πρωταθλήματος. Μετά το τέλος των \(R\) γύρων, πρωταθλήτρια είναι η ομάδα που προηγείται στη συνολική βαθμολογία.

Το κανάλι πρόκειται να μεταδώσει όλους τους αγώνες του πρωταθλήματος. Θέλει το πλήθος των αγώνων να είναι \(M\), αλλά δεν έχει προσδιορίσει τις επιθυμητές τιμές των \(T\) και \(R\).

Δεδομένου του \(M\), ζητείται να βρεθούν οι τιμές των \(T\) και \(R\) έτσι ώστε το συνολικό πλήθος αγώνων να είναι ίσο με \(M\). Αν αυτό δεν είναι εφικτό για κανένα συνδυασμό \(T\) και \(R\), το πρόγραμμά σας πρέπει να εκτυπώνει τη λέξη «IMPOSSIBLE». Αν είναι εφικτό για περισσότερους συνδυασμούς \(T\) και \(R\), να προτιμάται αυτός με τη μεγαλύτερη τιμή του \(R\).

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

Η είσοδος θα αποτελείται από μία γραμμή που θα περιέχει μόνο ένα φυσικό αριθμό, το \(M\).

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

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει είτε τη λέξη «IMPOSSIBLE», είτε ένα ζεύγος φυσικών αριθμών \(T\) και \(R\), χωρισμένων μεταξύ τους με ένα κενό διάστημα.

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

1o

tvmatch.in tvmatch.out
64 8 3

Εξήγηση 1ου παραδείγματος: Αν ξεκινήσουν \(8\) ομάδες, στον πρώτο γύρο θα παίξουν \(28\) αγώνες. Στο δεύτερο γύρο θα έχουν μείνει \(7\) ομάδες και θα παίξουν \(21\) αγώνες. Τέλος, στον τρίτο γύρο θα έχουν μείνει \(6\) ομάδες και θα παίξουν \(15\) αγώνες. Το σύνολο των αγώνων είναι \(28 + 21 + 15 = 64\). Προσέξτε ότι το ίδιο σύνολο αγώνων μπορεί να προκύψει αν ξεκινήσουν \(9\) ομάδες και παίξουν δύο γύρους (\(36 + 28 = 64\)).

2o

tvmatch.in tvmatch.out
371 14 6

3o

tvmatch.in tvmatch.out
17 IMPOSSIBLE

Περιορισμοί

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