Дополнительное задание для повышения оценки
TODO: Тесты на EJudge ещё не готовы
Правила:
- Для того, чтобы не потерять баллы, надо самостоятельно решить 4 задачи из 6 (первые четыре проще)
- Для того, чтобы набрать +1 балл, надо решить все 6 задач
Задачи
EJudge: EditDistance 'Редакторское расстояние'
Ввести через пробел два слова A и B, состоящие из строчных латинских букв (оба слова не длиннее 1000 символов). Над словом A можно производить следующие виды операций:
- Добавить любую букву в любую позицию в слове;
- Удалить любую из букв слова;
- Заменить любую из букв слова на любую другую букву.
- Какое количество операций потребуется, чтобы получить из слова A слово B?
qazwsxedcrfvtgbyhn qazxswedcrftgbyhn
3
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), при движении через которую время минимально
0.5000 0.3000 0.7000 8
0.19541106
EJudge: TuringMachine 'Машина Тьюринга'
Написать программу, эмулирующую машину Тьюринга. Программа читает со стандартного ввода программу для машины Тьюринга в табличном виде (синтаксис описан тут, с упрощением: полностью «пустых» правил, как в третьем примере, быть не должно), если в очередной строке не содержится пробелов — она последняя, и содержит входное слово. Выводится результат работы МТ (предполагается, что программа применима к этому слову). Если программа не заканчивается после 100000 шагов, эмулятор останавливается без какой-либо диагностики. Пояснение к синтаксису см. в подсказках:
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
bcb
EJudge: ArithRebus 'Арифметический ребус'
Требуется расшифровать запись арифметического равенства, в котором цифры заменены буквами, причем разные цифры заменены разными буквами, одинаковые - одинаковыми. Предполагается, что исходное равенство верно и записано по обычным правилам арифметики. В частности, в записи числа первая слева цифра не является цифрой 0; используется десятичная система счисления. Ввести ребус в формате ЧИСЛО+ЕЩЕ=СУММА, вывести в столбик все решения в строковом лексикографическом порядке.
ЧИСЛО+ЕЩЕ=СУММА
29348+767=30115 29368+747=30115 59638+474=60112 59678+434=60112 69714+838=70552 69734+818=70552
Написать программу, которая умеет решать арифметические ребусы на сложение двух чисел. Примеры арифметических ребусов.
Ввод: строка вида «СЛОВО+ЕЩЁ=СУММА»