3.3. Задачи Олимпиады

   Задачи были  подобраны  довольно разнородными - некоторые из
них очень простые,  и их решили все участники, другие, несмотря
на простую постановку условия и короткое решение, очень сложны,
и решили их только некоторые команды.
   Предполагалось (и в некоторых случаях это действительно име-
ло место), что для решения задач компьютерные реализации испол-
нителей не нужны. Но, конечно, те команды, которые имели в сво-
ем распоряжении компьютерные Плюсики, Буквоеды и Кукарачи, име-
ли более комфортную лабораторию, по сравнению с теми командами,
которые обошлись листком бумаги и шариковой ручкой.
   Мы отдавали себе отчет в том, что в Олимпиаде будут участво-
вать дети разных возрастов и,  в  частности,  этим  объясняется
разный  уровень  сложности  задач. Однако, анализ  фактического
возрастного состава групп показал, что среди участников имеются
коллективы,  в  которых  ребята старшего возраста  отсутствуют.
Чтобы поставить все коллективы в более или менее одинаковые ус-
ловия, мы  приняли решение ввести некоторый (достаточно мягкий)
выравнивающий коэффициент.
   Механизм получения оценки за работу группы с учетом введения
коэффициента приводится ниже.

итоговая оценка = сумма набранных баллов * коэффициент

                            10
коэффициент =  ──────────────────────────────
               средний возраст детей в группе

                                  сумма возрастов в группе
средний возраст детей в группе =  ────────────────────────
                                     число участников

   Из формулы коэффициента  видно, что он равен единице для ко-
манд со средним возрастом детей 10 лет.

   1. (3 балла) Автор  Ю.А.Первин. В последовательности чисел
                   1, 2, 3, 5, 8, 13, 21, ...
какое будет следующим?

   2. (3 балла) Автор  Ю.А.Первин. Даны несколько чисел:
                    23, 13, 17, 15, 31, 47, 5
Какое среди них лишнее?

   3. (3 балла) Автор  Ю.А.Первин.  У Кати Пушковой хороший по-
черк. Поэтому  учительница попросила Катю перед уроком написать
на доске заранее подготовленный список. Катя выполнила задание.
Даже перестаралась. Написала один город лишний:
   Владимир, Суздаль, Ярославль,  Кострома, Иркутск, Сергиев-По-
сад, Переславль-Залесский.
   На какую тему хотела поговорить  учительница  на  уроке?  Что
лишнего написала Катя?

   4. (3 балла)  Автор  Ю.А.Первин. Как надо продолжить цепочку
чисел?
                  1, 2, 4, 5, 7, 8, 10, 11 ...

   5. (3 балла) Автор  Ю.А.Первин. Какая буква продолжает цепочку?
                       Б, В, Г, Д, Ж, З, ...

   6. (3 балла)  Автор  Ю.А.Первин.  Страничка разделена на две
части. Вверху написаны слова
               волк, бегемот, крокодил, лиса, лось
а внизу
              карась, жираф, петух, лошадь, медведь
   В нижнюю часть надо  перенести  одно слово из верхней. Какое
это слово?

   7. (3 балла)  Автор  Ю.А.Первин.  Страничка разделена на две
части. Вверху написаны слова
          домовой, строитель, лесник, засоня, равенство
а внизу
              рассвет, подножка, загон, постройка
   В нижнюю часть надо  перенести  одно слово из верхней. Какое
это слово?

   8. (5 баллов) Отгадайте черный ящик.

                       ┌───────┬────────┐
                       │Вход   │Выход   │
                       ├───────┼────────┤
                       │0      │0       │
                       │1      │1       │
                       │13     │1       │
                       │26     │2       │
                       │260    │2       │
                       │261    │3       │
                       │262    │4       │
                       │202    │4       │
                       │12345  │9       │
                       │22345  │10      │
                       │12040  │1       │
                       └───────┴────────┘

9. (5 баллов) Отгадайте черный ящик.

                       ┌───────┬────────┐
                       │Вход   │Выход   │
                       ├───────┼────────┤
                       │0      │9       │
                       │1      │8       │
                       │13     │86      │
                       │26     │73      │
                       │260    │739     │
                       │435    │564     │
                       │678    │321     │
                       │495    │504     │
                       │17935  │82064   │
                       └───────┴────────┘

10. (5 баллов) Отгадайте черный ящик.

                     ┌───────┬────────────┐
                     │Вход   │Выход       │
                     ├───────┼────────────┤
                     │2      │10          │
                     │31     │1101        │
                     │26     │1022        │
                     │260    │102200      │
                     │345    │110220      │
                     │6782   │22033010    │
                     │94513  │3302200111  │
                     │519374 │200133110302│
                     └───────┴────────────┘

   11. (5 баллов) Прочитайте зашифрованный текст и объясните спо-
соб построения  кода.  Известно, что числом "312327" закодировано
слово "кто".

- 312327 2314 2342312732? - 24262527243330 312723.
- 10 232723, 312327 2837 3011413323 3127173731! - 27234037233330
  28373428423127293719.
- 4220, 2625272423332337, 292837, 31423537232410, 26272542! -
  243142344230 312723 33 40 27383328 262514352731 2731423442302410
  2842 383725374037.

   12. (3 балла)  Написать программу для исполнителя Плюсик, вы-
числяющую следующее арифметическое выражение:
              1111*7 - 17*(874 - 6*(37 + 9*11)+345)

   13. (5 баллов) Написать программу для исполнителя Плюсик, вы-
числяющую следующее арифметическое выражение:

             823 - 11*7   34*15 - 45*3 + 685
     1004 -  ────────── * ──────────────────
                373       31*11 + 27*7
      ──────────────────────────────────────
       822 - 67*3 + 45*(417 - 46*7) - 3896

   14. (4 балла) На одном из перевернутых кубиков в пятой строке
поля Кукарачи - буква "Ь". Найдите ее и составьте слово  МЫШЬ. В
первом столбце третьей строки расположена  буква  "Ф"  - ее надо
спихнуть в ров.

                1 2 3 4 5 6 7 8 9 10
               ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
             1 │М│Ы│Ш│ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             2 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             3 │Ф│ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             4 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             5 │ │?│?│?│?│?│?│?│?│ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             6 │ │ │ │ │ │ │ │ │¤│ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             7 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             8 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             9 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             10│ │ │ │ │ │ │ │ │ │ │
               └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

   15. (6 баллов) Автор Е.П.Лилитко. Требуется построить нового
исполнителя, "управляемого  данными", поведение которого  будет
полностью зависеть от  расположения букв на поле, а именно: из-
начально Кукарача движется вниз до  тех  пор,  пока не встретит
одну из букв "В", "Н", "Л",  "П" или "С". Встретив одну из этих
букв, он  продолжает  движение  соответственно "вверх", "вниз",
"влево", "вправо" или немедленно останавливается. На дальнейшем
пути Кукараче  может  вновь  повстречаться  одна из приведенных
букв, и тогда он вновь изменяет  направление вышеописанным спо-
собом. Для  нового исполнителя создайте программу (установите в
нужные места буквы-команды и Кукарачу), заставляющую ходить его
по расширяющейся спирали.

   16. (3 балла)  Под  Кукарачей  во  второй строке расположена
цифра (ее значение больше двух). Определить, какая это цифра, и
поставить ее в строку с соответствующим номером.
                1 2 3 4 5 6 7 8 9 10
               ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
             1 │¤│ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             2 │?│ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             3 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             4 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             5 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             6 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             7 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             8 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             9 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             10│ │ │ │ │ │ │ │ │ │ │
               └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

   17. (9 баллов) Автор Е.П.Лилитко. Кукарача расположен в ниж-
нем левом углу поля. Первая строка и первый  столбец поля пусты
за исключением буквы  "Г",  расположенной точно в левом верхнем
углу поля.  На остальном пространстве поля разбросано некоторое
количество букв "А", не более чем по одной на строку. Таким об-
разом, некоторые строки  содержат одну букву "А", а некоторые -
ни одной. Требуется очистить поле от  букв, попутно подсчитывая
их  количество.  В конце работы Кукарача должен остановиться  в
строке,  номер  которой равен количеству сброшенных в ров  букв
"А", т.е. если изначально на поле была одна буква "А", Кукарача
останавливается в  первой строке, если две  - во второй  и т.д.
Сообщение "Не могу" допускается только  в  том  случае, если ни
одной буквы "А" на поле не оказалось.

   18. (8 баллов) Во второй строке злоумышленник перемешал бук-
вы в слове ЭКРАН. Восстановить испорченное слово. После исправ-
ления  слово  может быть расположено в любой  строке  или  даже
столбце. В последнем случае его нужно читать сверху вниз.

                1 2 3 4 5 6 7 8 9 10
               ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
             1 │ │¤│ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             2 │ │?│?│?│?│?│ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             3 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             4 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             5 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             6 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             7 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             8 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             9 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             10│ │ │ │ │ │ │ │ │ │ │
               └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

   19. Кукарачья арифметика. Введем новые  обозначения  для ко-
манд исполнителя:


            2             ВЛЕВО  - 1
            │             ВВЕРХ  - 2
        1 ──┼── 3         ВПРАВО - 3
            │             ВНИЗ   - 4
            4
   Программа для исполнителя теперь задается числом,  состоящим
из цифр 1, 2, 3, 4, например, короткий поход Кукарачи

                ─┼─┼─┼─┼─┼─┼─┼─┼─┼─
                 │ │ │┌┼┐│ │ │ │ │
                ─┼─┼─┼┼┼┼┼─┼─┼─┼─┼─
                 │ │ │└┼¤│ │ │ │ │
                ─┼─┼─┼─┼─┼─┼─┼─┼─┼─

запишется в виде программы: 1234.
   Будем  полагать  также, что поле Кукарачи бесконечно (или, по
крайней мере, очень большое).
   а) (3 балла)  Доказать, что если траектория движения приводит
Кукарачу в  клетку, с которой он  начал движение, то  сумма цифр
числа, задающего программу исполнителя, четна.
   б) (2 балла) Верно ли обратное:  если сумма цифр числа, зада-
ющего программу  движения исполнителя, четна, то после выполнения
программы Кукарача оказывается в исходной позиции.
   в) (3 балла) Известно, что в программе исполнителя нет команд
ВВЕРХ, а число команд ВЛЕВО равно числу команд ВПРАВО. Докажите,
что в этом случае сумма цифр числа-программы делится на 4, а ес-
ли при  этом условии еще число  команд ВЛЕВО равно  числу команд
ВНИЗ, то сумма цифр числа-программы делится на 8.
