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

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

Правила:

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

Задачи

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

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

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

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

   qazwsxedcrfvtgbyhn qazxswedcrftgbyhn

   Output:

   3

   Дана строка A, состоящая из строчных латинских букв.
   • Над ней можно производить следующие виды операций:
   • Добавить любую букву в любую позицию в строке;
   • Удалить любую из букв строки;
   • Заменить любую из букв строки на любую другую букву.
   Какое количество операций потребуется, чтобы получить из строки A строку B?
   • ввод: строка с двумя словами A и B
   • вывод: минимальное количество операций для преобразования A в B

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

   Рассмотрим карту, левый нижний угол которой имеет координаты (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). Точность вычислений — до 4000 знаков после запятой :)

   • Ввод: 4 числа через пробел: Y, V1, V2, количество знаков после запятой
   • Вывод: X-координата точки (X, Y), при движении через которую время минимально

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

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

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

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

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

4. Машина Тьюринга

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

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

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