| |
|
III Всеукраїнська олімпіада з інформатики
|
|
Республiканська олiмпiада юних програмiстiв.
м.Ворошиловград, 1990 р.
10 клас.
Теоретичний тур.
Т10.1 Одинокий король довго ходив по безкiнечнiй шахiвницi. Вiдома послiдовнiсть з n його ходiв (вгору, вниз, влiво, вправо, вгору-влiво i т.i.). Скласти алгоритм, який визначає, чи побував король двiчi на одном и тому самому полi за мiнiмальну можливу при заданному n кiлькiсть обчислень.
Т10.2 Задано масив чисел A[1:N, 1:M], упорядкований за спаданням по рядках i стовпчиках, тобто:
A[I,1] £
A[I,2] £
... £
A[I,M] (при всiх I)
A[1,J] £
A[2,J] £
... £
A[N,J] (при всiх J)
Знайти елемент массиву, який дорiвнює заданому числу и надрукувати його iндекси (I,J). Надрукувати слово "немає", якщо такого елемента не знайдеться. Розв'язання необхiдно знайти за k*(M+N), а не за k*(M*N) операцiй, де k - константа, що не залежить вiд N i M.
Т10.3 Задано N2 чисел {1,2,...,N2} (N>2). Скласти алгоритм, який розiб'є цi числа на N груп так, что одночасно будуть виконуватися такi умови:
1) Кожна група мiстить N чисел
2) Ккожне число належить тiльки однiй групi
3) Суми чисел в усiх групах однаковi.
11 клас.
Теоретичний тур.
Т11.1 Дано 3 лiтернi змiннi S1, S2, S3. Скласти алгоритм, який у змiннiй S1 замiнює всi пiдрядки, що дорiвнюють S2, на пiдрядки, що дорiвнюють S3. Замiни повиннi проводитись злiва направо; чергова замiна виконується на пiдрядку, в якому вже виконанi попереднi замiни.
Т11.2 Задан масив чисел A[1:N, 1:M, 1:L], впорядкований за спаданням по кожному вимiру, тобто:
A[I,J,1] £
A[I,J,2] £
... £
A[I,J,L] (при всiх I,J)
A[I,1,K] £
A[I,2,K] £
... £
A[I,M,K] (при всiх I,K)
A[1,J,K] £
A[2,J,K] £
... £
A[N,J,K] (при всiх J,K).
Знайти елемент массиву, який дорiвнює заданому числу и надрукувати його iндекси (I,J,К). Надрукувати слово "немає", якщо такого елемента не знайдеться. Розв'язання необхiдно знайти за С*L*(M+N), а не за C*L*(M*N) операцiй, де k - константа, що не залежить вiд N, M, K.
T11.3 Скласти алгоритм, який визначає послiдовнiсть виконання N робiт, якщо для кожної роботи задано список робiт, результати яких вона повинна безпосередньо використовувати: цей список може бути порожнiм.Надрукувати вiдповiдне повiдомлення, якщо послiдовнiсть робiт не можна визначити. Найкращий алгоритм визначає порядок за K*(D+N) операцiй, де D - розмiр всiх спискiв; K - константа, яка не залежить вiд N i D.
10-11 клас.
Практичний тур.
Скласти та реализувати на ЕОМ програму, яка розпiзнає шестицифровий поштовий iндекс за найменьшу кiлькiсть заппитань. При одному запитаннi програма повинна вказати користувачу потрiбний вiдрiзок сiтки i одержати вiдповiдь, чи входить вiн у склад зображення цифри. |
| | |
|
