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

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

3. EJudge: DeepWood 'Дремучий лес'

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

   • На карте леса все деревья изображаются кругами и задаются координатами центра и радиусом
   • При этом в лесу бывают сросшиеся деревья (изображения таких деревьев на карте пересекаются),
   • Одно дерево может находиться внутри другого.
   • Точка, в которой стоит наблюдатель, не лежит внутри или на границе ни одного из деревьев.

   • Требуется определить, кажется ли лес дремучим данному наблюдателю.
     • Ввод:

       1. строка вида (x0, y0, радиус0), (x1, y1, радиус1), … — карта леса

       2. строка вида x, y — координаты наблюдателя

     • Вывод: YES (дремучий лес) или NO (не дремучий)

   Input:

   (587, 597, 100), (361, 239, 103), (320, 543, 114), (845, 296, 117), (260, 335, 93), (228, 616, 117), (119, 128, 107), (121, 640, 85), (575, 261, 87), (640, 581, 100), (448, 361, 99), (254, 579, 115), (718, 257, 114), (441, 653, 114), (450, 588, 94), (222, 619, 119), (647, 668, 78), (686, 422, 85), (249, 446, 104), (746, 219, 80)
   577, 441

   Output:

   YES

4. 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

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

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

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

   Input:

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

   Output:

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

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

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