Дополнительное задание для повышения оценки

TODO: Тесты на EJudge ещё не готовы

Правила:

• Для того, чтобы не потерять баллы, надо самостоятельно решить 4 задачи из 6 (первые четыре проще)
• Для того, чтобы набрать +1 балл, надо решить все 6 задач

Задачи

1. EJudge: EditDistance 'Редакторское расстояние'

   Ввести через пробел два слова A и B, состоящие из строчных латинских букв (оба слова не длиннее 1000 символов). Над словом A можно производить следующие виды операций:

   • Добавить любую букву в любую позицию в слове;
   • Удалить любую из букв слова;
   • Заменить любую из букв слова на любую другую букву.

   • Какое количество операций потребуется, чтобы получить из слова A слово B?
   Input:

   qazwsxedcrfvtgbyhn qazxswedcrftgbyhn

   Output:

   3

2. EJudge: LesPole 'Лес и поле'

   Рассмотрим карту, левый нижний угол которой имеет координаты (0; 0), а правый верхний — (1; 1).

   • Область, ограниченная точками (0; 0), (0; Y), (1; Y), (1; 0), занята лесом.
   • Область, ограниченная точками (0; Y), (0; 1), (1; 1), (1; Y), занята полем.
   • Скорость передвижения по лесу равна V1, скорость перемещения по полю равна V2.

   • Определите, в какой точке нужно пересечь границу леса и поля, чтобы как можно быстрее добраться из точки (0; 0) в точку (1; 1)
     • Ввод: 4 числа через пробел: Y, V1, V2, N (количество знаков после запятой, не более 250)
     • Вывод: имеющая N знаков после запятой (все совпадают с цифрами точного решения) X-координата точки (X, Y), при движении через которую время минимально
   Input:

   0.5000 0.3000 0.7000 8

   Output:

   0.19541106

1. EJudge: TuringMachine 'Машина Тьюринга'

   Написать программу, эмулирующую машину Тьюринга. Программа читает со стандартного ввода программу для машины Тьюринга в табличном виде (синтаксис описан тут, с упрощением: полностью «пустых» правил, как в третьем примере, быть не должно), если в очередной строке не содержится пробелов — она последняя, и содержит входное слово. Выводится результат работы МТ (предполагается, что программа применима к этому слову). Если программа не заканчивается после 100000 шагов, эмулятор останавливается без какой-либо диагностики. Пояснение к синтаксису см. в подсказках:

   Input:

         a      b     c      _      #
   0    ,R,    ,R,   ,R,   #,L,1   ,N,
   1    ,L,    ,L,   ,L,    ,R,2   ,L,
   2   _,R,   _,R,3 _,R,4   ,R,!  _,R,!
   3    ,R,    ,R,   ,R,   b,L,1   ,R,
   4    ,R,    ,R,   ,R,   c,L,1   ,R,
   bacab

   Output:

   bcb

2. Многочлен с рациональными коэффициентами

3. EJudge: ArithRebus 'Арифметический ребус'

   Требуется расшифровать запись арифметического равенства, в котором цифры заменены буквами, причем разные цифры заменены разными буквами, одинаковые - одинаковыми. Предполагается, что исходное равенство верно и записано по обычным правилам арифметики. В частности, в записи числа первая слева цифра не является цифрой 0; используется десятичная система счисления. Ввести ребус в формате ЧИСЛО+ЕЩЕ=СУММА, вывести в столбик все решения в строковом лексикографическом порядке.

   Input:

   ЧИСЛО+ЕЩЕ=СУММА

   Output:

   29348+767=30115
   29368+747=30115
   59638+474=60112
   59678+434=60112
   69714+838=70552
   69734+818=70552

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

   • Ввод: строка вида «СЛОВО+ЕЩЁ=СУММА»