Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Word2

Задача Word2 

Во время  урока информатики два ученика, не слушая пояснений учителя, играют в такую игру. Каждый из них в своей тетради записывает два выбранных ими вместеслова и пытается за определенное количество ходов из первого слова получить второе. Выигрывает тот, кто сделает минимальное количество ходов.

Ход – это одна из таких операций:
1.заменить какой-то символ из первого слова  каким-то символом второго слова;
2. вычеркнуть какой-либо символ из первого слова;
3. Вставить какой-нибудь символ из второго слова после либо перед каким-нибудь символом первого слова.  Например, для преобразования слова “limuzin” в слово “buzina” необходимо выполнить такие действия: 

Преобразование

Номер операции

limuzin
imuzin
ibuzin
ibuzina 

Þ
Þ
Þ
Þ

imuzin
ibuzin
ibuzina
buzina

2
1
3
2

 Попробуйте написать программу, которая находит  минимальное количество  ходов для преобразования одного заданного слова в другое. 
Технические условия. Программа читает с клавиатуры две строчки длиной не более 104 символов каждая и выводит на экран единственное число – минимальное количество ходов.
 

Пример

Ввод

Вывод

  

limuzin
buzina

4 

  

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"