MalnaRISC

Είναι νωρίς το πρωί και η κροατική ομάδα του IOI αρχίζει να συγκεντρώνεται στο αεροδρόμιο του Ζάγκρεμπ. Το ταξίδι είναι μεγάλo με τελικό προορισμό τη Σιγκαπούρη με στάση στο Άμστερνταμ. Ο κύριος Malar ήπιε την τελευταία σταγόνα από το ρόφημά του με βάση το γκρέιπφρουτ και διέταξε την ομάδα να προχωρήσει προς την πύλη. Όπως συνήθως συμβαίνει, εξαφανίστηκε μετά τον έλεγχο ασφαλείας και με κάποιο τρόπο κατάφερε να εμφανιστεί μόλις λίγα λεπτά πριν την επιβίβαση.
Olympian 1: Πού ήσασταν;! Ορκίζομαι ότι θα χάσετε την επόμενη πτήση αν συνεχίσετε να το κάνετε αυτό.
κ. Malnar: Δεν φταίω εγώ αυτή τη φορά, η ασφάλεια δεν με άφησε να περάσω. Νόμιζαν ότι μπορεί να είμαι ένας τρομοκράτης.
Olympian 2: Ένας τρομοκράτης;! Δεν θα βλάπτατε ούτε μύγα. Τι συνέβη;
κ. Malnar: Α, βρήκαν το MalnaRISC (Υπολογιστής μειωμένου σετ οδηγιών) και αρνήθηκαν να πιστέψουν ότι είμαι σε θέση να φτιάξω τον δικό μου επεξεργαστή. Με άφησαν να φύγω μόλις εξήγησα πόσο αποτελεσματικό είναι στην ταξινόμηση ακεραίων.
Olympian 3: Δεν θα σας πίστευα επίσης. Στην πραγματικότητα, εξακολουθώ να μην το κάνω. Τι κάνει τον επεξεργαστή σας τόσο ενδιαφέρον;
κ. Malnar: Είστε μέλη της εθνικής μας ομάδας IOI, δεν χρειάζεται να σας εξηγήσω τίποτα. Εδώ είναι η τεκμηρίωση, ανακαλύψτε το μόνοι σας.
Olympian 4: Δώστε μου το, θα λύσω το φετινό COI με αυτό χρησιμοποιώντας assembly.
Η γλώσσα assembly για το MalnaRISC περιέχει μία μόνο οδηγία:
  • CMPSWP ~R_i~ ~R_j~ – εναλλάσσει τις τιμές στους καταχωρητές ~R_i~ και ~R_j~ εάν ισχύει ~R_i~ > ~R_j~.
Το ιδιαίτερο με το MalnaRISC είναι ότι όλες οι εντολές που είναι γραμμένες στην ίδια γραμμή θα εκτελούνται παράλληλα κατά τη διάρκεια ενός μόνο νανοδευτερόλεπτου. Φυσικά, κάθε καταχωρητής μπορεί να χρησιμοποιηθεί το πολύ μία φορά ως όρισμα σε μία μόνο γραμμή.
Είναι γνωστό ότι οι καταχωρητές ~R_1,\,R_2, \cdots,\,R_N~ περιέχουν ορισμένους ακέραιους αριθμούς. Γράψτε έναν αποτελεσματικό κώδικα σε assembly που ταξινομεί αυτές τις τιμές σε μη φθίνουσα σειρά.

Είσοδος

Η μόνη γραμμή περιέχει έναν ακέραιο ~N~ από την περιγραφή του προβλήματος.

Έξοδος

Εκτυπώστε έναν ακέραιο ~t~ στην πρώτη γραμμή που υποδηλώνει το χρόνο εκτέλεσης του προγράμματός σας (σε νανοδευτερόλεπτα).
Στις επόμενες ~t~ εκτυπώστε τον κώδικα assembly που ταξινομεί τις τιμές στους ~N~ καταχωρητές. Κάθε γραμμή πρέπει να περιέχει τουλάχιστον μία εντολή και κάθε καταχωρητής πρέπει να αναφέρεται μόνο μία φορά σε μία γραμμή. Καθε η εντολή πρέπει να είναι της μορφής "CMPSWP ~R_i\,R_j~" ~(1 \le i,\,j \le N )~, και οι οδηγίες σε μία μόνο γραμμή πρέπει να διαχωρίζονται από έναν ενιαίο χαρακτήρα διαστήματος.

Βαθμολογία

Υποπροβλήματα	~N~	~t_1~	~t_2~	~t_3~	Βαθμοί
~1~	~8~	~28~	~12~	~6~	~10~
~2~	~13~	~78~	~22~	~10~	~10~
~3~	~16~	~120~	~28~	~10~	~10~
~4~	~32~	~496~	~60~	~15~	~10~
~5~	~53~	~1378~	~102~	~21~	~10~
~6~	~64~	~2016~	~124~	~21~	~10~
~7~	~73~	~2628~	~142~	~28~	~10~
~8~	~82~	~3321~	~160~	~28~	~10~
~9~	~91~	~4095~	~178~	~29~	~10~
~10~	~100~	~4950~	~196~	~30~	~10~

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

$$\displaystyle points(t) = \begin{cases} &0 &t>t_1\\ &1+\frac{2}{t-t_2} &t_1 \ge t >t_2\\ &3 + \frac{7(t_2-t+1)}{t_2-t_3} &t_2 \ge t > t_3\\ &10 &t_3 \ge t \\ \end{cases} $$

Οι πόντοι για κάθε υποπρόβλημα θα στρογγυλοποιούνται σε δύο δεκαδικά ψηφία. Η συνολική βαθμολογία λαμβάνεται από άθροιση αυτών των πόντων και στρογγυλοποίηση αυτού του αθροίσματος με τον ίδιο τρόπο.

Παραδείγματα

input

2

output

1
CMPSWP R1 R2

input

3

output

3
CMPSWP R1 R2
CMPSWP R1 R3
CMPSWP R2 R3

input

4

output

4
CMPSWP R1 R3 
CMPSWP R2 R4
CMPSWP R1 R2 CMPSWP R3 R4
CMPSWP R2 R3