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. На квадратном поле размером 3*3 с помощью датчика случайных чисел расставлены 8 фишек с номерами от 1 до 8 (рис.1). Построить алгоритм расстановки фишек по возрастанию их номеров так, как показано на рис.2. Передвигать фишки можно только на соседнюю свободную позицию.

1

7

3

 

1

2

3

6

5

2

 

4

5

6

8

4

   

7

8

 

Рис. 1

 

Рис. 2

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

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

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

1) каждая группа содержит точно 11 чисел;

2) каждое число принадлежит только одной группе;

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

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

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