Ο επεξεργαστής κειμένου eVIgma

Για να μην γράφουμε μόνο κώδικα για προβλήματα, αποφασίσαμε να γράψουμε έναν πλήρως λειτουργικό επεξεργαστή κειμένου, τον e-VI-gma! Για κάθε feature που υλοποιείτε θα παίρνετε έξτρα βαθμούς, οι οποίοι θα κυμαίνονται ανάλογα με το πόσο αποδοτικά λειτουργεί το feature.

Πρώτο feature: γραφομηχανή

Αρχικά, μπορούμε μόνο να εισάγουμε χαρακτήρες στο τέλος του κειμένου και να διαγράφουμε τον τελευταίο χαρακτήρα. Επειδή όμως δεν έχουμε πλήρη εικόνα του κειμένου που γράφουμε, μπορούμε να ζητήσουμε να εκτυπώσουμε τον ~i~-οστό χαρακτήρα του κειμένου.

Δεύτερο feature: αντίγραφα ασφαλείας

Πλέον, πέρα από εισαγωγές και διαγραφές μπορούμε να δημιουργούμε αντίγραφα της δουλειάς μας. Τα αντίγραφα είναι μεταβλητά· δλδ. κάθε εισαγωγή / διαγραφή μπορεί να γίνει στο τέλος κάθε αντιγράφου του κειμένου που έχουμε.

Τρίτο feature: επιτέλους έχουμε βελάκια!

Η γραφομηχανή εκσυγχρονίστηκε και μας επιτρέπει να κινούμαστε στο αρχείο για να κάνουμε εισαγωγές και διαγραφές παντού! Δυστυχώς το σύστημα αντιγράφων έπαψε να λειτουργεί, οπότε όσο προσπαθούμε να το επισκευάσουμε, αρκεί να προγραμματίσουμε εισαγωγές και διαγραφές σε οποιοδήποτε σημείο του αρχείου

Τέταρτο feature: φτιάξαμε τα αντίγραφα!

Φτιάξαμε τα πάντα! Μπορούμε να γράψουμε και διαγράψουμε σε οποιοδήποτε σημείο οποιουδήποτε αντιγράφου του αρχείου.

Μορφή εισόδου (STDIN)

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

1. INSERT i s: εισάγει την συμβολοσειρά s στην θέση ~i~ του τρέχοντος αντιγράφου (αρχικά βρισκόμαστε στο αντίγραφο υπ' αριθμόν 1) (π.χ. για τα πρώτα 2 fetures, το ~i~ θα ισούται πάντα με ~L + 1~, όπου ~L~ το τρέχον μέγεθος του αντγράφου).
2. ERASE i k: διαγράφει ~k~ χαρακτήρες από την θέση ~i~ του τρέχοντος αντιγράφου
3. GET i v: εκτυπώνει τον ~i~-οστό χαρακτήρα (αρίθμηση από 1) του αντιγράφου υπ' αριθμόν ~v~
4. SNAP: δημιουργεί ένα νέο αντίγραφο του τρέχοντος, με αριθμό \(\hbox{|current versions|} + 1\)
5. VERSION v: ορίζουμε το αντίγραφο υπ' αριθμόν ~v~ ως τρέχον.

Μορφή εξόδου (STDOUT)

Στην έξοδο να εκτυπώσετε μία γραμμή με χαρακτήρες: για κάθε ερώτημα τύπου GET τον χαρακτήρα που αντιστοιχεί

Περιορισμοί

• Για ~30\%~ των αρχείων ελέγχου, ~Q \le 500~
• Για το υπόλοιπο ~70\%~, ~Q \le 5,000~
• Για ~50\%~ των αρχείων ελέγχου, το μέγιστο μέγεθος συμβολοσειράς θα είναι ~{} \le 5,100~
• Για το υπόλοιπο ~50\%~, ~|S| \le 100,000~

Παράδειγμα

Είσοδος:

5
INSERT 1 abcde
SNAP
ERASE 3 2
GET 3 1
GET 3 2

Έξοδος:

ec