                     Решения задач
                     -------------
5.2.12. Задача c (10 баллов) Кукарачья геометрия.
Средний бал решений: 5.6 (57%)

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

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



    Решение.

   Для решения  задачи можно завести две рекурсивные "пружины".
   Одну для установки  кубика  "c", вторую для установки самого
исполнителя в последнюю вершину прямоугольника.
   Первая "пружина"  должна  состоять  из отложенных выполнений
команды ВНИЗ в  количестве, равном двойной длине отрезка ab.
   Вторая "пружина" должна содержать отложенные выполнения  ко-
манды ВЛЕВО по числу, равному длине отрезка ab.

   Описания алгоритма.
   1) Сначала заводим "пружину" с номером 2, рекурсивно переме-
щая исполнитель вправо  по строке до кубика "b" (отложенная ко-
манда ВЛЕВО).
   2) Перемещаем исполнитель  в исходное положение у кубика "a"
(справа  от  него). При этом энергия "пружины" не  расходуется:
перемещение выполняется циклом ПОКА.
   3) Заводим "пружину" с номером 1, снова рекурсивно перемещая
исполнитель вправо по строке до кубика  "b" (отложенная команда
ПОВТОРИ 2 ВНИЗ).
   4) Работа пружин: пружина 1 устанавливает кубик "c", пружина
2 - исполнитель.


ЭТО Прямоугольник                    │
 Завод_пружины_2                     │
 ВЛЕВО ВНИЗ    <─────────────────────┼ Коррекция положения исполнителя
КОНЕЦ                                │
                                     │
ЭТО Завод_пружины_2     <───────┐    │ Исполнитель шагает к "b", заводя
 ВПРАВО                         │    │ вторую рекурсивную пружину.
 ЕСЛИ b                         │    │
  ТО                            │    │
  {                             │    │ Ура, нашли "b"! Теперь нужно:
    Установка_b2                │    │ Вернуть "b" на место.
    Возврат_к_a                 │    │ Вернуться в исходное положение за "a".
    Завод_пружины_1             │    │ Завести "пружину" 1.
  }                             │    │
  ИНАЧЕ Завод_пружины_2  ───────┘    │
 ВЛЕВО      <────────────────────────┼ Отложенная команда для перемещения
КОНЕЦ                                │ исполнителя по горизонтали к четвертой
                                     │ вершине прямоугольника (той самой
                                     │ вершине, которую он сам изображает).
                                     │
ЭТО Установка_b2                     │ Возвращаем "b" на прежнее место после
 ВНИЗ                                │ завода пружины 2, а исполнителя
 ПОВТОРИ 2 ВПРАВО                    │ помещаем перед "b" для дальнейшего
 ВВЕРХ                               │ путешествия к "a".
 ВЛЕВО                               │
 ВНИЗ                                │
 ПОВТОРИ 2 ВЛЕВО                     │
 ВВЕРХ                               │
КОНЕЦ                                │
                                     │
ЭТО Возврат_к_a                      │ Возвращаемся в исходное
 // Возвращаемся к a                 │ положение за кубиком "a".
 ПОКА НЕ a ВЛЕВО                     │
 // Возвращаем a на место            │ Нашли (толкнули) "a"!
 ВНИЗ                                │ Вернем "a" на место, а исполнитель
 ПОВТОРИ 2 ВЛЕВО                     │ установим следом за этим кубиком.
 ВВЕРХ                               │
 ВПРАВО                              │
 // Кукарачу на исходную!            │
 ВНИЗ                                │
 ПОВТОРИ 2 ВПРАВО                    │
 ВВЕРХ                               │
КОНЕЦ                                │
                                     │
ЭТО Завод_пружины_1     <───────────┐│
 ВПРАВО                             ││
 ЕСЛИ b ТО Установка_b1             ││
 ИНАЧЕ Завод_пружины_1   ───────────┘│
 ПОВТОРИ 2 ВНИЗ  <───────────────────┼ Отложенные команды для транспортировки
КОНЕЦ                                │ кубика "c" вниз в вершину прямоугольника.
                                     │
ЭТО Установка_b1                     │ Возвращаем "b" на место после
 ВНИЗ                                │ завода пружины 1 и помещаем исполнитель
 ПОВТОРИ 2 ВПРАВО                    │ в удобное место для начала работы
 ВВЕРХ                               │ "пружины" 1.
 ВЛЕВО                               │
 ВНИЗ                                │
 ВЛЕВО                               │
КОНЕЦ                                │


   Только два решения, присланные на конкурс, работают правиль-
но. Это программы команд 24 и 30.

--------------------------------------------------------------

Команда: 24
Авторы: Пинженин Павел, 9-й класс
Оценка: 10

Авторское описание алгоритма.
Шаг 1.
   Исполнитель делает шаг  вправо,  пока не встретит букву "b".
Далее возвращает смещенную букву  на  место и смещает букву "с"
вниз на  удвоенное  число шагов, пройденных вправо (рекурсивная
процедура).
Шаг 2.
   Исполнитель возвращается вверх и устанавливается под  буквой
"b".
Шаг 3.
   Исполнитель делает двойной шаг вниз, пока не встретит букву.
Далее возвращает смещенную  букву на место и смещается влево на
число шагов, пройденных вниз (рекурсивная процедура).

 Комментарий куратора.

   Новый набор "пружинок"!
   Павел пружину ab расходуют на смещение "c" вниз на 2Pab.
   Вторая пружина - cb. Такой пружины еще не  было. Она переме-
щает исполнитель в четвертую вершину прямоугольника.
   Наблюдая за тем,  как исполнитель ищет в рекурсии кубик "b",
поднимаясь зигзагами  от "c"  к "b", я ахнул: для  Pab = 2 этот
алгоритм  работать  не будет! Но напрасно я волновался:  хитрый
Павел обработал этот случай отдельно. Молодец!

ЭТО Конкурс_9с
 ВПРАВО
 ЕСЛИ НЕ ПУСТО
  ТО Финиш
  ИНАЧЕ
  {
    Поиск
    ВНИЗ ВНИЗ
    Возврат
    В_угол
    ВВЕРХ
  }
КОНЕЦ                                  

ЭТО Финиш
  // Найдена буква b, Pab=2
  // На место ставим b
  ВНИЗ ВПРАВО
  ВПРАВО ВВЕРХ ВЛЕВО
  // На место ставим с
  ВНИЗ ВЛЕВО ВНИЗ ВНИЗ
  // На место Кукарачу
  ВЛЕВО ВЛЕВО ВНИЗ
КОНЕЦ                                  

ЭТО Поиск
  // Рекурсивная процедура.
  // Ищем точку b, сдвигаем исполнителя
  // вниз на отрезок 2ab.
  ВПРАВО
  ЕСЛИ ПУСТО ТО Поиск
  ИНАЧЕ         Вернуть
  ВНИЗ ВНИЗ
КОНЕЦ

ЭТО Вернуть
  // Возвращение на место точки b
  ВНИЗ ВПРАВО ВПРАВО ВВЕРХ
  ВЛЕВО  ВНИЗ ВЛЕВО
КОНЕЦ

ЭТО Возврат
  // с поставлена на место, исполнитель
  // возвращается под букву b.
  ВПРАВО ВВЕРХ ВЛЕВО
  ПОКА ПУСТО { ВПРАВО ВВЕРХ ВЛЕВО }
  ВНИЗ ВЛЕВО ВЛЕВО ВВЕРХ ВПРАВО
  ВНИЗ ВПРАВО
КОНЕЦ                                  

ЭТО В_угол
 // Рекурсивная процедура, находит с,
 // ставит исполнитель в требуемую
 // клетку
 ВНИЗ ВНИЗ
 ЕСЛИ ПУСТО ТО В_угол
 ИНАЧЕ         На_место
 ВЛЕВО
КОНЕЦ

ЭТО На_место
  //Возвращает с после сдвига на место.
  ВПРАВО ВНИЗ ВНИЗ ВЛЕВО ВВЕРХ ВВЕРХ
КОНЕЦ                                  

--------------------------------------------------------------
Команда: 30
Авторы: Саша Усик, Саша Отенко
Оценка: 9

Авторское описание алгоритма.
   Смещаем по  диагонали, как и в предыдущей задаче. На входе в
рекурсию нужно добавить  процедуру  смещения `c' на две позиции
вниз. Эта процедура должна найти `b', сместиться на этой колон-
ке вниз до буквы `c', сместить ее на две позиции, и вернуться в
исходную точку: все это проще всего реализуется рекурсией.

   Комментарий куратора.
   Особенность программы:  на  каждом  шаге рекурсивного поиска
"b" (процедура "вправо") запускается  дополнительная  (опять же
рекурсивная процедура) "найти_b", которая не просто ищет "b" (с
текущего места) и возвращает исполнителя на опять же на текущее
место, но  и сдвигает "c" на  две позиции вниз.  Таким образом,
когда, выполняя процедуру "вправо",  исполнитель  дойдет, нако-
нец, до  "b", кубик "c"  окажется уже смещенным на нужное число
клеток вниз. Самого исполнителя в четвертую вершину прямоуголь-
ника  перемещает  энергия "пружины",  накопленная  в  процедуре
"вправо".  Эта  "пружина"  перемещает исполнителя по  диагонали
зигзагами ВЛЕВО-ВНИЗ-ВНИЗ.
   Очень красивое  решение! Правда, неоптимальное в смысле "бе-
готни" исполнителя по полю. Число шагов исполнителя сильно рас-
тет при увеличении Pab.
   Примерный расчет.
   В программе куратора число шагов исполнителя оценивается так:
   2Pab   - завод двух "пружин"
   Pab     - возврат к "a"
   Pab + 2Pab - работа двух пружин
   Итак, в этой программе

            число шагов исполнителя = 6Pab+ k

   Здесь k -  постоянное число, независимое от длины отрезка ab
- расход на возвраты кубиков "a"  и "b" на прежние места и кор-
рекция исполнителя.

  В программе команды 30:

  Pab - завод пружины 1 в процедуре "вправо"
  Pab + 2Pab - работа этой пружины
  Шаги в остальных пружинах подсчитываются сложнее.
   При каждом  рекурсивном вызове  процедуры "вправо" заводятся
еще две пружины
  - для поиска "b" и возврата на текущее место;
  - для поиска "c", смещения его вниз на две клетки  и возврата к "b".
   Оценка числа шагов для этих пружин:
       ┌─────────────── от текущего места до "b" и назад
       │           ┌──  от "b" до "c", сдвиг "c" и назад к "b"
       │           │
     2(Pab - 1) + 2(1+2)
     2(Pab - 2) + 2(1+4)
     2(Pab - 3) + 2(1+6)
      ...                            i =  от 1 до  (Pab-1)
     2(Pab - i) + 2(1+2i)
      ...
     2          + 2(1+2(Pab-1))

   Попробуем просуммировать эти шаги.

   S = 2Pab(Pab-1) - 2(1+2+...+(Pab-1)) + 2(Pab-1) + 4(1 + 2 +...+(Pab-1)) =
   = 2Pab(Pab-1) + 2(1+2+...+(Pab-1)) + 2(Pab-1)

   Так как, 1+2+...+(Pab-1) = Pab(Pab-1)/2, то

   S = 2Pab(Pab-1) + Pab(Pab-1)/2 + 2(Pab-1) =

     =  2Pab^2  - 2Pab + Pab(Pab-1)/2  + 2Pab - 2 =

     =  2Pab^2 + Pab(Pab-1)/2- 2 =

     = 3/2 Pab^2 - Pab/2 - 2

   Иными словами, видим,  что  зависимость  шагов исполнителя в
программе куратора линейная, а в программе команды 30 - квадра-
тичная.
   Это означает, например, что при увеличении  Pab  в  10  раз,
число шагов исполнителя  в  программе куратора возрастет тоже в
10 раз, а в программе команды 30 - в 100 раз.

ЭТО программа
  вправо
КОНЕЦ

ЭТО вправо                             
  ВПРАВО
  ЕСЛИ ПУСТО ТО { найти_b              
        вправо                         
  } ИНАЧЕ { вернуть                    
    найти_c                            
  ВЛЕВО ВНИЗ }                         
                                       
                                       
  ВЛЕВО ВНИЗ ВНИЗ
КОНЕЦ

ЭТО найти_b
  ВПРАВО
  ЕСЛИ НЕ ПУСТО ТО { вернуть
    найти_c
    ВЛЕВО ВВЕРХ
  }                                    
  ИНАЧЕ {
    найти_b
  ВЛЕВО }
КОНЕЦ                                  
                                       
ЭТО вернуть
  ВНИЗ ВПРАВО ВПРАВО ВВЕРХ ВЛЕВО ВНИЗ  
ВЛЕВО                                  
                                       
КОНЕЦ                                  
                                       
ЭТО найти_c                            
  ВНИЗ                                 
  ЕСЛИ ПУСТО ТО найти_c                
  ИНАЧЕ { ВНИЗ ВВЕРХ }                 
  ВВЕРХ                                
КОНЕЦ

Апелляционная переписка
-----------------------

                      * * *


 Руководитель команды 30, Саша Отенко, пишет:

>
>    но особенно нас огорчило  замечание  к задаче C, тем более,
> что оно не имеет под собой оснований! ;)
>

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

> ...
>    ... "букву А  трогать  _нельзя_,  букву  Б
> вверх толкать тоже  нельзя".
>

   При таких  ограничениях  кубик  "a"  может  стоять в первом
столбце.

                      * * *

   И снова сообщение от руководителя команды 30, Саши Отенко.

   Саша прислал новую программу, которая не "трогает" букву "a"
и имеет линейную  зависимость  числа шагов исполнителя от длины
отрезка ab.
   Работает она так. Первая пружинка ab заводится, когда испол-
нитель идет от  "a"  к "b". Затем, не  возвращая  "b" на место,
энергия пружины тратится на установку "b".  Теперь заводим пру-
жинку cb,  двигаясь  в поисках "b" зигзагами ВПРАВО-ВВЕРХ-ВЛЕВО
(чтобы не вытолкнуть за поле "b", когда кубик в первой строке).
При обнаружении кубика  "b" он устанавливается на место, в пру-
жина "распрямляется" устанавливая исполнителя в четвертую  вер-
шину.

ЭТО программа
  вправо

  ВПРАВО
  пвл

  топай

  ВЛЕВО
  ВНИЗ
КОНЕЦ

ЭТО вправо
  ВПРАВО
  ЕСЛИ ПУСТО ТО вправо
  ИНАЧЕ ВНИЗ

  ВНИЗ
  ВНИЗ
КОНЕЦ

ЭТО пвл
  ВПРАВО
  ВВЕРХ
  ВЛЕВО
КОНЕЦ

ЭТО топай
  ВВЕРХ
  пвл

  ЕСЛИ ПУСТО ТО топай
  ИНАЧЕ {
    ВНИЗ
    ВЛЕВО
  }

  ВЛЕВО
  ВНИЗ
  ВНИЗ
КОНЕЦ


   Далее Саша предложил модификацию условия задачи "c":

>
>    Кукарача стоит на букве "а" (в  среде  это  можно  сделать),
> буква "с" сразу под  "в".  Зачем такие модификации? Чтобы алго-
> ритм был более универсальным, а именно: доделать, чтобы работал
> и для Pab=1.
>
   Можно еще добавить, что кубик "c" может стоять где угодно на
будущем отрезке bc, в том числе и сразу под буквой "b".

   Новое решение Саши для этой задачи, понятно, является совсем
небольшой (не идейной) модификацией старого:

ЭТО программа
  ВПРАВО
  проверка

  ВПРАВО
  пвл

  топ

  ВЛЕВО
  ВНИЗ
КОНЕЦ

ЭТО проверка
  ЕСЛИ ПУСТО ТО вправо
  ИНАЧЕ ВНИЗ
КОНЕЦ

ЭТО вправо
  ВПРАВО
  проверка

  ВНИЗ
  ВНИЗ
КОНЕЦ

ЭТО пвл
  ВПРАВО
  ВВЕРХ
  ВЛЕВО
КОНЕЦ

ЭТО топ
  ЕСЛИ ПУСТО ТО топай
  ИНАЧЕ {
   ВНИЗ
   ВЛЕВО
  }
КОНЕЦ

ЭТО топай
  ВВЕРХ
  пвл

  топ

  ВЛЕВО
  ВНИЗ
  ВНИЗ
КОНЕЦ

   Таким  образом  задача c стала клонировать. Теперь мы  имеем
три задачи, каждая из которых интересна и поучительна.

   1) Известно, что столбец точки a больше 2
   2) Точка a расположена в строке где угодно
   3) Дополнительно к 2): исполнитель  в  точке a, точка b, где
угодно в строке за точкой a;  точка c где угодно на будущем от-
резке bc.
