|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
2009. Copy-Paste
|
| View Problem Statistics | Submit | Problem added debug |
|
Девять лет назад на нашей олимпиаде предлагалась следующая задача. У Васи сломалась клавиатура, и теперь он может набирать текст только с помощью мышки. За одно действие он может скопировать одну букву из таблицы символов или какой-то фрагмент уже набранного текста, а затем добавить этот кусок в набираемый текст. Если Вася будет вставлять в произвольное место, он может запутаться, поэтому вставляет только в конец уже имеющегося текста. Напишите программу, которая даст Васе точную инструкцию, каким образом за наименьшее число действий копирования-вставки получить заданный текст. В 2010 году участникам предлагалось решить эту задачу для входной строки длиной до 104 символов. Но время идёт, Васе приходится набирать всё более длинные тексты, а клавиатура у него всё ещё сломана... Попробуйте теперь решить эту задачу с длиной строки до 106. Входные данные В единственной строке входных данных содержится текст, который нужно набрать Васе. Текст состоит из N строчных букв английского алфавита (1 ≤ N ≤ 106). Выходные данные Выведите в первой строке выходных данных одно число K – количество действий, которые предстоит сделать Васе. Каждая из следующих K строк должна содержать или слово 'letter' строчными буквами без кавычек, или слово 'copy', затем пробел, затем позицию первого символа копируемого фрагмента (от 1 до L включительно, где L – длина уже введённого текста), затем пробел, затем позицию символа после копируемого фрагмента (от 2 до L + 1 включительно). При наличии нескольких верных ответов выведите любой. Пример Входные данные abab Выходные данные 3 letter letter copy 1 3 |
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Vologda Students Contests / | XXII Interuni Olympiad - 2019 / |
| 2008. I - Saddle Point | 2009. |
| time generating 0.093 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |