XI республиканская олимпиада по информатике в Карелии (1997-98)

I тур

1. Дискета стоит 4 рубля 10 копеек за штуку. Пачка из одиннадцати дискет стоит 40 рублей. Коробка из 24 пачек -- 950 рублей. Составьте программу, которая по необходимому покупателю числу дискет вычислит количество штук, пачек и коробок. Программа должна максимально экономить деньги покупателя.

2. На полоске бумаги записаны несколько букв (от 3 до 10000). Указать минимальное число разрезов, необходимое для формирования новой полоски, в которой буквы будут идти по алфавиту. Например, для ВБВГААБ необходимо три разреза: В--БВ--Г--ААБ

3. Найти все числа от 1 до N, которые являются произведением ровно трех простых чисел. Например, одним из таких чисел будет 70, так как 70=2*5*7. (Простым, называется натуральное число, не имеющее других натуральных делителей, кроме себя и единицы.)

4. Из правильного математического выражения со скобками удалили все, кроме скобок. Получилась правильная последовательность скобок, в которой каждой открывающей скобке соответствует закрывающая. После этого каждой открывающей скобке поставили в соответствие число, показывающее, сколько всего скобок (открывающих и закрывающих) расположено между данной открывающей скобкой и соответствующей ей закрывающей.
Пример расстановки чисел:

( ( ) ( ( ) ( ) ) ( ( ) ) ( ) )
14 0 4 0 0 2 0 0

Напишите программу, которая по заданной последовательности чисел восстановит исходную последовательность скобок или сообщит, что это невозможно.

Примечание: баллы за задания выставлялись с учетом количества человек, решивших задачу. Например, если задачу решило 3 человека, то каждый получает за нее 3 балла. Если задачу решил только один -- он получает все 9 баллов. Задача считалась решенной только с случае прохождения всех тестов.

II тур

Требуется написать и предоставить программу игры "Гравикс". Разумеется, для этого Вам предстоит придумать и реализовать стратегию игры в "Гравикс" за компьютер.

Описание игры "Гравикс" (см. также здесь - он-лайновая версия подобной игры):

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

Пример игровой ситуации:

Правила проведения чемпионата игровых программ

Для проверки компьютерных стратегий мы предполагаем провести соревнование между работающими программами. Для этого каждая программа должна удовлетворять некоторым требованиям по вводу и выводу.
Программа получает игровое поле из файла fld и, сделав свой ход, записывает его туда же. Для работы с файлом жюри предоставляет две процедуры (getfld и putfld), которые делают ввод и вывод игрового поля соответственно. Процедура getfld помещает игровое поле в глобальный массив fld[5][7]. Каждый элемент этого массива либо 0 (нет фишки), либо 1 (своя фишка), либо 2 (фишка противника).
Ваша программа должна использовать эти процедуры в неизменном виде и делать свой ход, поместив 1 в соответствующее место массива.
Корректность делаемых программами ходов будет проверять специальная программа. Выдача некорректного хода засчитывается как поражение.
Каждый участник олимпиады предоставляет только одну версию программы. В ходе турнира каждая программа сыграет с каждой по два раза: один раз она будет ходить первой, другой раз -- второй. За выигрыш дается два очка, за ничью (что бывает крайне редко) одно, за проигрыш (или некорректную игру) -- 0 очков. Доработка программы после начала турнира не допускается. Каждый ход не должен занимать более 15 секунд "раздумий", иначе также засчитывается поражение. В случае дважды проявившейся некорректной игры и/или злоупотребления временем работы программа исключается из турнира.
Для проведения турнира была использована программа-арбитр arbitr.c, а перед началом тура участникам были даны процедуры ввода вывода fld.bas, fld.pas, fld.c, и fld.h. Их можно взять здесь.

Участники

Принимало участие 9 человек. Из них 2 из районов республики (Сегежа и Костомукша), остальные представляли город Петрозаводск. 1 человек из 9-го класса, 1 -- из 10-го, остальные -- учащиеся 11 класса.

Результаты

По первому туру:

По второму туру:

Окончательные результаты:

Организаторы и жюри

Члены жюри: В.В.Бондаренко (председатель), Р.А.Сузи, С.В.Мацко
Помогали в проведении туров олимпиады: В.А.Токарев (председатель оргкомитета)
Спонсор олимпиады: компания Сплайн

Организаторы олимпиады: Министерство образования Республики Карелия и Карельский институт повышения квалификации работников образования