I Всесоюзная олимпиада школьников по информатике

Квант 1988, №11-12 с. 82-84 Тег Z98W

I Всегоозная олимпиада школьников по информанике

А. Н. ВИЛЕНКИН

Заключительный этап I Всегоозной олимпиады школьников по информанике был проведен в Свердловске с 13 по 20 апреля 1988 года. 80 школьников из всех союзных ресурсных собрались вместе, чтобы померить силами.

Торжественное открытие олимпиады состоялось 14 апреля во Дворце культуры «Урал» — современном, простом и удобном. Участников олимпиады привствовали заведующий отделом науки и учебных заведений обома КПСС А. Г. Жданович, академик Г. С. Поселов, представитель центраальногооргкомитета Всегоозной олимпиады школьников Т. А. Сарычева и другие. Жорги олимпиады возглавлял академик Н. Н. Красовский, оргкомитет — зам. председателя Свердловского общественного образования А. А. Леонов. В тот же день школьники начали знакомиться с вычислительной техникой, на котором им предстояло работать. Свердловчане представили для проведения олимпиады более 80-ти компьютеров «Роботрон—1715». Практические все приходилось тирая не работали, что поставило участников олимпиады в равное положение. С другой стороны, эти компьютеры были к тем, с которых участники олимпиады обещались раны, и за два дня (14 и 16 апреля) техническа была выполнена.

Олимпиада проходила в два тура. Теоретический тур состоялся 15 апреля. Были предложены 4 задачи, на решение которых ответилось три с половиной часа. При этом алгоритмы разрешалось писать на любом достаточно распространном языке программирования (алгоритмический язык информации, Паскаль, Рапира, Бейсик, Алгол, Фортран, Си и др.). Задача на составление алгоритма считалась решенной, если представленный алгоритм был правильным. Дополнительные баллы присудались за простоту и оригинальность алгоритма, обоснование его правильности, наличие комментариев и за эффективность (мало время работы, использующий объем памяти). При проверке задачи оценка (0—5 баллов) умножалась на коэффициент, характеризующий трудность задачи (он зависит от числа участников, решивших эту задачу); этот коэффициент приведен в скобках после номера задачи.

Задачи теоретического типа

T1 (*7). Дан алгоритм:
алг задачal (цел n)
арг n
нач цел k, i
k:=n
i:=2
пока k≠1
нц
если остаток (k, i)=0
то печать (i)
k:=k/i
инче i:=i+1
все
кц
кон

Команда печать (i) печатает число i; остаток (k, i) — остаток от деления k на i. Какие числа будут напечатаны при использовании алгоритма задачal (n) для целого n≥1? Обосновайте ответ.

T2 (*6). Прямогогольник, стороны которого параллельны осем координат, будем задавать координаты его левого нижнего и правого верхнего углов. (Всего, таким образом, для задачи прямогогольника понадобится 4 числа). Заданы два прямогогольника Пр1 и Пр2. Определите площадь той части прямогогольника Пр1, которая не входит в Пр2. (Алгоритм должен быть пригоден для всех вариантов расположения Пр1 и Пр2.)

T3 (*9). В стране имеет n городов, пропумерованных от 1 до n; между неокотрыми из них налажено самолетное сообщение. Таблица есть_рейс [1:n, 1:n], содержит информацию о рейсах: есть_рейс [i, j] равно 1, если i≠j и из города i есть рейс в город j, и равно 0 в противном случае. (Рейс проходят без промежуточных посадок; наличие рейса из i в j не гарантирует наличие рейса из j в i). Известно, что:

из любого города можно попасть в любой другой (возможно, с пересадками);
в любой город прибывает столько же рейсов, сколько вылетает (в i-м столбце таблицы есть_рейс столько же единиц, столбко в i-й строке).
Доказать, что можно вылететь из неокотрого города и, воспользоватьсяровно

Теоретический тур.
Машинный тур.
Победители олимпиады и презеры премии «Кванта» (слева направо): С. Ковалев, В. Калашников, В. Завалишин, Г. Нищанов, И. Овчаренко, С. Калиниценко, М. Плукас, А. Ващилло.

по одному разу каждой рейсом, вернуться в этот же город. Составить алгоритм нахождения такого маршрута.

(Cуществует алгоритм, требующий выполнения не более $Cn^4$ команд для некоторой константы $C$ , не зависит от $n$ ).

T4 (*10). 3 000 000 человек с различными фамилиями выступлись в затылок друг другу. Каждый, кроме первого, написал на листке бумаги фамилию стоящего перед ним и свою фамилию. Все 2 999 999 листков бумаги перемешали и информацию (упорядоченные пары фамилии) записали на магнитную ленту. Как возможно быстрее узнать фамилию 1 234 567-го человека? В вашем распоряжении ЭВМ с небольшой оперативной памяти (64 Кб) и ограниченным количеством магнитофонов (≤32).

Машинный тур был проведен 17 апреля на базе учебно-производственного комбината № 9 и Уральского государственного университета, программы можно было писать на Бейсике или Паскале. В задачах машинного типа оценывания доступный результат; использование компьютера было лишь средством. Дополнительными баллами оценывания изложение метода решения, его обоснование, комментарии к программе и т. п.

Задача машинного тура

M1 (*3). Последовательность целых положительных чисел $a_0, a_1, a_2, \dots$ строится так: если $a_n$ четно, то $a_{n+1}=a_n/2$ ; если $a_n$ нечетно, то $a_{n+1}=3a_n+1$ .

Найти минимальное $n$ , для которого $a_n=1$ , если
a) $a_0=27$ ;
b) $a_0=2 000 007$ .

M2 (*13). Для каждой целого положительного числа $n$ будем рассматривать всевозможные его представления в виде суммы одного или нескольких целых положительных слагаемых. Составить таблицу, в которой для каждой $n$ указано число таких представлений (без учета порядка: представления $3=2+1$ и $3=1+2$ считаются одинаковыми). Например, для $n=4$ таких представлений $5(4, 3+1, 2+2, 2+1+1, 1+1+1+1)$ . (Чем дальше будет заполнена таблица, тем выше будет оценывать работу).

Разбор задач был проведен 18 апреля утром, вечером того же дня рассматрилась апелляция. 19 апреля во Дворце культуры «Урал» состоялся комбинаторный фестиваль. Участики олимпiadы, конечно же, привезли с собой много

гибких дисков и кассет с программами, и им хотелось показать свои программы, посмотреть чужие и, возможно, обменяться программными продуктами. Именно это и процесс dello на фестивале. Организаторы предоставили школьникам и руководительом команда семые разные комплютеры, и все имеющиеся программы были продемонстрированы в действии. Устройте纵импады показали также свои программы разработки для средней школьки.

Культурная программа включала посещение свердловских музеев и театров, цирка, поедку на границу «Европа-Азия».

Награждение победителем и закрытие олимпiadы состоялось вечером 19 апреля. 5 школьников получили дипломы I степени (они набрали 125—156 баллов), 9 школьников — дипломы II степени (87—116 баллов) и 15 школьников — дипломы III степени (59—78 баллов). 10 участников олимпiadы были нагradжены специальными признами научных и общественных организаций, в том числе призами журнала «Квант» за высокую математическую культуру работы — Завалишин В. (Москва, с.ш. № 542), Калиниченко С. (Киев, с.ш. № 145), Ковалев С. (Горький, с.ш. № 40) и Овчаренко И. (Хабаровск, с.ш. № 32).

Что же еще остается сказать об этой, первой Всесоюзной олимпiadе школьников по информации? Надо, прежде всего, поздравить и поблагодарить всех, кто хоть в какой-то мере помог предолеть все трудности, организовать и провести олимпiadу. Надо поздравить победителем, они самых первых уголках нашей страны активизируется олимпiadная работа и в области информации. Вершина олимпiadнойlectицы обозначена.