Различия между версиями 3 и 4
Версия 3 от 2021-01-09 21:25:58
Размер: 4593
Редактор: FrBrGeorge
Комментарий:
Версия 4 от 2021-01-09 21:29:40
Размер: 3825
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 9: Строка 9:
 Дана строка A, состоящая из строчных латинских букв.
  Над ней можно производить следующие виды операций:
  * Добавить любую букву в любую позицию в строке;
  * Удалить любую из букв строки;
  * Заменить любую из букв строки на любую другую букву.
 Какое количество операций потребуется, чтобы получить из строки A строку B?
  * ввод: строка с двумя словами A и B
  * вывод: минимальное количество операций для преобразования A в B

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

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
    Рассмотрим карту, левый нижний угол которой имеет координаты (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

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

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

LecturesCMC/PythonIntro2020/AdditionalTask (последним исправлял пользователь FrBrGeorge 2021-01-21 13:50:09)