38ος ΠΔΠ B' Φάση
Σύστημα επικοινωνίας (commsystem)
Μετά από αρκετά περιστατικά ασυνεννοησίας με τους σερβιτόρους
του, ο Τάκης εγκατέστησε στην πιτσαρία του ένα νέο ηλεκτρονικό
σύστημα για να μπορούν να μεταφέρουν παραγγελίες από τον χώρο
εξυπηρέτησης στην κουζίνα. Το σύστημα επιτρέπει στους σερβιτόρους
να στέλνουν στον Τάκη τις παραγγελίες κωδικοποιημένες με τη μορφή
δυαδικών συμβολοσειρών, δηλαδή συμβολοσειρών που αποτελούνται
από 0 και 1 (π.χ. “000110”).
Έστω μία ακολουθία \(p_1, p_2, \ldots, p_Ν\) αποτελούμενη από \(Ν\) θετικούς ακέραιους αριθμούς. Θα λέμε ότι η ακολουθία \(p\) είναι πυραμίδα, αν υπάρχει θέση \(k\) (με \(1 \leq k \leq N\)) τέτοια ώστε:
- \(p_i < p_{i+1}\), για κάθε \(i\) με \(1 \leq i < k\),
- \(p_i > p_{i+1}\), για κάθε \(i\) με \(k \leq i < N\).
Με κάποιον περίεργο τρόπο (που δε μας απασχολεί), κάθε παραγγελία στην πιτσαρία αναπαρίσταται ως μία πυραμίδα. Δουλειά σας είναι να δημιουργήσετε ένα πρωτόκολλο επικοινωνίας μεταξύ των σερβιτόρων και του Τάκη.
Το πρόβλημα αυτό είναι “επικοινωνιακό” (communication). Αυτό σημαίνει ότι ο κώδικάς σας θα εκτελείται δύο φορές για κάθε περίπτωση ελέγχου:
- την πρώτη φορά (ως σερβιτόροι) με δεδομένα εισόδου τις παραγγελίες, για να τις “κωδικοποιήσετε” σε μορφή δυαδικών συμβολοσειρών που μπορούν να σταλούν μέσω του συστήματος,
- τη δεύτερη φορά (ως Τάκης) με δεδομένα εισόδου τις κωδικοποιημένες δυαδικές συμβολοσειρές από την πρώτη εκτέλεση, για να τις “αποκωδικοποιήσετε” και να επαναφέρετε τις παραγγελίες ως πυραμίδες.
Ο κώδικάς σας θεωρείται σωστός για μια παραγγελία όταν η πυραμίδα που εκτυπώνει κατά τη δεύτερη εκτέλεση είναι ίδια με αυτή που έλαβε ως είσοδο κατά την πρώτη εκτέλεση, και θεωρείται σωστός σε μία περίπτωση ελέγχου αν είναι σωστός για όλες τις παραγγελίες που αυτή περιέχει. Διαβάστε παρακάτω προσεκτικά τον τρόπο που λειτουργεί η είσοδος και η έξοδος, καθώς και τον τρόπο αξιολόγησης (εξαρτάται από το πόσο μεγάλες είναι οι δυαδικές συμβολοσειρές που στέλνετε μέσω του συστήματος).
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(M\) που είναι είτε ίσος με \(1\), είτε ίσος με \(2\). Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό \(T\): το πλήθος από παραγγελίες.
Αν \(M=1\), έχετε τον ρόλο των σερβιτόρων. Ακολουθούν \(T\) παραγγελίες, καθεμία από τις οποίες αποτελείται από δύο γραμμές. Η πρώτη γραμμή της παραγγελίας περιέχει έναν ακέραιο αριθμό \(N\): το μέγεθος της αντίστοιχης πυραμίδας. Η δεύτερη γραμμή της παραγγελίας περιέχει \(N\) ακέραιους αριθμούς \(p_1, p_2, \ldots , p_N\): τα στοιχεία της πυραμίδας.
Αν \(M=2\), έχετε τον ρόλο του Τάκη. Ακολουθούν \(T\) μηνύματα, το καθένα από τα οποία αποτελείται από μία γραμμή που περιέχει μία δυαδική συμβολοσειρά. Είναι εγγυημένο ότι οι δυαδικές συμβολοσειρές έχουν προκύψει από την εκτέλεση του προγράμματος σας σε κάποιες παραγγελίες με \(M=1\).
Δεδομένα εξόδου (stdout)
Αν \(M=1\), η έξοδος πρέπει να περιέχει \(T\) γραμμές. Για κάθε παραγγελία, η γραμμή που της αντιστοιχεί πρέπει να περιέχει μία μη κενή δυαδική συμβολοσειρά, η οποία κωδικοποιεί την αντίστοιχη πυραμίδα της εισόδου.
Αν \(M=2\), πρέπει να περιέχει \(2T\) γραμμές. Σε κάθε παραγγελία πρέπει να αντιστοιχούν δύο γραμμές: η πρώτη γραμμή πρέπει να περιέχει έναν ακέραιο αριθμό, το μέγεθος \(N\) της πυραμίδας που συμβολίζει η δυαδική συμβολοσειρά, και η δεύτερη γραμμή πρέπει να περιέχει \(N\) ακέραιους αριθμούς, τα στοιχεία της πυραμίδας.
Παράδειγμα εισόδου-εξόδου
1η εκτέλεση:
| stdin | stdout |
|---|---|
| 1 2 5 1 4 8 11 3 3 1 2 3 |
0011010 111 |
2η εκτέλεση:
| stdin | stdout |
|---|---|
| 2 2 0011010 111 |
5 1 4 8 11 3 3 1 2 3 |
Εξήγηση παραδείγματος: Κατά την πρώτη του εκτέλεση, το πρόγραμμά μας επιλέγει να
κωδικοποιήσει την πυραμίδα \([1, 4, 8, 11, 3]\) ως τη δυαδική συμβολοσειρά
“0011010” και την \([1, 2, 3]\) με την “111”. Σημείωση: H εν λόγω
κωδικοποίηση είναι αυθαίρετη, το πρόγραμμά σας μπορεί να επιλέξει όποια
μορφή κωδικοποίησης θέλει.
Κατά τη δεύτερη εκτέλεση του, το πρόγραμμά μας λαμβάνει ως είσοδο τις δυαδικές συμβολοσειρές που προέκυψαν από την πρώτη εκτέλεση, και καταφέρνει να τις αποκωδικοποιήσει και να επαναφέρει τις αρχικές παραγγελίες που έλαβαν οι σερβιτόροι. Έτσι, το πρόγραμμά μας θεωρείται σωστό για αυτήν την περίπτωση ελέγχου.
Περιορισμοί
- \(1 \leq T \leq 100.000\).
- \(N \geq 1\).
- \(1 \leq p_i \leq 12\).
- Κάθε παραγγελία που δίνεται είναι πυραμίδα.
Υποπροβλήματα
Έστω \(L_{\max}\) το μέγιστο μήκος δυαδικής συμβολοσειράς που στέλνει το πρόγραμμά σας, κατά την πρώτη του εκτέλεση, μεταξύ όλων των παραγγελιών όλων των περιπτώσεων ελέγχου του εκάστοτε υποπροβλήματος.
- (21 βαθμοί) Πρέπει \(L_{\max} \leq 92\).
- (23 βαθμοί) Είτε \(p_1 > p_2\), είτε \(p_{N-1} < p_N\), και πρέπει \(L_{\max} \leq 22\).
- (27 βαθμοί) Πρέπει \(L_{\max} \leq 28\).
- (29 βαθμοί) Πρέπει \(L_{\max} \leq 22\).
Παρατηρήσεις
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(16\) MB.