Роботландский Университет 99/00
Азы программирования
Задачи турнира Кукарачи
--------------------------------

т у р н и р  к у к а р а ч и
- - - - - -  - - - - - - - -

   Задачи пронумерованы цифрами 1-9 и буквами a, b, c, d, e. Та-
кая нотация  вводится для упрощения автоматической обработки ре-
зультатов турнира.

З А Д А Ч И
- - - - - -
декабрь, 1999 (C) А.А.Дуванов

                                     Таил в молчанье он глубоком
                                     Движенья сердца своего,
                                     И на челе его высоком
                                     Не изменялось ничего.
                                                      А.С.Пушкин


   Слова Александра  Сергеевича  --  про  нашего молчуна Кукара-
чу-Залесского. Хотя на самом  деле  Кукарача родился не в Перес-
лавле, а на Дальнем Востоке на пограничной реке Амур. В  том са-
мом месте, где в Амур впадает Зея. И случилось это в 1984 году.
   Сначала Кукарача (тогда его называли просто Таракан) трудился
на ЭВМ "Искра-1256". Трудно теперь представить себе такой персо-
нальный компьютер. Объем  его  оперативной памяти составлял аж 4
Кб! Сколько памяти на вашем компьютере? 8, 16, 32, а  может быть
64 Мб?  Устройством  ввода  служил обычный кассетный магнитофон.
Графики, конечно, не было и в помине. Вот в каких условиях приш-
лось работать  нашему  герою.  Потом были: "Искра-226", "Ямаха",
"УК-НЦ", "PC".


р а з м и н к а
- - - - - - - -

   Разминка включает в себя три очень простых задачи.
   Во всех этих задачах  считается,  что справа поле велико нас-
только, насколько это необходимо для решения.

Задача 1. (5 баллов)

   Текстовая строка  - это последовательность из нескольких сим-
волов. Будем считать концом строки символ пробела. Для обобщения
наших рассмотрений  введем  понятие пустой строки. Пустая строка
-- это пустое место, отсутствие каких-либо символов.
   Операция соединения двух текстовых строк в  одну строку назы-
вается операцией  конкатенации.  Обычно  эта  операция  в языках
программирования обозначается  так  же,  как и операция сложения
знаком "+".

   Примеры выполнения операции конкатенации.
1) каша+лот  = кашалот
   Соединяются две непустые строки.
2) каша++лот = кашалот
   Соединяются две непустые строки и одна пустая -- она распола-
   гается "между" двумя знаками "+".
3) + =
   Соединяются две пустые строки. Результат -- пустая строка.

4) +по+беда+ = победа
   Соединяются 4  строки. Первая и последняя, соединяемые строки
   -- пустые.

   Замечание.  Предполагается,  что  среди символов, входящих  в
состав строк, знака "+" нет.

   Задание.
   На поле исполнителя во второй строке записано выражение, сос-
тоящее из  строк, соединенных между собой операцией конкатенации
"+". Некоторые из строк или даже все, могут быть пустыми. Пустая
строка не занимает  клетку на поле,  а как бы  располагается  на
стыке двух клеток.  Символ  пробела изображается на поле клеткой
без кубиков.
   Произвести указанные операции и получить результат. В началь-
ный момент исполнитель расположен слева от записи.

     Примеры работы программы.

До выполнения                 После работы программы

   1 2 3 4 5 6 7 8 9 0           1 2 3 4 5 6 7 8 9 0
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬       ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │ │     1 │ │л│и│с│и│ц│а│¤│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │¤│л│и│+│с│и│+│ц│а│ │ │     2 │ │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


   1 2 3 4 5 6 7 8 9 0           1 2 3 4 5 6 7 8 9 0
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬       ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │ │     1 │ │к│о│ш│к│а│¤│ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │¤│к│о│+│ш│+│+│к│а│+│ │     2 │ │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

   И так далее.


Задача 2. (5 баллов)

   Введем в символьной строке операцию минус:  "-". Эта операция
будет удалять из строки символ, который  ей предшествует. Напри-
мер,
                     крош-кодил = крокодил

   Замечание 1. Каждый знак "-"  в  строке  рассматривается  как
операция, а не как символ строки.


   Замечание  2.  Знак операции "-" может быть  самым  первым  в
строке (из строки ничего не удаляется) и самым последним (удаля-
ется самый последний символ).

   Замечание 3. Операции "-" не могут следовать в строке подряд,
то есть, записи вида "по--беда" исключаются.

   Задание.
   На поле исполнителя во второй строке записано выражение, сос-
тоящее из символов  строки  со знаками "-". Произвести указанные
операции и  получить  результат.  В начальный момент исполнитель
расположен слева от записи.


Задача 3. (6 баллов)

   Решить задачу  2  при  допущении следования нескольких знаков
операций "-"  подряд.  При  этом операции выполняются последова-
тельно слева направо.
   Например, при выполнении первой операции "-" строка "по--беда"
превратится  в  строку  "п-беда".  Результат выполнения двух
операций -- слово "беда".

   Замечание. 6  баллов за задачу выставляются, если результиру-
ющая запись не уплотняется. Например,

До выполнения                 После работы программы

   1 2 3 4 5 6 7 8 9 0           1 2 3 4 5 6 7 8 9 0
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬       ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │ │     1 │ │л│ │ │ │ │о│с│ь│¤│ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │¤│л│и│с│-│-│о│с│ь│ │ │     2 │ │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Если же программа уплотняет запись:

   1 2 3 4 5 6 7 8 9 0           1 2 3 4 5 6 7 8 9 0
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬       ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │ │     1 │ │л│о│с│ь│¤│ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │¤│л│и│с│-│-│о│с│ь│ │ │     2 │ │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


то балл за задачу повышается до 10.


л е к с и ч е с к и е   а н а л и з а т о р ы
- - - - - - - - - - -   - - - - - - - - - - -

   Для решения  четырех  задач  этой серии, необходимо повторить
язык Бэкуса-Наура.
   Настоятельная рекомендация:  перед записью программного  кода
обязательно нарисуйте диаграмму переходов и эту схему прилагайте
к решению как его составную часть.


Задача 4 (5 баллов)

Определение 1
-------------
<программа> := <команда>|<программа><команда>
<команда>   := <пустая>|<простая>|<условная>
<пустая>    :=
<простая>   := 0|1|2|3|4|5|6|7|8|9
<условная>  := е<условие><команда>
<условие>   := к|м


Замечание.
- - - - -
   Из определения видно, что отсутствие каких-либо символов яв-
ляется корректной (пустой) программой.


Примеры программ

1)
2) 123
3) ек1
4) емек1


Примеры не программ

1) к1
2) е1
3) ее


Смысл, который может иметь программа, заданная определением
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

   Пусть, например, "1", "2", "3", "4"  --  это  команды  ВВЕРХ,
ВНИЗ, ВЛЕВО, ВПРАВО исполнителя на клетчатом  поле. Пусть, усло-
вие "к" истинно, если в клетке растет капуста, а условие "м" ис-
тинно, если в клетке растет морковь.

   Тогда программа  "11ек31"  в  более привычной записи выглядит
так:

ВВЕРХ
ВВЕРХ
ЕСЛИ КАПУСТА ТО ВЛЕВО
ВВЕРХ

   Это означает следующее. Исполнитель перемещается на две клет-
ки вверх, затем проверяет, растет ли в клетке капуста. Если рас-
тет, он перемещается влево, а затем вверх. Если  капуста не рас-
тет, исполнитель поднимается вверх без смещения влево.

Программа "1екем23" переводится так:

ВВЕРХ
ЕСЛИ КАПУСТА ТО
  ЕСЛИ МОРКОВЬ ТО ВНИЗ
ВЛЕВО

   Исполнитель  смещается вверх и проверяет, растет ли в  клетке
капуста и морковь одновременно. Если это так, он смещается вниз.
В любом случае исполнитель затем  перемещается  на  одну  клетку
влево.

   Формально определение допускает программы типа "екекек1", что
в обозначенной выше среде означает то же самое, что "ек1".
   На самом деле, в некоторых средах программы "екекек1" и "ек1"
могут отличаться по смыслу.
   Пусть проверка  меняет  среду.  Например, каждые две проверки
"к",  совершенные над клеткой с капустой, губят ее  (исполнитель
затаптывает капусту ногами), и капуста в клетке погибает.
   Тогда программа "ек1"  смещает  исполнитель вверх из клетки с
капустой (капуста в клетке остается), а  программа "екекек1" ос-
тавляет исполнитель на  месте  и меняет экологию клетки (капуста
гибнет от затаптывания).
   Таким образом, показано, что введенное выше определение прог-
раммы может иметь смысл. Какой? Самый  разный.  Все  зависит  от
среды, в которой предполагается выполнение программы и  алгорит-
мов работы команд исполнителя и проверок.
   Нас сейчас  интересует  чисто  формальная сторона дела. Нужно
написать лексический  анализатор,  при  помощи которого Кукарача
сможет проверить  соответствие  записи  на своем поле введенному
определению 1.

   Задание. Напишите программу для Кукарачи, которая  проверяет,
является ли запись на  его  поле программой в смысле определения
1.
   В начальный  момент  исполнитель  расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - программа, установить исполнитель в
конец записи:
                         запись¤
   Если запись - не программа, поставить  исполнитель под первым
неверным символом:
                         запись
                           ¤


Задача 5 (8 баллов)

Определение 2
-------------
<программа>   := <команда>|<программа><команда>
<команда>     := <простая>|<условная>
<простая>     := 0|1|2|3|4|5|6|7|8|9
<условная>    := <сокращенная>|<полная>
<сокращенная> := е<условие><команда>
<полная>      := <сокращенная>и<команда>
<условие>     := к|м


   Задание. Напишите программу для Кукарачи, которая  проверяет,
является ли запись на  его  поле программой в смысле определения
2.
   В начальный  момент  исполнитель  расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - программа, установить исполнитель в
конец записи:
                         запись¤
   Если запись - не программа, поставить  исполнитель под первым
неверным символом:
                         запись
                           ¤

   Дополнительно к разработке лексического анализатора придумать
среду, исполнитель,  описать алгоритмы работы команд и проверок,
ввести более  содержательные обозначения лексем языка и записать
несколько программ-примеров в формальной нотации определения 2 и
эквивалентных новых обозначениях.


Задача 6 (6 баллов)

Определение 3
-------------
<текст>       := <слово>.|<слово><разделитель><текст>
<разделитель> := _|,
<слово>       := <буква>|<слово><буква>
<буква>       := а|м

   Задание. Напишите программу для Кукарачи, которая  проверяет,
является ли запись на его поле текстом в смысле определения 3.
   В начальный  момент  исполнитель  расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - текст, установить исполнитель в ко-
нец записи:
                         запись¤
   Если запись -  не текст, поставить исполнитель под первым не-
верным символом:
                         запись
                           ¤

Задача 7 (7 баллов)
   Измените  определение  задачи 6 таким образом, чтобы в  новом
определении:

   1) текст всегда  начинался словом, первая буква которого заг-
      лавная, то есть текст обязан начинаться с буквы "М" или "А";
   2) внутри текста заглавных букв быть не должно;
   3) слово не должно состоять из одной буквы.

   Напишите программу для Кукарачи, которая проверяет,  является
ли запись на его поле текстом в смысле нового определения.
   В начальный  момент  исполнитель  расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - текст, установить исполнитель в ко-
нец записи:
                         запись¤
   Если запись -  не текст, поставить исполнитель под первым не-
верным символом:
                         запись
                           ¤


к у к а р а ч ь я   г е о м е т р и я
- - - - - - - - -   - - - - - - - - -

   Расстояние на поле Кукарача измеряет своими шагами. Так, рас-
стояние между двумя соседними клетками по вертикали или по гори-
зонтали равно 1. Ведь Кукараче нужно  сделать  ровно  один  шаг,
чтобы пройти из одной такой клетки-точки в другую. А вот рассто-
яние между двумя  соседними клетками по диагонали равно 2! Такая
странная у исполнителя геометрия.
   Вообще говоря, из одной клетки  в  другую  Кукарача может по-
пасть самым причудливым образом. Когда мы  говорим, что измеряем
расстояние шагами  исполнителя,  то имеем ввиду наименьшее число
шагов из  всех  возможных,  которое  должен сделать исполнитель,
чтобы попасть из одной клетки в другую.


Задача 8 (4 баллов)

   Изобразите  на  поле исполнителя при помощи кубиков с  буквой
"о":

   1) окружность радиуса 1;
   2) круг радиуса 1;
   3) окружность радиуса 2;
   4) круг радиуса 2;
   5) геометрическое место точек, удаленных на 1 от диагональной
      цепочки клеток, протянутой из клетки (1,1);
   6) геометрическое место точек, удаленных на 2 от диагональной
      цепочки клеток, протянутой из клетки (1,1);
   7) равносторонний треугольник со стороной, равной 2;
   8) равносторонний треугольник со стороной, равной 3;
   9) равносторонний треугольник со стороной, равной 4.


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

Задача 9 (8 баллов)

   Кубики a, b и  с  образуют на поле равнобедренный треугольник
(сторона ca вытянута по вертикали). Исполнитель располагается на
перпендикуляре, проведенном из вершины b на сторону ac, сразу за
вершиной b.  Точка a отстоит от точки c  на два кукарачьих шага.
Ниже приводятся примеры возможных начальных установок:

До выполнения программы

  │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │c│ │ │ │ │ │ │   │ │ │c│ │ │ │ │ │   │ │ │ │с│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │b│¤│ │ │ │ │ │ │   │b│¤│ │ │ │ │ │ │   │b│¤│ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │a│ │ │ │ │ │ │   │ │ │a│ │ │ │ │ │   │ │ │ │a│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼

   Задание. Напишите программу, которая разместит точки a и c на
окружности с центром  в середине исходного отрезка ac и радиусом
равным длине перпендикуляра, опущенного из вершины  треугольника
b на сторону  ac.  После выполнения программы исполнитель должен
располагаться в центре окружности:

После выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │   │ │ │ │c│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │   │ │ │c│ │ │ │ │ │   │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │c│ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │b│¤│ │ │ │ │ │ │   │b│ │¤│ │ │ │ │ │   │b│ │ │¤│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │a│ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │   │ │ │a│ │ │ │ │ │   │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │   │ │ │ │c│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼


Задача a (8 баллов)

   Три кубика на поле образуют равнобедренный треугольник с дли-
ной основания, равной двум шагам исполнителя. Основание вытянуто
по вертикали. Сам исполнитель располагается на высоте, проведен-
ной к основанию, сразу за  вершиной, из  которой опущена высота.
Повернуть треугольник на  90 градусов по часовой стрелке и уста-
новить исполнителя так,  чтобы он и три вершины повернутого тре-
угольника образовывали ромб. Смотрите рисунки примеров возможных
состояний среды до и после выполнения программы.


До выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │*│ │ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │   │ │ │ │ │*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │*│¤│ │ │ │ │ │ │   │ │*│¤│ │ │ │ │ │ │   │ │*│¤│ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │*│ │ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │   │ │ │ │ │*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

После выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │*│ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │*│ │*│ │ │ │ │ │   │ │ │*│ │*│ │ │ │ │   │ │ │ │*│ │*│ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │¤│ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │¤│ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │¤│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┤


Задача b (8 баллов)

   Справа от исполнителя находится группа из несколько кубиков.
   Сместить эту  группу  "параллельно"  на  столько  строк вниз,
сколько кубиков в группе.


До выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 1│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 2│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 3│ │¤│*│ │ │ │ │ │ │   │ │¤│*│*│ │ │ │ │ │   │ │¤│*│*│*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 4│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

После выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 1│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 2│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 3│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 4│ │ │*│ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 5│ │ │ │ │ │ │ │ │ │   │ │ │*│*│ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
 6│ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │*│*│*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Задача c (8 баллов)

   Справа от  исполнителя находится группа из несколько кубиков.
Образовать из  кубиков лесенку с  высотой ступеньки в два шага и
шириной --  в один шаг  Кукарачи. Сам исполнитель в конце работы
изображать еще одну, дополнительную ступеньку.
   Смотрите рисунки примеров возможных состояний среды до и пос-
ле выполнения программы.
   Расположение полученной лесенки на поле не имеет значения.

До выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │¤│*│ │ │ │ │ │ │   │ │¤│*│*│ │ │ │ │ │   │ │¤│*│*│*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

После выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │¤│ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │¤│ │ │ │ │   │ │ │ │ │*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │¤│ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │*│ │ │ │ │ │ │   │ │ │*│ │ │ │ │ │ │   │ │ │*│ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Задача d (10 баллов)

   Решить предыдущую  задачу  при  условии,  что  лесенка должна
иметь ступени размером в один шаг исполнителя как по высоте, так
и по ширине.


До выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │¤│*│ │ │ │ │ │ │   │ │¤│*│*│ │ │ │ │ │   │ │¤│*│*│*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

После выполнения программы

  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │¤│ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │¤│ │ │ │ │   │ │ │ │ │*│ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │¤│ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │   │ │ │ │*│ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │*│ │ │ │ │ │ │   │ │ │*│ │ │ │ │ │ │   │ │ │*│ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │   │ │ │ │ │ │ │ │ │ │
  ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼   ┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


   Задача  e  (10 баллов) Придумать свою собственную задачу  для
Кукарачи, написать ее условие и решение. Балл за это задание оп-
ределяется оригинальностью условия и качеством решения.
