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

Сумы, 1992 г.

10-11 класс

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

Т1. Пусть массив A состоит из N различных элементов. Составить алгоритм, который находит K-й элемент по порядку убывания.

Т2. Выпуклый многоугольник задается координатами (X₁,Y₁), (X₂,Y₂),..., (X_N,Y_N) его N вершин. Координаты вершин являются элементами соответствующих массивов X и Y. Триангуляцией выпуклого N-угольника называется произвольное его разбиение на N-2 треугольника с помощью N-3 непересекающихся диагоналей. Стоимостью триангуляции называется сумма длин N-3 проведенных диагоналей. Составить алгоритм поиска триангуляции наименьшей стоимости заданного многоугольника. Для упрощения длиною диагонали, соединяющей вершины (X_I,Y_I) и (X_J,Y_J), можно считать число |X_I-X_J| +|Y_I-Y_J|.

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

П1. Русский текст зашифрован с помощью некоторого ключевого слова таким образом:

1) Буквы ключевого слова пишутся много раз над буквами исходного текста;

2) К алфавитному порядковому номеру каждой буквы текста прибавляется алфавитный порядковый номер соответствующей буквы ключевого слова;

3) Если результат превышает 32, из него вычитается 32;

4) Полученное число задает порядковый алфавитный номер буквы в зашифрованном тексте.

Например, исходные данные:

КЛЮЧК ЛЮЧ КЛЮЧКЛЮЧКЛ

"ФРАЗА ДЛЯ ШИФРОВАНИЯ" (КЛЮЧ - ключевое слово) дадут следующий результат:

"ЯЬЯЯЛ РКЧ ГФУИЩОЯЕУЛ".

Буквы е и ? совпадают, все буквы строчные, латинские заменены русскими с тем же написанием, знаки препинания не преобразуются, длина ключевого слова равна 4.

Зашифрованный текст содержит условие второй задачи.

1. Расшифровать текст, если ключевое слово неизвестно. При расшифровке рекомендуется использовать компьютер. Решение должно содержать метод расшифровки с описанием использования ЭВМ, ключевое слово и расшифрованный текст.

2. По желанию участник может попросить ключевое слово и расшифровать текст. При это максимальное количество баллов за практический тур уменьшается таким образом: если ключевое слово было получено в течение 1-го часа, участник получает до 10% баллов, в течение 2-го часа - 20%, в течение 3-го - 30%, 4-го - 40%.

3. Используя компьютер, решить вторую задачу.

Задача П2 была предложена в 4-х вариантах:

П2. Вариант 4: ШХСЯВъЛ УРКЧЙЖД М, ТЮНССЦЙЕБП У ГЙБОЧ, Й Т, ъъЕХЩТБЙЙЛ Н ЗСЭЖЫ. ЦМРШъМУМ ШЬПУЩМНЬЬ, ЦПВЧЬБП ЛОПФСЮ ОРАМММЦЗЖ ЧЦМШХЦФА ВЙНМШЯ М Й Т С УБЯСЭЬТЙСУ Т ЫМВЫСВФ Б ЛЭЖ ВЙЦЙХ АФТЫЙ, ЦПВЧЬЬХ ъъЕХЩТБВъЛ Г Р С ЩЖ БЧРЖАПМУБИ О Г. ЭСЦБъСС ИЭЙГЖЭСЛ ЮЫОШЖЭЫъГ Б ЦС ЕЮФТОЛ ъъГЯЙРБВЕ РСГМ Э ЕАЬППЬ.