|
V Республiканська олiмпiада юних програмiстiв.
Суми, 1992 р.
10-11 клас
Теоретичний тур.
Т1. Нехай масив A складається з N рiзних елементiв. Скласти алгоритм, який знаходить K-й елемент за порядком спадання.
Т2. Опуклий багатокутник задається координатами (X1,Y1), (X2,Y2),..., (XN,YN) його N вершин. Координати вершин є елементами вiдповiдних масивiв X та Y. Триангуляцiєю опуклого N-кутника називаеться довiльне його розбиття на N-2 трикутника за допомогою N-3 дiагоналей, що не перетинаються мiж собою. Вартiстю триангуляцiї називається сума довжин N-3 проведених дiагоналей. Скласти алгоритм пошуку триангуляцiї найменьшої вартостi заданого багатокутника. Для спрощення довжиною дiагонали, що з'єднує вершини (XI,YI) и (XJ,YJ), можна вважати число |XI-XJ| +|YI-YJ|.
Практичний тур.
П1. Росiйський текст зашифровано за допомогою деякого ключового слова таким чином:
1) Лiтери ключового слова пишуться багато разiв над лiтерами вхiдного текста;
2) До алфавiтного порядкового номера кожної лiтери текста додається алфавiтний порядковий номер вiдповiдної лiтери ключового слова;
3) Якщо результат перевищує 32, вiд ньоо вiднiмається 32;
4) Одержане число визначає порядковий алфавiтний номер лiтери в зашифрованому текстi.
Наприклад, вхiднi данi:
КЛЮЧК ЛЮЧ КЛЮЧКЛЮЧКЛ
"ФРАЗА ДЛЯ ШИФРОВАНИЯ" (КЛЮЧ - ключове слово) дадуть такий результат:
"ЯЬЯЯЛ РКЧ ГФУИЩОЯЕУЛ".
Лiтери е и ¸
спiвпадають, всi лiтери маленькi, латинськi замiнено росiйськими з тим же написанням, роздiловi знаки не перетворюються, довжина ключового слова дорiвнює 4.
Зашифрований текст мiстить умову другої задачi.
1. Розшифрувати текст, якщо ключове слово невiдоме. При розшифровцi радимо використовувати комп'ютер. Розв'язання повинно мiстити метод розшифровки с описом застосування ЕОМ, ключове слово и розшифрований текст.
2. За бажанням учасник може попросити ключове слово и розшифрувати текст. При цьому максимальна кiлькiсть балiв за практичний тур зменшується таким чином: якщо ключове слово було одержано на протязi 1-ої години, учасник одержує до 10% балiв, на протязi 2-ої години - 20%, на протязi 3-ої - 30%, 4-ої - 40%.
3. Використовуючи комп'ютер, розв'язати другу задачу.
Задача П2 була запропонована в 4-х варiантах:
П2. Варiант 4: ШХСЯВъЛ УРКЧЙЖД М, ТЮНССЦЙЕБП У ГЙБОЧ, Й Т, ъъЕХЩТБЙЙЛ Н ЗСЭЖЫ. ЦМРШъМУМ ШЬПУЩМНЬЬ, ЦПВЧЬБП ЛОПФСЮ ОРАМММЦЗЖ ЧЦМШХЦФА ВЙНМШЯ М Й Т С УБЯСЭЬТЙСУ Т ЫМВЫСВФ Б ЛЭЖ ВЙЦЙХ АФТЫЙ, ЦПВЧЬЬХ ъъЕХЩТБВъЛ Г Р С ЩЖ БЧРЖАПМУБИ О Г. ЭСЦБъСС ИЭЙГЖЭСЛ ЮЫОШЖЭЫъГ Б ЦС ЕЮФТОЛ ъъГЯЙРБВЕ РСГМ Э ЕАЬППЬ. |
