|
Республиканская олимпиада юных программистов. г.Ворошиловград, 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 Заданы N2 чисел {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 класс. Практический тур. Составить и реализовать на ЭВМ программу, распознающую шестизначный почтовый индекс за наименьшее количество запросов. При одном запросе программа должна указывать человеку требуемый отрезок сетки и получать ответ, входит ли он в состав изображения цифры. |
[an error occurred while processing this directive]