5. Турнир Кукарачи (сетевой Университет 98/99 учебного года)

Пояснительная записка
---------------------
   Задачи пронумерованы цифрами 1-9 и буквами a, b, c, d. Такая
нотация вводится для упрощения автоматической обработки резуль-
татов турнира.
   Дополнительно к условиям задач используйте следующие разъяс-
нения.
   В задаче 3:
   - расположение последнего кубика с символом "!"  в записи за-
ранее не известно;
   - горизонтальный  размер  поля считается  настолько большим,
насколько это необходимо для решения задачи;
   - кубики с символами могут располагаться в любой строке (даже
первой) начиная с любого столбца (даже первого).
   В задачах 4-8:
   - расположение записи в строке совершенно произвольное;
   - не разрешается смещать по горизонтали кубики, составляющие
запись;
   - разрешается смещать  запись  на строку вверх, но структура
ее не  должна меняться: после выполнения программы исполнителем
кубики должны следовать  друг за другом без промежутков в преж-
нем порядке;
   - горизонтальный  размер  поля считается  настолько большим,
насколько это необходимо для решения задачи.

  В задачах 9-c:
   - кубики с символами "a"  и  "b" могут располагаться в любой
строке поля (даже самой первой);
   - кубик с символом "a" может располагаться  в любом столбце,
даже самом первом;
   - после выполнения программы все кубики должны оставаться на
прежних местах (кроме задачи c, где кубик с символом "c" должен
перемещаться вниз по условию задачи);
   - горизонтальный и вертикальный размер  поля  считаются нас-
только большими, насколько это необходимо для решения задачи.

                             ЗАДАЧИ
                             ~~~~~~
                                   ноябрь, 1998 (C) А.А.Дуванов

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


Задача 1 (4 балла)
   Где-то  на  поле,  в  прямоугольнике,  образованном клетками
(1,3), (1,7), (9,3),  (9,7), расположен кубик с непустым симво-
лом.
   Найти этот кубик и переместить его в клетку (1,1). В началь-
ный момент исполнитель расположен в клетке (1,1).

Задача 2 (5 баллов)
   Где-то  на  поле,  в  прямоугольнике,  образованном клетками
(3,3), (3,7), (9,3), (9,7), расположен кубик с ненулевой цифрой.
   Установить этот кубик в первом столбце в клетку, номер стро-
ки которой равен значению цифры на кубике.
   В начальный момент исполнитель расположен в клетке (3,1).

Задача 3 (7 баллов)
   В одной строке  поля расположены кубики с символами так, что
между ними есть пустое пространство -  две  или  больше  пустых
клеток. Известно, что среди кубиков  есть  только  один кубик с
символом "!", и он - самый последний. Написать программу, кото-
рая уплотняет символы - сдвигает их в строке так, чтобы все они
шли подряд без промежутков. В начальный момент исполнитель рас-
положен сразу за первым символом.
   Пример начальной установки среды:
                    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─
                 1 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
                 2 │ │л│¤│ │и│ │ │ │с│ │ │а│ │ │!│
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

   Среда после выполнения программы:
                    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─
                 1 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
                 2 │ │л│и│с│а│!│¤│ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─


Задача 4  (5 баллов)
   В программировании очень часто используют язык  Бэкуса-Наура
для описания определений. Впервые этот язык был использован для
описания языка программирования Алгол-60.
   В языке Бэкуса-Наура используются следующие символы:
   <>    - скобки, выделяющие определяемое понятие;
   ::=   - сложный символ, который читается "по определению есть";
   |     - символ, обозначающий альтернативу, читается "или".
  Введем такое определение числа.
Определение 1
-------------
<число> ::= <цифра> | <число><цифра>    (1)
<цифра> ::= 0 | 1                       (2)

   Прочитать это определение можно так:
   "Число"  по  определению есть: или "цифра", или объект,  про
который мы знаем, что он "число",  вслед  за  которым  записана
"цифра".
   "Цифра" - это либо символ "0", либо символ "1"
   Как видите, первая строка в определении содержит рекурсию!
   Проверим соответствуют ли определению "число" следующие объ-
екты: "1", "01", "12".
   1) Объект "1" - число, потому что:
   1 - цифра (правило 2), а цифра является числом (правило 1).
   2) Объект "01" - число, потому что:
   0 -  это число (так как "0" - это цифра по правилу 2, а зна-
чит, число по правилу 1). Число, за которым  следует цифра, яв-
ляется числом (правило 1), значит, "01" - число.
   3) Объект "12" - не число, потому что за  числом "1" следует
не цифра в смысле правила 2.
   Таким образом, по определению 1 числом  является любая после-
довательность из нулей и единиц.
   Задание. Напишите программу для Кукарачи, которая проверяет,
является ли запись на его поле числом в смысле определения 1.
   В начальный  момент  исполнитель расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая  запись  -  число, установить исполнителя в
конец записи:
                         запись¤
   Если запись  -  не  число,  поставить  исполнителя в десятую
строку поля.

Задача 5  (7 баллов)
   Решить задачу 4,  но если запись не является числом, устано-
вить исполнитель под первым неверным символом  в записи. Напри-
мер:
                         1021
                           ¤
   Если запись - число, установить исполнитель  за последним ее
символом. Например:
                         1011¤

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

 Введем следующее определение числа:
Определение 2
-------------
<число>   ::= <целое> | <дробное>
<целое>   ::= <цифра> | <целое><цифра>
<дробное> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра>   ::= 0 | 1

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

1)   1010¤

2)   121.34
      ¤
3)   .00¤

4)   .10.0
        ¤

Задача 7. (9 баллов)
 Введем следующее определение числа:
Определение 3
-------------
<число>   ::= <целое> | <дробь>
<целое>   ::= <цифра> | <целое><цифра>
<дробь>   ::= <простая> | <десятичная>
<простая> ::= <целое>/<целое>
<десятичная> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра>   ::= 0 | 1

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

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

 Введем следующее определение выражения
Определение 4
-------------
<выражение> ::= <число>+<число> | <число>+<выражение>
<число>   ::= <цифра> | <число><цифра>
<цифра> ::= 0 | 1
   Задание. Напишите программу для Кукарачи, которая проверяет,
является ли запись  на его поле выражением в смысле определения
4.
   В начальный  момент  исполнитель расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - выражение, установить исполнитель в
конец записи:
                         запись¤
   Если запись - не выражение, поставить исполнитель под первым
неверным символом:
                         запись
                           ¤

Задача 9 (5 баллов)
   Кукарачья геометрия.
   Определение 5
   -------------
   Будем рассматривать  каждую  клетку  на поле исполнителя как
геометрическую точку. Координаты точки отсчитываются от  левого
верхнего угла поля и обозначаются как обычные точки на плоскос-
ти парой чисел (x,y). Число x - номер строки, а y - номер стол-
бца, на  пересечении  которых  расположена клетка-точка. Первое
число x будем называть строкой точки, второе y  - столбцом точ-
ки. Точки  будем обозначать малыми латинскими буквами, приписы-
вая к ним, в  случае  необходимости, координаты. Точка o, соот-
ветствующая первой  клетке  в  первой  строке, имеет координаты
(1,1). Таким образом, она обозначается как o(1,1).

   Определение 6
   -------------
   Горизонтальным отрезком на поле Кукарачи назовем упорядочен-
ную пару точек, имеющих одинаковую  строку.  При  этом  столбец
первой точки пары меньше столбца второй.  Отрезок будем обозна-
чать двумя латинскими  буквами  - названиями точек, его образу-
ющих. При  необходимости  в  скобках можно указывать координаты
точек, отделяя их друг от друга запятой.
   Например, горизонтальный  отрезок, образуемый двумя  точками
a(x,y1)  и   b(x,y2),   можно   обозначать   как   ab  или  как
ab((x,y1),(x,y2)).
   Длиной  горизонтального  отрезка  ab((x,y1),(x,y2))  назовем
число y2-y1. Обозначать длины горизонтальных отрезков будем как
Pab или Pab((x,y1),(x,y2)). Таким образом, можно записать:
                 Pab((x,y1),(x,y2)) = y2-y1
   Будем считать, что  точка  t(t1,t2) на поле исполнителя при-
надлежит горизонтальному отрезку ab((x,y1),(x,y2)), если:
                      t1 = x
                      y1 <= t2 <= y2
(через "<=" обозначен знак "меньше или равно")

   Определение 7
   -------------
   Вертикальным отрезком на поле Кукарачи назовем упорядоченную
пару точек, имеющих одинаковый столбец. При  этом строка первой
точки пары меньше строки второй. Отрезок будем обозначать двумя
латинскими буквами - названиями точек, его  образующих. При не-
обходимости в скобках можно указывать координаты точек, отделяя
их друг от друга запятой.
   Например,  вертикальный отрезок,  образуемый  двумя  точками
a(x1,y)  и   b(x2,y),   можно   обозначать   как   ab  или  как
ab((x1,y),(x2,y)).
   Длиной вертикального отрезка ab((x1,y),(x2,y)) назовем число
x2-x1. Обозначать  длины  горизонтальных отрезков будем как Pab
или Pab((x1,y),(x2,y)). Таким образом, можно записать:
                 Pab((x1,y),(x2,y)) = x2-x1
   Будем считать, что  точка  t(t1,t2) на поле исполнителя при-
надлежит вертикальному отрезку ab((x1,y),(x2,y)), если:
                      x1 <= t1 <= x2
                      t2 = y
(через "<=" обозначен знак "меньше или равно")

 Задание.
   Буквы a и  b на поле исполнителя образуют горизонтальный от-
резок ab. В начальный момент Кукарача расположен на этом отрез-
ке сразу за буквой a.
   Написать программу,  которая поставит Кукарачу в нижний пра-
вый угол квадрата, построенного на  отрезке  ab  как на верхней
его стороне.
   Пример. При таком расположении букв a и b на поле:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│¤│ │ │ │b│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 6 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 7 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

   Кукарача должен быть установлен в точку (7,7):
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│ │ │ │ │b│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 6 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 7 │ │ │ │ │ │ │¤│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

Задача a (6 баллов)
   Определение 8
   -------------
  Горизонтальный отрезок,  концевая  точка  которого совпадает с
одной из точек вертикального отрезка, называется перпендикуляром
к вертикальному отрезку.
   Соответственно вертикальный отрезок, концевая точка которого
совпадает с  одной из точек горизонтального отрезка, называется
перпендикуляром к горизонтальному отрезку.
   Перпендикуляр к  отрезку называется срединным, если его кон-
цевая точка совпадает с точкой, расположенной  точно в середине
отрезка. Понятно, что срединный  перпендикуляр  можно построить
только к отрезку с длиной, выражающейся четным числом.
   Задание.
   Буквы a и  b на поле исполнителя образуют горизонтальный от-
резок ab.  Известно,  что  длина  отрезка  ab выражается четным
числом. В начальный момент Кукарача расположен на этом отрезке,
сразу за буквой a.
   Установить исполнитель в точку на срединном  перпендикуляре,
построенного к отрезку  ab  вниз так, чтобы длина вертикального
отрезка, изображающего перпендикуляр,  равнялась половине длины
отрезка ab.

   Пример. При таком расположении букв a и b на поле:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│¤│ │ │ │ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

   Кукарача должен быть установлен в точку (5,5):
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│ │ │ │ │ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │¤│ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼


Задача b (8 баллов)
   Исполнитель расположен где-то внутри горизонтального отрезка
ab. Сместить его  вниз из исходного положения на Pab. Известно,
что столбец точки a больше 2.
   Пример начальной установки среды:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │ │a│ │ │¤│ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

   Среда после выполнения программы:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │ │a│ │ │ │ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 6 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 7 │ │ │ │ │ │¤│ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼


Задача c (10 баллов)
   Буквы a и  b на поле исполнителя образуют горизонтальный от-
резок ab. В начальный момент Кукарача расположен на этом отрез-
ке сразу за буквой a. Буква  c установлена на поле так, что об-
разуется вертикальный отрезок  bc длины 2. Построить на поле из
букв a, b, c и исполнителя прямоугольник abc¤. Длина одной сто-
роны прямоугольника  должна  равняться  длине исходного отрезка
ab, длина другой (сторона bc) - в два раза больше:

                    a────b
                    │    │
                    │    │    Pbc = 2*Pab
                    │    │
                    ¤────c

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