|
Республиканская олимпиада юных программистов.
г.Ворошиловград, 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 2 чисел {1,2,...,N2 (N>2). Составить алгоритм, который расположит эти числа в N групп так, что одновременно будут выполняться следующие условия:
1) Каждая группа содержит N чисел
2) Каждое число принадлежит только одной группе
3) Суммы чисел во всех группах одинаковы.
11 класс.
Теоретический тур.
Т11.1 Даны 3 литерные переменные S1, S2, S3. Составить алгоритм, который в переменной S1 заменяет все подстроки, равные S2, на подстроки, равные S3. Замены должны проводится слева направо; очередная замена выполняется на подстроке, в которой уже выполнены предыдущие замены.
Т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 класс.
Практический тур.
Составить и реализовать на ЭВМ программу, распознающую шестизначный почтовый индекс за наименьшее количество запросов. При одном запросе программа должна указывать человеку требуемый отрезок сетки и получать ответ, входит ли он в состав изображения цифры. |
