Дополнительное задание

• Дополнительное задание может поднять оценку на 1 балл, решить надо все задачи
  • «удовл» → «хор»
  • «хор» → «отл», при условии решения 75% Д/З (видимо, не вовремя)

  • не допускается повышение оценки «неуд» → «удовл», но можно решить задания, прийти на экзамен и поднять (или не поднять) её до «хор» устными ответами

• Напоминаю, что «зачёт» — это «хор»

Задания:

1. EJudge: NiceLab 'Красивый лабиринт'

   Написать генератор «достаточно случайного» двумерного лабиринта, в котором стены представлены символом '#', а комнаты/коридоры — '.'. Программа вводит три числа через запятую — ширину и высоту лабиринта (нечётные), а также — должен ли он быть проходим из левого верхнего угла в правый нижний (1 — должен, 0 — нет). Выводится сам лабиринт. Разумеется, не такой, как в примере, тестирующая программа будет проверять следующтие свойства:

   • в проходимом лабиринте не должно быть недоступных комнат,
   • не должно быть сплошных блоков из стен или комнат размером 2×2

   • лабиринт может не иметь циклических/альтернативных путей (в том числе, может никогда их не иметь)

   • для построения непроходимого дабиринта недостаточно заткнуть вход или выход в районе левого верхнего/правого нижнего углов (это можно получиться только случайно)

   • алгоритм не обязан быть «полностью» случайным (в примерах видно, что мой алгоритм любит ходить вдоль стен )

   • (далее см. подсказки)
   Input:

   13,11,1

   Output:

   .#...#.......
   .###.#.#.###.
   ...#...#.#.#.
   ##.#####.#.#.
   .#.....#.#...
   .#####.#.####
   ...#.#.#.....
   .#.#.#.#.###.
   .#...#.#.#...
   .#####.###.#.
   ...........#.

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

3. EJudge: DodgsonDet 'Определитель'

   Ввести квадратную целочисленную матрицу построчно и посчитать её определитель (например, методом конденсации Доджсона). Размер матрицы (1<N<14) определяется длиной её нулевой строки. Описание предлагаемого метода в подсказках. Пользоваться numpy нельзя:)

   Input:

   8, 8, 5, 6, 3
   1, 4, 4, 9, 0
   9, 6, 7, 7, 3
   4, 1, 0, 1, 4
   6, 7, 9, 7, 3

   Output:

   2784