Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
1988 год
     
I Всеукраинская олимпиада по информатике

Республиканская олимпиада 1988 г.

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

9 класс

Задача ¹ 1

Вокруг считающего стоят N человек, один из которых назван первым, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий ведет счет до М, начиная с первого. Человек, на котором остановился счет, выходит из круга. Счет продолжается со следующего человека (при этом выбывшие из круга не считаются) и так до тех пор, пока не останется один человек. Определить начальный номер этого человека.

Задача ¹ 2

Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 20 строк. Игроки задают начальные значения переменных А и В из множества {0,1} (Например, А=0, В=0 или А:=1, В:=0), а затем по очереди вписывают по одному из операторов вида

1. А:=1-А

2. В:=1-В

3. ЕСЛИ А=1 ТО В:=1-В ВСЕ

4. ЕСЛИ А=0 ТО В:=1-В ВСЕ

5. ЕСЛИ В=1 ТО А:=1-А ВСЕ

6. ЕСЛИ В=0 ТО А:=1-А ВСЕ

в любую незанятую строку. Когда заполнены все строки, полученная последовательность операторов выполняется при заданных начальных значениях. Если после исполнения алгоритма значения А и В будут различны, побеждает первый игрок, если равны - побеждает второй игрок. Определите при каждом начальном наборе А и В, есть ли у кого-либо из игроков выигрышная стратегия? Если стратегия есть, то в чем она заключается?

Задача ¹ 3

Последовательность 1,0,0,1,0,1,1,0,0,1,1,0,1,0,.. строится так: первый ее элемент равен 1, остальные получаются из элементов с меньшими номерами с помощью операции отрицания:

1, eсли X = 0

NOT (X) =

0, если X = 1

Второй элемент равен отрицанию первого, то есть 0; третий и четвертый равны отрицанию первого и второго соответственно; элементы с пятого по восьмой равны отрицаниям элементов 1-4 соответственно, и т.д.; элементы с номерами 2k +1 ,..., 2 k+1 равны отрицаниям элементов с номерами 1,2,...,2k соответственно. Составить программу, вычисляющую N-й член описанной последовательности по заданному N.

10 класс

Задача ¹ 1

В некотором арифметическом выражении удалили все символы, кроме скобок. Составить алгоритм, определяющий по полученной последовательности скобок, правильно ли они были первоначально расставлены.

Задача ¹ 2

Два человека играют в "алгоритмическую игру". Игровое поле - лист бумаги в линейку, содержащий 20 строк. Игроки по очереди вписывают в любую незанятую строку по одному из операторов вида:

1. A:=1-A

2. B:=1-В

3. ЕСЛИ А=1 ТО В:=1-В ВСЕ

4. ЕСЛИ А=0 TO B:=1-B ВСЕ

5. ЕСЛИ В=1 ТО А:=1-А ВСЕ

6. ЕСЛИ В=0 ТО А:=1-А ВСЕ

Когда все строки заполнены, переменным А и В присваиваются значения из множества {0,1} (например, А:=1,В:=1 или А:=0,В:=1) и выполняются все операторы в той последовательности, в которой они записаны. Если в результате значения А и В различны, побеждает первый игрок, если равны - второй игрок. Есть ли у кого- либо из игроков стратегия, гарантирующая выигрыш независимо от начальных значений А и В?

Задача ¹ 3

Возьмем полоску бумаги, согнем ее пополам К раз следующим образом:

и развернем полоску так, чтобы углы на всех сгибах стали равны 90 . Посмотрев на торец полоски, увидим ломаную, которая называется "драконовой ломаной К-го порядка":

К=0 К=1 К=2 К=3

Написать алгоритм, который, получая на входе числа K и L, рисует драконову ломаную К-го порядка с длиной одного звена, равной L.

ПРАКТИЧЕСКИЙ ТУР.

1 вариант

Задача ¹ 1

Дан список всех 64 полей шахматной доски 8 х 8 в виде числовых координат. Написать алгоритм, который определяет, является ли этот список маршрутом ферзя по всем полям доски.

Задача ¹ 2

Дана упорядоченная по возрастанию линейная таблица натуральных чисел А[1] <...< A[N]. Найти наименьшее натуральное число, не представимое в виде суммы некоторых чисел из таблицы. Сумма может состоять и из одного слагаемого; каждый элемент таблицы может входить в нее не более одного раза.

Приемлемое решение должно укладываться в С*N действий, где С - постоянная, не зависящая от N.

2 вариант

Задача ¹ 1

Составить алгоритм, получающий на входе число K и выдающий на выходе К-тое по порядку четырехзначное число, у которого никакие две цифры не равны между собой. Первым таким числом является 0123.

Задача ¹ 2

Имеются две таблицы натуральных чисел А[1:N] и B[1:N]. Найти перестановку i[1], i[2],..., i[N] чисел 1, 2,...,N, для которой сумма

A[1] * B[i[1]] + ... +A[N] * B[i[N]] минимальна. В перестановку каждое число должно входить только один раз.

Достаточно эффективным будет считаться алгоритм, требующий выполнения К * N операций, где К - постоянная величина, не зависящая от N. Наилучшее известное решение требует выполнения К*N*Log N операций.

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

© Всеукраинский виртуальный центр олимпиад школьников "ОЛІМП"

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"