Республиканская олимпиада юных программистов.

г.Ворошиловград, 1990 г.

10 класс.

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

Т10.1 Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из n его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) Составить алгоритм, определяющий, побывал ли король дважды на одном и том же поле за минимальное возможное при заданном n количество вычислений.

Т10.2 Задан массив чисел A[1:N, 1:M], упорядоченный по убыванию по строкам и столбцам т.е.:

A[I,1] ? A[I,2] ? ... ? A[I,M] (при всех I)

A[1,J] ? A[2,J] ? ... ? A[N,J] (при всех J)

Найти элемент массива, равный заданному числу и напечатать его индексы (I,J). Напечатать слово "нет", если такого элемента не окажется. Решение необходимо найти за k*(M+N), а не за k*(M*N) операций, где k - константа, не зависящая от N и M.

Т10.3 Заданы N² чисел {1,2,...,N² (N>2). Составить алгоритм, который расположит эти числа в N групп так, что одновременно будут выполняться следующие условия:

1) Каждая группа содержит N чисел

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

3) Суммы чисел во всех группах одинаковы.

11 класс.

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

Т11.1 Даны 3 литерные переменные S₁, S₂, S₃. Составить алгоритм, который в переменной S₁ заменяет все подстроки, равные S₂, на подстроки, равные S₃. Замены должны проводится слева направо; очередная замена выполняется на подстроке, в которой уже выполнены предыдущие замены.

Т11.2 Задан массив чисел A[1:N, 1:M, 1:L], упорядоченный по убыванию по каждому измерению, т.е.:

A[I,J,1] ? A[I,J,2] ? ... ? A[I,J,L] (при всех I,J)

A[I,1,K] ? A[I,2,K] ? ... ? A[I,M,K] (при всех I,K)

A[1,J,K] ? A[2,J,K] ? ... ? A[N,J,K] (при всех J,K).

Найти элемент массива, равный заданному числу и напечатать его индексы (I,J,K). Напечатать слово "нет", если такого элемента не окажется. Решение необходимо найти за C*L*(M+N), а не за C*L*(M*N) операций, где C - константа, не зависящая от N,M и K.

T11.3 Составить алгоритм, определяющий последовательность выполнения N работ, если для каждой работы задан список работ, результаты которых она должна непосредственно использовать: этот список может быть пустым. Напечатать соответствующее сообщение, если последовательность работ нельзя определить. Наилучший алгоритм определяет порядок за K*(D+N) операций, где D - размер всех списков; K - константа, не зависящая от N и D.

10-11 класс.

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

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