Σύστημα επικοινωνίας

Μετά από αρκετά περιστατικά ασυνεννοησίας με τους σερβιτόρους του, ο Τάκης εγκατέστησε στην πιτσαρία του ένα νέο ηλεκτρονικό σύστημα για να μπορούν να μεταφέρουν παραγγελίες από τον χώρο εξυπηρέτησης στην κουζίνα. Το σύστημα επιτρέπει στους σερβιτόρους να στέλνουν στον Τάκη τις παραγγελίες κωδικοποιημένες με τη μορφή δυαδικών συμβολοσειρών, δηλαδή συμβολοσειρών που αποτελούνται από ~0~ και ~1~ (π.χ. "~000110~").

Έστω μία ακολουθία ~p_1~, ~p_2~, ~...~, ~p_N~ αποτελούμενη από ~N~ θετικούς ακέραιους αριθμούς. Θα λέμε ότι η ακολουθία ~p~ είναι πυραμίδα, αν υπάρχει θέση ~k~ (με ~1 \le k \le N~) τέτοια ώστε:

• ~p_i < p_{i+1}~, για κάθε ~i~ με ~1 \le i < k~,
• ~p_i > p_{i+1}~, για κάθε ~i~ με ~k \le i < N~.

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

Το πρόβλημα αυτό είναι "επικοινωνιακό" (communication). Αυτό σημαίνει ότι ο κώδικάς σας θα εκτελείται δύο φορές για κάθε περίπτωση ελέγχου:

• την πρώτη φορά (ως σερβιτόροι) με δεδομένα εισόδου τις παραγγελίες, για να τις "κωδικοποιήσετε" σε μορφή δυαδικών συμβολοσειρών που μπορούν να σταλούν μέσω του συστήματος,
• τη δεύτερη φορά (ως Τάκης) με δεδομένα εισόδου τις κωδικοποιημένες δυαδικές συμβολοσειρές από την πρώτη εκτέλεση, για να τις "αποκωδικοποιήσετε" και να επαναφέρετε τις παραγγελίες ως πυραμίδες.

Ο κώδικάς σας θεωρείται σωστός για μια παραγγελία όταν η πυραμίδα που εκτυπώνει κατά τη δεύτερη εκτέλεση είναι ίδια με αυτή που έλαβε ως είσοδο κατά την πρώτη εκτέλεση, και θεωρείται σωστός σε μία περίπτωση ελέγχου αν είναι σωστός για όλες τις παραγγελίες που αυτή περιέχει. Διαβάστε παρακάτω προσεκτικά τον τρόπο που λειτουργεί η είσοδος και η έξοδος, καθώς και τον τρόπο αξιολόγησης (εξαρτάται από το πόσο μεγάλες είναι οι δυαδικές συμβολοσειρές που στέλνετε μέσω του συστήματος).

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο commsystem.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο commsystem.out.

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

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~M~ που είναι είτε ίσος με ~1~, είτε ίσος με ~2~. Η δεύτερη γραμμή περιέχει έναν ακέραιο αριθμό ~T~: το πλήθος από παραγγελίες.

Αν ~M = 1~, έχετε τον ρόλο των σερβιτόρων. Ακολουθούν ~T~ παραγγελίες, καθεμία από τις οποίες αποτελείται από δύο γραμμές. Η πρώτη γραμμή της παραγγελίας περιέχει έναν ακέραιο αριθμό ~N~: το μέγεθος της αντίστοιχης πυραμίδας. Η δεύτερη γραμμή της παραγγελίας περιέχει ~N~ ακέραιους αριθμούς ~p_1~, ~p_2~, ~...~, ~p_N~: τα στοιχεία της πυραμίδας.

Αν ~M = 2~, έχετε τον ρόλο του Τάκη. Ακολουθούν ~T~ μηνύματα, το καθένα από τα οποία αποτελείται από μία γραμμή που περιέχει μία δυαδική συμβολοσειρά. Είναι εγγυημένο ότι οι δυαδικές συμβολοσειρές έχουν προκύψει από την εκτέλεση του προγράμματος σας σε κάποιες παραγγελίες με ~M = 1~.

Αρχεία εξόδου (commsystem.out)

Αν ~M = 1~, η έξοδος πρέπει να περιέχει ~T~ γραμμές. Για κάθε παραγγελία, η γραμμή που της αντιστοιχεί πρέπει να περιέχει μία μη κενή δυαδική συμβολοσειρά, η οποία κωδικοποιεί την αντίστοιχη πυραμίδα της εισόδου.

Αν ~M = 2~, πρέπει να περιέχει ~2T~ γραμμές. Σε κάθε παραγγελία πρέπει να αντιστοιχούν δύο γραμμές: η πρώτη γραμμή πρέπει να περιέχει έναν ακέραιο αριθμό, το μέγεθος ~N~ της πυραμίδας που συμβολίζει η δυαδική συμβολοσειρά, και η δεύτερη γραμμή πρέπει να περιέχει ~N~ ακέραιους αριθμούς, τα στοιχεία της πυραμίδας.

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

1η εκτέλεση:

Είσοδος:

1
2
5
1 4 8 11 3
3
1 2 3

Έξοδος:

0011010
111

2η εκτέλεση:

Είσοδος:

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 \le T \le 100.000~
• ~N \ge 1~
• ~1 \le p_i \le 12~
• Κάθε παραγγελία που δίνεται είναι πυραμίδα.

Υποπροβλήματα:

Έστω ~L_{max}~​ το μέγιστο μήκος δυαδικής συμβολοσειράς που στέλνει το πρόγραμμά σας, κατά την πρώτη του εκτέλεση, μεταξύ όλων των παραγγελιών όλων των περιπτώσεων ελέγχου του εκάστοτε υποπροβλήματος.

1. (21 βαθμοί) Πρέπει ~L_{max} \le 92~.
2. (23 βαθμοί) Είτε ~p_1 > p_2~, είτε ~p_{N - 1} < p_N~, και πρέπει ~L_{max} \le 22~.
3. (27 βαθμοί) Πρέπει ~L_{max} \le 28~.
4. (29 βαθμοί) Πρέπει ~L_{max} \le 22~.

Παρατηρήσεις:

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~1~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~16~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: commsystem *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: commsystem */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: commsystem */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: commsystem */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.