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

Красноярск, 17-22 марта 1989 года

Задачи

Теоретический тур

Задача 1. Разбиение

Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников.

Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD.

Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.

Задача 2. Две окружности

Построить алгоритм, моделирующий на экране дисплея движение с постоянной скоростью V двух окружностей радиуса R внутри прямоугольной области, заданной координатами своих вершин. В момент начала движения координаты центров окружностей - (X1,Y1) и (X2,Y2), а углы между траекториями движения и вертикальной осью координат - A1 и A2. Столкновения окружностей между собой и с границами области - упругие.

Задача 3. Домино

Данные N косточек домино по правилам игры выкладываются в прямую цепочку начиная с косточки, выбранной произвольно, в оба конца до тех пор, пока это возможно.

Построить алгоритм, позволяющий определить такой вариант выкладывания заданных косточек, при котором к моменту, когда цепочка не может быть продолжена, "на руках" останется максимальное число очков.

Задача 4. Диски и шары

Имеются два одинаковых диска. На каждом из них есть круглое отверстие радиуса R, касающееся границы диска. Диски расположены горизонтально, плотно прижаты друг к другу и скреплены общей осью, проходящей через их центр вращения. Верхний диск неподвижен, а нижний равномерно вращается с заданной угловой скоростью W2. Вдоль границы верхнего диска катятся с постоянной угловой скоростью W1 N шаров радиуса R. Шары расположены плотно друг за другом и пронумерованы цифрами от 1 до N. Если при совпадении отверстий на дисках шар проваливается, то плотность цепочки шаров "мгновенно" восстанавливается.

Построить алгоритм, позволяющий определить номера первых M шаров, выпавших при совпадении отверстий на дисках, если в момент начала движения угол между центрами отверстий верхнего и нижнего дисков был равен A1, а угол между центрами отверстия верхнего диска и первым шаром цепочки - А2. Угол сектора, по дуге которого расположена цепочка шаров, равен А3.

Практический тур

Задача 5. Простые числа

На интервале (1000; 9999) найти все простые числа, каждое из которых обладает тем свойством, что сумма первой и второй цифры записи этого числа равна сумме третьей и четвертой цифр.

Задача 6. 3**512

Найти все цифры десятичной записи числа 3512.