5.3. Задачи школьников

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

                         * * *


   Ребята придумали  интересные  задачи.  Некоторые годятся для
хороших упражнений  (например,  05), другие для турнира (напри-
мер, задачи команд 24, 30), третьи содержат новые идеи, которые
можно развивать (например, задача команды 14).

--------------------------------------------------------------
Команда: 05
Авторы: Оборонов Сережа, Лосев Вова
Оценка: 7

   Кукарача в клетке (1,1),  в  клетке (1,2) находится цифра больше
0, она является первым слагаемым в неоконченном примере на сло-
жение с ответом 10, который записан в первой  строке, начиная с
13 столбца.  В четвертой строке, начиная  со 2-го столбца  и по
10-ый, записаны разные цифры от 1 до 9. Надо: в  зависимости от
первого символа, найти  второе слагаемое в 4-ой строке и поста-
вить его на свое место в примере.

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

   Неплохая тренировочная задачка для юных программистов.
   Дополняю описание условия картинкой:
    12345678901234567890
 1  ¤*..........+.=10...    * - любая цифра
 2  ....................
 3  ....................
 4  .#########..........    # - набор перемешанных цифр 1..9

Авторское решение

//-------------------------------------
// Поставить 1-е слагаемое на место и
// проверить его.
// Проверить цифры в 4
// строке, найти второе слагаемое и
// поставить его на место.
//-------------------------------------
ЭТО Пример
 ПОВТОРИ 10 ВПРАВО // 1-е слагаемое
 ЕСЛИ 1 ТО { Подготовка Проверка_9 }   
 ИНАЧЕ ЕСЛИ 2
         ТО { Подготовка Проверка_8 }
 ИНАЧЕ ЕСЛИ 3                          
         ТО { Подготовка Проверка_7 }  
 ИНАЧЕ ЕСЛИ 4                          
         ТО { Подготовка Проверка_6 }  
 ИНАЧЕ ЕСЛИ 5                          
         ТО { Подготовка Проверка_5 }
 ИНАЧЕ ЕСЛИ 6
         ТО { Подготовка Проверка_4 }
 ИНАЧЕ ЕСЛИ 7
         ТО { Подготовка Проверка_3 }  
 ИНАЧЕ ЕСЛИ 8
         ТО { Подготовка Проверка_2 }
 ИНАЧЕ ЕСЛИ 9
         ТО { Подготовка Проверка_1 }  
 Поставить_цифру
КОНЕЦ // Пример
//-------------------------------------
// Поставить исполнитель в клетку 4,14
ЭТО Подготовка
 ВНИЗ                                  
 ПОВТОРИ 3 ВПРАВО
 ПОВТОРИ 2 ВНИЗ
КОНЕЦ // Имя                           
//-------------------------------------
// Найти цифру 9                       
ЭТО Проверка_9                         
  ВНИЗ                                 
  ВЛЕВО
  ВВЕРХ
  ЕСЛИ НЕ 9
     ТО Проверка_9
     ИНАЧЕ Обойти                      
  ВПРАВО
КОНЕЦ // Проверка_9

//-------------------------------------
// Найти цифру 8
ЭТО Проверка_8
  ВНИЗ
  ВЛЕВО
  ВВЕРХ
  ЕСЛИ НЕ 8                            
     ТО Проверка_8
     ИНАЧЕ Обойти
  ВПРАВО                               
КОНЕЦ // Проверка_8                    
                                       
//-------------------------------------
// Найти цифру 7                       
ЭТО Проверка_7
  ВНИЗ
  ВЛЕВО
  ВВЕРХ
  ЕСЛИ НЕ 7                            
     ТО Проверка_7
     ИНАЧЕ Обойти
  ВПРАВО
КОНЕЦ // Проверка_7                    

//-------------------------------------
// Найти цифру 6
ЭТО Проверка_6
  ВНИЗ
  ВЛЕВО                                
  ВВЕРХ
  ЕСЛИ НЕ 6
     ТО Проверка_6                     
     ИНАЧЕ Обойти                      
  ВПРАВО                               
КОНЕЦ // Проверка_6                    
                                       
//-------------------------------------
// Найти цифру 5
ЭТО Проверка_5
  ВНИЗ
  ВЛЕВО                                
  ВВЕРХ
  ЕСЛИ НЕ 5
     ТО Проверка_5
     ИНАЧЕ Обойти                      
  ВПРАВО
КОНЕЦ // Проверка_5

//-------------------------------------
// Найти цифру 4
ЭТО Проверка_4                         
  ВНИЗ
  ВЛЕВО
  ВВЕРХ                                
  ЕСЛИ НЕ 4                            
     ТО Проверка_4                     
     ИНАЧЕ Обойти                      
  ВПРАВО                               
КОНЕЦ // Проверка_4

//-------------------------------------
// Найти цифру 3
ЭТО Проверка_3                         
  ВНИЗ
  ВЛЕВО
  ВВЕРХ
  ЕСЛИ НЕ 3                            
     ТО Проверка_3
     ИНАЧЕ Обойти
  ВПРАВО
КОНЕЦ // Проверка_3

//-------------------------------------
// Найти цифру 2
ЭТО Проверка_2
  ВНИЗ                                 
  ВЛЕВО                                
  ВВЕРХ                                
  ЕСЛИ НЕ 2                            
     ТО Проверка_2                     
     ИНАЧЕ Обойти
  ВПРАВО
КОНЕЦ // Проверка_2

//-------------------------------------
// Найти цифру 1
ЭТО Проверка_1
  ВНИЗ
  ВЛЕВО                                
  ВВЕРХ
  ЕСЛИ НЕ 1
     ТО Проверка_1
     ИНАЧЕ Обойти
  ВПРАВО
КОНЕЦ // Проверка_1                    

//-------------------------------------
// Обойти цифру и поставить ее во 2-ю  
// строку                              
ЭТО Обойти                             
  ВВЕРХ                                
  ВЛЕВО                                
  ВВЕРХ
КОНЕЦ // Обойти
//-------------------------------------
// Толкнуть цифру на место
ЭТО Поставить_цифру                    
 ВНИЗ
 ВПРАВО
 ВВЕРХ
КОНЕЦ // Поставить_цифру               

--------------------------------------------------------------
Команда: 14
Авторы: Лавриков Сергей
Оценка: 6

    Определение 9
   Помимо вертикальных и горизонтальных отрезков в кукарачьей ге-
ометрии есть еще свободные и диагональные отрезки.
   Свободный отрезок - это отрезок, находящийся не на вертикали
и горизонтали.
   Диагональный отрезок - отрезок, координаты точек которого име-
ют одинаковую разность (например:  a(3;2) и b(6;5), у обоих раз-
ность координат равна 1).

    Определение 10
   Треугольник бывает: горизонтально-вертикальный - у него преоб-
ладают горизонтальные и/или вертикальные отрезки; и свободный - у
него все отрезки свободные и/или диагональные.

    Предыстория и задание.
   Кукарача поспорил с Корректором, что сможет с завязанными гла-
зами встать внутрь свободного треугольника, находящегося в  квад-
рате  с координатами (2,2),  (6,2),  (2,6) и (6,6).  Для помощи в
клетках (2,9) и (9,9) находятся восклицательные знаки.
   (Примечание: знаки друг от друга находятся на расстоянии в 2
клетки; вершины не стоят на одной вертикали или горизонтали).

  Примечание, до которого надо догадаться.
   Чтобы была  возможность  решить задачу, надо догадаться, что
наиболее полно входящая клетка, находится на пересечении верти-
кальной линии,  проходящей  через  клетку, которая находится на
срединном столбце ТРЕУГОЛЬНИКА, т.е. если все точки спроектиро-
вать на  прямую, то это  та, что внутри отрезка, и горизонтали,
проходящей через серединную строку треугольника.


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

   Сережа продолжает развивать  кукарачью геометрию.
   А ведь может получится очень интересно, правда?
   Немного улучшим определения.
   Определение 9.  Свободным отрезком называется любая пара то-
чек, не образующая вертикальный или горизонтальный отрезок.
   Определение 9a. Свободный отрезок ab(a(a1,a2),b(b1, b2)) на-
зывается диагональным, если a1-a2 = b1-b2.
   Кукарачинская геометрия ждет своих Лобачевских!
   Может быть, они займутся вычислением площадей геометрических
фигур или построением биссектрис углов.

   А вот условие задачи сформулировано недостаточно четко.
   Где в начальный момент находится Кукарача?
   Что такое срединный столбец треугольника? Всегда ли он быва-
ет в треугольнике?
   Программу, которую  предлагает  Сережа  побивает все рекорды
длины: около 300  строк. Кроме того, как сознается автор, она
до конца не отлажена.
   Однако, идея  красивая  и  может, развиваясь, превратиться в
изящную задачу с коротким решением.

--------------------------------------------------------------
Команда: 20
Авторы: Меденников Антон
Оценка: 6

    Задача. В одной строке справа от  исполнителя находится кубик
с символом. Найти его и установить на первоначальное место испол-
нителя.

   Комментарий куратора.
   Хорошая задача-упражнение по мотивам конкурсных заданий.

ЭТО Поиск
  ВПРАВО                               
  ЕСЛИ ПУСТО                           
    ТО Поиск                           
    ИНАЧЕ На_место                     
// Отложенная команда                  
////////////
  ВЛЕВО   //
////////////
КОНЕЦ // Поиск                         
//-------------------------------------
ЭТО На_место
// Кубик с символом на место           
  ВПЕРЕД                               
  ПОВТОРИ 2 ВПРАВО
  НАЗАД                                
  ВЛЕВО                                
КОНЕЦ // На_место                      


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

Условие задачи.
   Буквы a,b  и с расположены во 2-й строке  так, что длина от-
резка ab больше,  чем  длина отрезка bc. Исполнитель расположен
где-то между символами  a и b. Поставить исполнитель так, чтобы
длина отрезка a¤ стала равна длине  отрезка  bc  (Pa¤=Pbc).  Не
разрешается смещать кубики  по  горизонтали. Кубик с символом а
может располагаться в любом столбце, даже  самом первом. Кубики
можно смещать на строку вверх, сохраняя заданные длины отрезков
ab и bc.

   Комментарий куратора.
   Влияние конкурсных  идей, конечно, есть, но очень интересная
задача! Условию требуется поясняющий рисунок:
 a...¤..b.c........ ──> a.¤....b.c........

   И решение красивое: Павел заставляет исполнитель вычитать от
длины отрезка ac  длину отрезка ab для нахождения нужного поло-
жения Кукарачи в ответе.


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

ЭТО Конкурс_d
  Поиск_a                              
  Поиск_b                              
  ВВЕРХ
КОНЕЦ
//                                     
ЭТО Поиск_a                           │
//Смещение вверх кубиков, стоящих     │ Здесь в рекурсии нет необходимости.
//слева от исполнителя (до буквы a).  │ Вполне можно обойтись циклом ПОКА
  ВНИЗ ВЛЕВО ВВЕРХ                    │
  ПОКА ПУСТО Поиск_a                  │
КОНЕЦ                                 │
//                                    │
ЭТО Поиск_b                            
//Рекурсивная процедура                
//Смещение вверх кубиков, стоящих      
//справа от исполнителя (до буквы b),
//и возврат на требуемую клетку.
  ВНИЗ ВПРАВО ВВЕРХ                    
  ЕСЛИ ПУСТО ТО Поиск_b
  ИНАЧЕ   Ставлю_с                     
  ВЛЕВО                                
КОНЕЦ                                  
//                                    │
ЭТО Ставлю_с                          │
//Смещение вверх кубиков, стоящих     │ Здесь тоже можно обойтись
//справа от буквы b (до буквы с).     │ без рекурсии.
  ВНИЗ ВПРАВО ВВЕРХ                   │
  ПОКА ПУСТО    Ставлю_с              │
КОНЕЦ                                 │

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

Определения и объяснения.
-------------------------

   Для записи чисел используется ограниченный набор цифр. Когда
число невозможно записать одной цифрой, используют старшие раз-
ряды:
8+7=15 <-- пятнадцать нельзя записать одной цифрой: получено
           число, большее, чем 9. Потому в старший разряд
           перенесли число десяток (их нельзя записать цифрой),
           полученных в результате сложения: 1.

   Это десятичная система счисления:  десять  цифр (0, 1, 2, 3,
4, 5, 6, 7, 8, 9). В двоичной же системе счисления используются
только две цифры: 0, 1. Это упрощает алгоритм сложения (не нуж-
но запоминать, сколько будет  2+7,  а сколько будет 3+6): нужно
запомнить только четыре суммы. Но зато  такая система счисления
делает число громоздким  в записи, и потому неудобным в обраще-
нии между людьми.  А вот компьютеру наоборот, с громадинами во-
зиться - просто, зато чем меньше ему объяснять правил, тем луч-
ше (все-таки, не так-то просто объяснить железяке такую простую
вещь, как сложение). Вот эти правила:

0+0 = 0
0+1 = 1   от перемены мест слагаемых сумма не изменяется: 1+0=1 
1+1 = 10  <-- это не "десять". это "один-ноль". В двоичной системе
          нет цифры "2" (мы ее не можем записать одной цифрой,
          потому переносим 1 в  старший разряд)

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

8+7=15 <--- 8 единиц + 7 единиц = 1 десятка + 5 единиц - если их сложить,
                                    получите пятнадцать
здесь использовано только два разряда.

в двоичной выглядит так: 
             первое число: 1            0              0          0
1000+111=1111 <--- 1 восьмерка, ноль четверок, ноль двоек, ноль единиц +
          второе число: 1      1        1
             + 1 четверка, 1 двойка, 1 единица =
             = 1 восьмерка, 1 четверка, 1 двойка, 1 единица - если их все 
сложить - получите пятнадцать.
здесь использовано целых четыре разряда

   Но ведь  когда  складываешь числа десятичные, пока складыва-
ешь, не задумываешься, что это ты складываешь - десятки или ты-
сячи, верно? Так же не нужно задумываться, что  за двойку скла-
дываешь - четверки или восьмерки. Сначала  просто нужно сделать
сложение по правилам, а потом выясним, какой разряд что означа-
ет (если захотим ;)

Задание.
--------
   На поле есть два двоичных числа: из единиц и нолей (ей Богу,
можно было взять и десятичные числа, но там намного больше раз-
ветвлений в условиях было бы! Если Вам кажется проще десятичное
сложение - пожалуйста, можете располагать на  поле два десятич-
ных числа ;).
   Имеется также набор единиц и нолей (а если  Вы выбрали деся-
тичное сложение, то еще и двойки, тройки, ...  девятки. И вооб-
ще, везде, где написано "двоичный" читайте тогда "десятичный").
Составить из этого набора двоичную сумму этих чисел.
   В результате на поле  должно  остаться три числа: два слага-
емых и их сумма. Числа считаются  корректными двоичными числами
(без ошибок; содержат только  1  и 0). Результат 000010 считать
эквивалентным 10, и не требует упрощения.

   Ни в  чем не ограничиваю (а  то получается задача  не "реши-
те-ка вот это",  а "угадай, какой алгоритм я задумал"): размеры
поля и расположение цифр и чисел по Вашему усмотрению, как Вам
удобнее.

Предлагаю, например такое расположение:
 1   2   3   4   5   6   7  ...
===========================
   |   |   |   |   |   |
---+---+---+---+---+---+---
   |   |   |   |   |   |
---+---+---+---+---+---+---
   |   | 1 | 0 | 0 |   |
---+---+---+---+---+---+---
   |   |   |   |   | Ж |
---+---+---+---+---+---+---
   |   |   | 1 | 1 |   |
---+---+---+---+---+---+---
   |   |   |   |   |   |
---+---+---+---+---+---+---
   |   |   |   |   |   |
---+---+---+---+---+---+---
   |   |   |   |   |   |
---+---+---+---+---+---+---
   | 0 | 0 | 0 | 0 |   |
---+---+---+---+---+---+---
   | 1 | 1 | 1 | 1 |   |
===========================

   То есть, одно число в третьей строке, другое - в  пятой. Са-
мое длинное из них (или оба, если длины их равны), начинается с
третьей колонки.  Второе  выровнено  по  правому краю. Кукарача
расположен в четвертой  строке,  на одну колонку правее правого
края чисел.

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

   Комментарий куратора.
   Очень хорошая олимпиадная задача. Это если подработать ввод-
ную определительную часть.

Авторское описание алгоритма
   Ну, что тут писать - тут смотреть надо! Две процедуры рекур-
сии: одна считает,  что перенос из младшего разряда был, другая
- не учитывает. Обе процедуры смещают исполнитель влево, анали-
зируют  кубики  сверху и снизу от него, устанавливают  соответ-
ствующий разряд  числа результата в 0 или в  1, и вызывают либо
процедуру учета переноса, либо сложения  без  учета  его  (если
суммирование битов дало число меньше 10==2). Если сверху и сни-
зу от Кукарачи были пустые кубики, то поле очищается от возмож-
но присутствующего ноля в первой позиции результата (он появля-
ется там, если в результате есть хотя бы одна 1). Все остальные
цифры были удалены  с  поля автоматически из-за особенностей их
геометрического расположения. (во, загнул! ;)

ЭТО программа
  перенос0                             
КОНЕЦ                                  

                                       
ЭТО перенос0                           
  ВЛЕВО                                

  ВВЕРХ
                                       
  ЕСЛИ 0 ТО {                          
    вниз
    ЕСЛИ 0 ТО сделать0                 
    ИНАЧЕ ЕСЛИ ПУСТО ТО сделать0       
    ИНАЧЕ ЕСЛИ 1 ТО сделать1           
                                       
    перенос0                           
  }                                    
                                       
  ИНАЧЕ ЕСЛИ 1 ТО {
    вниз                               
    ЕСЛИ 0 ТО { сделать1               
      перенос0 }                       
    ИНАЧЕ ЕСЛИ 1 ТО { сделать0         
      перенос1 }                       
    ИНАЧЕ ЕСЛИ ПУСТО ТО { сделать1
      перенос0 }                       
  }                                    
                                       
  ИНАЧЕ ЕСЛИ ПУСТО ТО {
     вниз
     ЕСЛИ 0 ТО { сделать0              
      перенос0 }                       
     ИНАЧЕ ЕСЛИ 1 ТО { сделать1
      перенос0 }
     ИНАЧЕ ЕСЛИ ПУСТО ТО { сделать0    
       очистить }                      
  }                                    
КОНЕЦ                                  
                                       
                                       
ЭТО перенос1
  ВЛЕВО ВВЕРХ                          
                                       
  ЕСЛИ 0 ТО {                          
    вниз                               
    ЕСЛИ 0 ТО { сделать1               
      перенос0 }
    ИНАЧЕ ЕСЛИ 1 ТО { сделать0         
      перенос1 }                       
    ИНАЧЕ ЕСЛИ ПУСТО ТО { сделать1     
      перенос0 }
  }
                                       
  ИНАЧЕ ЕСЛИ 1 ТО {                    
    вниз
    ЕСЛИ 0 ТО { сделать0
       перенос1 }                      
    ИНАЧЕ ЕСЛИ 1 ТО { сделать1         
       перенос1 }                      
    ИНАЧЕ ЕСЛИ ПУСТО ТО { сделать0     
       перенос1 }                      
   }                                   

  ИНАЧЕ ЕСЛИ ПУСТО ТО {                
    вниз                               
    ЕСЛИ 0 ТО { сделать1               
       перенос0 }                      
    ИНАЧЕ ЕСЛИ 1 ТО { сделать0         
       перенос1 }
    ИНАЧЕ ЕСЛИ ПУСТО ТО { сделать1     
       очистить }                      
  }                                    
КОНЕЦ

ЭТО вниз                               
  ВНИЗ ВНИЗ ВНИЗ                       
КОНЕЦ

ЭТО сделать0                           
  вниз1                                
  ВНИЗ ВВЕРХ                           
  вернуться                            
КОНЕЦ                                  
                                       
ЭТО сделать1
  вниз1                                
  ВПРАВО ВНИЗ ВЛЕВО ВВЕРХ              
  вернуться                            
КОНЕЦ                                  
                                       

ЭТО вниз1                              
  ВЛЕВО ВНИЗ ВНИЗ ВПРАВО               
КОНЕЦ                                  

ЭТО вернуться
  ВЛЕВО ВВЕРХ ВВЕРХ ВПРАВО ВВЕРХ ВВЕРХ 
КОНЕЦ                                  


ЭТО очистить                           
  ВВЕРХ                                
  вниз                                 
  вниз1                                
  ВНИЗ ВЛЕВО ВПРАВО ВВЕРХ вернуться    
КОНЕЦ                                  
