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

Нальчик, 1990 год

Задачи

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

Задача 1. Квадрат

На двумерной плоскости задано N точек с координатами (X1, Y1), (X2, Y2), ..., (XN, YN). Построить алгоритм, позволяющий из этих точек выделить вершины квадрата, содержащего максимальное число заданных точек.

Примечание: предполагается, что точки, расположенные на сторонах квадрата, принадлежат ему.

Задача 2. Последовательность

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

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

Задача 3. Автобусы

В городе имеется n автобусных остановок, обозначенные числами 1, 2, 3, ..., n. Проложено r автобусных маршрутов, заданных последовательностями соседних остановок при движении автобуса в одном направлении: 

M1= (i11, i12, ..., i1m1),
M2= (i21, i22, ..., i2m2),
.........................,
Mr= (ir1, ir2, ..., irmr),
где ijk из множества чисел от 1 до n.

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

Задача 4. Игра "8"

На квадратном поле размером 3*3 с помощью датчика случайных чисел расставлены 8 фишек с номерами от 1 до 8, что привело к комбинации на рисунке 1. Построить алгоритм расстановки фишек по возрастанию их номеров, как на рисунке 2. Передвигать фишки можно только на соседнюю свободную позицию.
173 123
652 456
84  78 
Рисунок 1 Рисунок 2

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

Задача 5. 121 число

Заданы 121 натуральное число - 1, 2, 3, ..., 121.

Составить программу, которая расположит эти числа в 11 групп так, что одновременно будут выполняться следующие условия:

  1. каждая группа содержит точно 11 чисел;
  2. каждое число принадлежит только одной группе;
  3. сумма чисел в каждой отдельной группе одинакова для всех групп.

Задача 6. 77!

Составить программу, которая в полной записи числа 77! (77 факториал) укажет в порядке убывания номера разрядов, содержащих цифру 7.

Примечание: разряды числа нумеруются в следующем порядке: разряд единиц имеет номер 1, десятков - 2, сотен -3 и т.д.