32ος ΠΔΠ Γ' Φάση
Push-Complement-Reverse (pcr)

Μας δίνεται μία ακολουθία αποτελούμενη από \(N\) αριθμούς \(x_1, x_2, \ldots, x_N\) που καθένας ανήκει στο σύνολο \(\{0, 1, 2, 3\}\). Παίζουμε το εξής παιχνίδι για έναν παίκτη και δύο φύλλα χαρτί (το αριστερό και το δεξιό):

1. Ξεκινάμε γράφοντας την ακολουθία των αριθμών στο αριστερό χαρτί. Το δεξιό χαρτί είναι κενό.
2. Επιλέγουμε μία από τις ακόλουθες τρεις κινήσεις:
   • ‘p’ (push): σβήνουμε τον πρώτο αριθμό της ακολουθίας του αριστερού χαρτιού και τον γράφουμε τελευταίο στο δεξιό χαρτί.
   • ‘c’ (complement): αντικαθιστούμε όλους τους αριθμούς του αριστερού χαρτιού με τους συμπληρωματικούς τους ως προς \(3\). Δηλαδή, ο αριθμος \(x\) αντικαθίσταται από \(3−x\).
   • ‘r’ (reverse): αντιστρέφουμε τη σειρά των αριθμών του δεξιού χαρτιού. Δηλαδή ο πρώτος γίνεται τελευταίος, κ.ο.κ.
3. Το παιχνίδι τελειώνει όταν διαγραφούν όλοι οι αριθμοί από το αριστερό χαρτί.
4. Ο παίκτης κερδίζει αν στην ακολουθία αριθμών του δεξιού χαρτιού στο τέλος του παιχνιδιού όλα τα \(0\) βρίσκονται σε γειτονικές θέσεις, όλα τα \(1\) σε γειτονικές θέσεις, κ.ο.κ.

Ο σκοπός μας είναι φυσικά να βρούμε μία ακολουθία κινήσεων με την οποία ο παίκτης να κερδίζει. Όμως:

• Αν αυτό μπορούμε να το καταφέρουμε με περισσότερους του ενός τρόπους, θέλουμε να κάνουμε τις λιγότερες δυνατές κινήσεις.
• Τέλος, αν και αυτό μπορούμε να το καταφέρουμε με περισσότερους του ενός τρόπους, επιλέγουμε τη λεξικογραφικά μικρότερη ακολουθία κινήσεων.

Ονομάζουμε «βέλτιστη» την ακολουθία κινήσεων που κερδίζει το παιχνίδι και ικανοποιεί τα παραπάνω κριτήρια.

Για παράδειγμα, ας ξεκινήσουμε με αρχική ακολουθία \(2, 3, 2, 1, 0\). Ας υποθέσουμε ότι ο παίκτης επιλέγει να παίζει συνέχεια την κίνηση ‘p’. Τότε, στο τέλος του παιχνιδιού, η ακολουθία στο δεξιό χαρτί θα είναι φυσικά και πάλι η \(2, 3, 2, 1, 0\). Επομένως, ο παίκτης δεν κερδίζει, καθώς το ζεύγος των αριθμών \(2\) δε βρίσκονται σε γειτονικές θέσεις (παρεμβάλλεται ένα \(3\)). Αντίθετα, αν ο παίκτης επιλέξει να παίξει τις παρακάτω κινήσεις:

Κίνηση	Αριστερό χαρτί	Δεξιό χαρτί
	2, 3, 2, 1, 0
p	3, 2, 1, 0	2
p	2, 1, 0	2, 3
r	2, 1, 0	3, 2
p	1, 0	3, 2, 2
c	2, 3	3, 2, 2
p	3	3, 2, 2, 2
r	3	2, 2, 2, 3
p		2, 2, 2, 3, 3

τότε στο τέλος του παιχνιδιού τόσο τα \(2\) όσο και τα \(3\) βρίσκονται σε γειτονικές θέσεις. Επομένως, η ακολουθία αυτή κερδίζει. Όμως δεν είναι βέλτιστη: η ακολουθία κινήσεων ‘pprppp’ κερδίζει επίσης και έχει μικρότερο μήκος.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (Pascal, C, C++, Java) το οποίο θα διαβάζει μερικές αρχικές ακολουθίες αριθμών και για κάθε μία από αυτές θα εκτυπώνει τη βέλτιστη ακολουθία κινήσεων.

Αρχεία εισόδου

Το αρχείο εισόδου με όνομα pcr.in είναι αρχείο κειμένου. Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς \(T\) και \(N\), χωρισμένους με ένα κενό διάστημα. Ο αριθμός \(T\) παριστάνει το πλήθος των ακολουθιών που θα ακολουθήσουν, ενώ ο αριθμός \(N\) παριστάνει το πλήθος των αριθμών κάθε ακολουθίας. Κάθε μία από τις επόμενες \(Τ\) γραμμές περιέχει \(N\) αριθμούς χωρισμένους ανά δύο με ένα κενό διάστημα: τους όρους \(x_1, x_2, \ldots, x_N\) μίας αρχικής ακολουθίας, όπου \(x_i \in \{0, 1, 2, 3\}\).

Αρχεία εξόδου

Το αρχείο εξόδου με όνομα pcr.out είναι αρχείο κειμένου με την εξής δομή. Έχει ακριβώς \(T\) γραμμές που κάθε μία περιέχει τη βέλτιστη ακολουθία κινήσεων για την αντίστοιχη αρχική ακολουθία της εισόδου (βλ. παραπάνω). Οι συμβολοσειρές αυτές θα αποτελούνται από τα γράμματα ‘p’, ‘c’ και ‘r’.

1^o

pcr.in	pcr.out
6 5 1 3 1 0 2 1 1 3 0 2 0 3 3 0 3 2 1 1 3 2 1 0 3 0 1 1 1 3 1 3	pprppp ppppp pcppcpp pcpppp ppcppp pppcpp

Περιορισμοί

• Ισχύει \(1 \le T \le 20, 1 \le N \le 100.000\)
• Ισχύει \(T \cdot N \le 100.000\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(1\le N\le 100\)

Προσοχή! Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

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

• Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: \(2\) sec.
• Μέγιστη διαθέσιμη μνήμη: \(256\) MB.