`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Республ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й.

Повний архів олімпіади (32 Kb)

© LIKT 1998-2024