Московские, осень' 13: Тур 08.11.13

«Curiosity» – это марсоход, который исследует кратер Гейла на Марсе. Недавно он обнаружил воду в марсианской почве, что облегчит высадку людей на Марс.

«Curiosity» поддерживает связь с Землей по каналу со скоростью 32 Kbit/s, но средняя задержка сигнала между Марсом и Землей составляет 14 минут и 6 секунд

“Ты только что увидел камень и нажал на тормоз, но ты знаешь, что марсоход уже проехал через этот камень” - объясняет Мэтт Хеверли, водитель марсохода. “Так что мы сначала планируем маршрут, а потом записываем последовательность простых команд: ехать на метр вперед, повернуть налево, сфотографировать и так далее”.

Иногда важно быстро реагировать на неожиданные события. Например, если камеры обнаружили что-то интересное, то нужно изменить маршрут и сделать дополнительную фотографию. Для этого на марсоход посылается команда вида

s/string/replacement/g

. Она заменяет все вхождения строки

string

на строку

replacement

, начиная с самой левой.

Более формально, если \(A\) - непустая строка и \(B\) - строка, то для применения команды

s/A/B/g

к строке \(S\) Вам надо сделать следующее:

1. Найти самое левое вхождение строки \(A\) в строку \(S\), такое что \(S = S_L + A + S_R\).
2. Если такого вхождения нет, то остановиться. Ответом будет строка \(S\).
3. Пусть \(R\) есть результат применения

   s/A/B/g

   к \(S_R\).
4. Ответом будет строка \(S_L + B + R\).

Это значит, что если есть два перекрывающихся вхождения строки \(A\) в строку \(S\), то только левое будет заменено. Например, применение “

s/aba/c/g

” к строке “abababa” дает “cbc”.

Чем дольше команда, тем больше времени надо на её передачу. Поэтому Вам надо написать программу, находящую кратчайшую команду, превращающую начальную строку в конечную.