|
Республiканська олiмпiада 1988 р. Теоретичниий тур.
9 клас Задача № 1 Навколо ведучого стоять N людей, один з яких вважається першим, а iншi занумерованi за годинниковою стрiлкою числами вiд 2 до N. Ведучий рахує до М, починаючи з першого. Той, на якому зупинився рахунок, виходить з кола. Рахунок продовжується з наступної людини (при цьому тi, що вибули з кола, не рахуються) и так доти, доки не залишиться одна людина. Визначити початковий номер цiєї людини.
Задача № 2 Двоє грають в "алгоритмiчну гру". Iгрове поле - аркуш паперу в лiнiйку, що мiстить 20 рядкiв. Гравцi задають початковi значення змiнних А i В з множини {0,1} (Наприклад, А=0, В=0 або А:=1, В:=0), а потiм по черзi вписують по одному з операторiв вигляду
1. А:=1-А 2. В:=1-В 3. ЯКЩО А=1 ТО В:=1-В ВСЕ 4. ЯКЩО А=0 ТО В:=1-В ВСЕ 5. ЯКЩО В=1 ТО А:=1-А ВСЕ 6. ЯКЩО В=0 ТО А:=1-А ВСЕ
в будь-який незайнятий рядок. Коли заповненi всi рядки, одержана послiдовнiсть операторiв виконується при заданих початкових значеннях. Якщо пiсля виконання алгоритма значення А i В будуть рiзнi, перемагає перший гравець, якщо рiвнi - перемагає другий гравець. Визначте при кожному початковому наборi А i В, чи є в когось iз гравцiв виграшна стратегiя? Якщо стратегiя є, то в чому вона заключається?
Задача № 3 Послiдовнiсть 1,0,0,1,0,1,1,0,0,1,1,0,1,0,.. будується так: перший її елемент дорiвнює 1, всi iншi одержуються з елементiв з меншими номерами за допомогою операцiї заперечення: 1, якщо X = 0 NOT (X) = 0, якщо X = 1 Другий елемент дорiвнює запереченню першого, тобто 0; третiй и четвертий джорiвнюють запереченню першого i другого вiдповiдно; елементи з п'ятого по восьмий дорiвнюють запереченням елементiв 1-4 вiдповiдно, i т.д.; елементи з номерами 2k +1 ,..., 2 k+1 дорiвнюють запереченням елементiв з номерами 1,2,...,2k вiдповiдно. Скласти програму, яка пiдраховує N-й член описаної послiдовностi для заданого N.
10 клас Задача № 1 В деякому арифметичному виразi вилучили всi символи, крiм дужок. Скласти алгоритм, що визначає для одержаної послiдовностi дужок, чи правильно вони були розставленi.
Задача № 2 Двоє грають в "алгоритмiчну гру". Iгрове поле - аркуш паперу в лiнiйку, що мiстить 20 рядкiв. Гравцi задають початковi значення змiнних А i В з множини {0,1} (Наприклад, А=0, В=0 або А:=1, В:=0), а потiм по черзi вписують по одному з операторiв вигляду
1. A:=1-A 2. B:=1-В 3. ЯКЩО А=1 ТО В:=1-В ВСЕ 4. ЯКЩО А=0 TO B:=1-B ВСЕ 5. ЯКЩО В=1 ТО А:=1-А ВСЕ 6. ЯКЩО В=0 ТО А:=1-А ВСЕ
Коли всi рядки заповненi, змiнним А i В присвоюються значення з множини {0,1} (наприклад, А:=1,В:=1 або А:=0,В:=1), одержана послiдовнiсть операторiв виконується при заданих початкових значеннях. Якщо пiсля виконання алгоритма значення А i В будуть рiзнi, перемагає перший гравець, якщо рiвнi - перемагає другий гравець. Чи є в когось iз гравцiв стратегiя, шо гарантує виграш незалежно вiд початкових значень А i В?
Задача № 3 Вiзьмемо смужку паперу, зiгнемо її навпiл К разiв таким чином:
i розвернемо смужку так, щоб кути на всiх мiсцях згину дорiвнювали 90 . Якщо подивитись на торець смужки, побачимо ламану, яка називається "драконовою ламаною К-го порядку":
К=0 К=1 К=2 К=3
Написати алгоритм, який, одержуючи на входi числа K i L, малює драконову ламану К-го порядку з довжиною однiєї ланки L.
ПРАКТИЧНИЙ ТУР.
1 варiант
Задача № 1 Дан список всiх 64 клiтин шахiвницi 8 х 8 у виглядi числових координат. Написати алгоритм, який визначає, чи є цей список маршрутом ферзя по всiх клiтинах шахiвницi.
Задача № 2 Дана впорядкована за зростанням линiйна таблиця натуральних чисел А[1] <...< A[N]. Знайти найменше натуральне число, яке не можна представити у виглядi суми деяких чисел з таблицi. Сума може складатись i з одного доданку; кожний елемент таблицi може входити в неї не бiльше одного разу. Прийнятне розв'язання повинно вкладатися в С*N дiй, де С - постiйна, що не залежить вiд N.
2 варiант Задача № 1 Скласти алгоритм, який одержує на входi число K и видає на виходi К-те за порядком чотирицифрове число, в якого ниякi двi цифрi не дорiвнюють мiж собою. Першим таким числом є 0123.
Задача № 2 Маємо двi таблицi натуральних чисел А[1:N] i B[1:N]. Знайти перестановку i[1], i[2],..., i[N] чисел 1, 2,...,N, для якої сума A[1] * B[i[1]] + ... +A[N] * B[i[N]] мiнiмальна. В перестановку кожне число повинно входити тiльки один раз. Досить ефективним буде вважатись алгоритм, що потребує виконания К * N операцiй, де К - постiйна величина, яка не залежить вiд N. Найкраще вiдоме розв'язання потребує виконання К*N*LogN операцiй. |