ZX Club #06 31 декабря 1997

Тусовка

News - Барнаульская олимпиада по информатике 1997 года.

         Олимпиада по информатике
         ════════════════════════

   В ноябре 1997 года, как и каждый год,
проходила олимпиада по информатике.
Участие приняли почти все школы. Несмотря
на то, что задания были у всех одинаковые,
баллы ставились каждой группой жюри
по-разному! Меня, ERASER'а, удивило, когда
в школе 101 за все задачи ставили по одно-
му баллу!?!?!? Итоги такой олимпиады соот-
ветствующие. Но перейдем от грустного к
более приятному. Для тех, кому интересно
порешать или просто посмотреть олимпиадные
задачи, предоставляется такая возможность:

     Задачи I тура кравевой олимпиады
     ────────────────────────────────

   1.Если человек, стоящий в очереди перед
Вами, был выше человека, стоявшего после
того человека, который стоял перед Вами,
то был ли человек, стоявший перед Вами,
выше Вас?

   2.Текст шифруется с помощью таблицы:
каждой цифре сопоставляется одна из трех
букв, расположенных под ней в таблице, а
знаку "*" пробел или одна из букв "ю","я".

      Расшифруйте следующий текст:

5343934*150413*6*8156215044414**305041080

┌──┬───┬───┬───┬───┬───┬───┬───┬───┬───┬─┐
│0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │*│
├──┼───┼───┼───┼───┼───┼───┼───┼───┼───┼─┤
│а │ г │ ж │ й │ м │ п │ т │ х │ ш │ ы │ю│
├──┼───┼───┼───┼───┼───┼───┼───┼───┼───┼─┤
│б │ д │ з │ к │ н │ р │ у │ ц │ щ │ ь │я│
├──┼───┼───┼───┼───┼───┼───┼───┼───┼───┼─┤
│в │ е │ и │ л │ о │ с │ ф │ ч │ ъ │ э │ │
└──┴───┴───┴───┴───┴───┴───┴───┴───┴───┴─┘

   3.Четыре черепахи, которые находятся в
вершинах квадрата со стороной <а> пикселей
начинают одновременно двигаться с постоян-
ной по деличине скоростью <v>, причем пер-
вая черепаха держит курс на вторую,
вторая - на третью, третья - на четвертую,
четвертая - на первую. Нарисовать путь
движения черепах при разных соотношениях
между <a> и <v>. Вывести на экран траек-
тории движения черепах.

   4.Пусть A - 2n-занчное число (первая
цифра не 0). Назовем число A - особым, ес-
ли оно само является точным квадратом и
числа, образованные его первыми n-цифрами
и его последним n-цифрами также являются
точным квадратами (при этом второе число
может начинаться с цифры 0, но не должно
быть равно нулю). Таким числом, например,
явлвется число 49.

   а) Найдите все двухзначные и четырех-
значные особые числа;
   b) Покажите, что существует хотя бы
одно двадцатизанчное особое число.

   5.На алгоритмическом языке написано не-
которое арифметическое выражение. Составь-
те программу, которая выводит на экран со-
общение о наличии синтаксической ошибки в
записи этого выражения. Например, выраже-
ние 23++76 неправильное.

   (1) Для записи арифметических выражений
используются только знаки арифметических
операций и цифры.
   (2) Ограничения на использование каких-
либо арифметичексих символов отсутствует.

   6.Собрался Иван-Царевич на бой со
Змеем-Горынычем, трехглавым и треххвостым.
"Вот тебе меч-кладенец, - говорит ему
баба-Яга. - Одним ударом ты можешь срубить
Змею либо одну голову, либо две головы,
либо один хвост, либо два хвоста. Запомни:
срубишь головы - новая вырастет, срубишь
хвост - два новых вырастут, срубишь два
хвоста - голова вырастет, срубишь две го-
ловы - ничего не вырастет". Составьте про-
рамму моделирования сражения Ивана-Цареви-
ча.

   Найдите решение, при котором:
   (1) Иван-Царевич побеждает Змей-Горыны-
   ча.
   (2) Змей-Горыныч побеждает Ивана-Царе-
   вича.
   (3) Какова оптимальная модель битвы (За
   какое наименьшее количество ударов
   Иван-Царевич может срубить Змею все го-
   ловы и все хвосты).

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

Алгоритм:
Пусть задан массив S(1),S(2),...,S(n)  (1)
Пирамидой называется непустая последо-
вательность элементов (1)
вида S(p),S(p+1),...,S(p)(1<=p<=q<=n)
для которой выполнено одно из следующих
условий.
1) 2p>q
2) 2p=q и S(p)>=S(q)
3) 2p<q и
           S(j)>=S(2j)(p<=j<=q/2)
           S(j)>=S(2j+1)(p<=j<=(q-1)/2)
Из определения вытекает утверждение:
1.Для любой последовательности (1) подпос-
ледовательность
       S(n2+1),S(n2+2),...,S(n)
является пирамидой. Знаком  обозначается
деление нацело.
2.Если последовательность (1)-пирамида, то
       S(1)>=max S(j)
              1<=j<=n
3.Если последовательность (1)-пирамида, то
значение любого узла будет не меньше зна-
чений его левого и правого потомков.
Пример: Последовательность 90,70,11,8,3,9,
7,5,6,1,2 - является пирамидой.

       90      Пояснение:
      /       90-имеет потомков: 70 и 11
     70   11   70-имеет потомков:  8 и  3
     /   /   11-имеет потомков:  9 и  7
    /   9   7  8-имеет потомков:  5 и  6
   8    3       3-имеет потомков:  1 и  2
  /   /
 5  6 1  2

Алгоритм построения пирамидальной сорти-
ровки:
Этап I. Построени пирамиды. В (1) "хвост",
т.е. подпоследовательность
        S(n2+1),S(n2+2),...S(n)   (4)
как мы уже отмечали, является пирамидой.
Будем наращивать (4), добавляя к ней ос-
тавшиеся элементы из (1). Пусть S(j+1),
S(j+2),...,S(n)-пирамида. Припишем к ней
слева элемент S(j):
       S(j),S(j+1),...,S(n)
и преобразуем (5) снова в пирамиду. Для
этого "просеем" S(j) по соответствующей
веточке. Делается это так. Рассмотрим S(j)
и два его потомка S(2j) и S(2j+1).Если
S(j) не меньше потомков, то вычисление
прекращаем, ибо (5)-уже пирамида. В про-
тивном случае обмениваем значение S(j) и
max(S(2j), S(2j+1)) в соответствующих по-
зициях и "опустившийся" элемент продолжаем
просеивать тем же самым способом. В конце
концов преобразованная последовательность
(5) станет пирамидой.
   Продолжая наращивание (5), превратим
весь массив (1) в пирамиду. При этом ока-
жется выполненным неравенство (3).
   Объявлвем получнную пирамиду S текущей
и переходим к следующему этапу.
Этап II. Сортировка пирамиды. В текущей
пирамиде S первый элемент не меньше ос-
тальных. Поступим с ним так. Обменяем зна-
чениями концевые элементы S и укоротим S
справа на 1. Полученная последовательность
уже может и не быть пирамидой. Применим к
ней процесс "просеивания" для элемента
S(1), описанный на этапе I. Преобразован-
ная последовательность S становится пира-
мидой. Повторяя этап II(n-1) раз, отсор-
тируем S по невозрастанию.

   8.Не допуская разрыва ('не отвывая ка-
   рандаша от бумаги') и не проходя дважды
   по одной линии нарисовать n-пятиконеч-
   ных звезд. Вывести на экран.

       _/__/__/__/__/__/__/_
         /  /  /  /  /  /  /
       │/││/││/││/││/││/││/│

   9.Составить рекурсивный алгоритм рисо-
вания окружностей следующего вида: цент-
ральная окружность радиуса R, на этой ок-
ружности симметрично располагаются 4 ок-
ружности радиуса R/2 каждая. На каждой из
этих 4-х окружностях строятся еще 4 - ана-
логичным образом. И т.д. Рисование прекра-
щается, если радиус последних окружностей
становится меньше некоторого числа <k>.

                                    ERASER