64
I Международная олимпиада по информанике
Канддаат технических наук
В. М. КИРЮХИН
В этом году по решению ЮНЕСКО, принятому на 24 сентября в 1987 году, состоялась I Международная олимпиада по информанике. Олимпиада проводилась с 15 по 20 мая в Народной Республики Болгарии, в г. Правец, и была приурочена к третьему международному конгрессу «Дети в информационномвеке».
Тринадцать стран (Болгария, Венгрия, Вьетнам, ГДР, Греция, Зимбабе, Китай, Куба, Польша, Советский Союз, ФРГ, Чехословакия и Югославия) присладаны своих школьников, возраст которых не превышал 19 лет, на первую Международную олимпиаду по информанике. Согласно положению об олимпиаде в состав каждой команды могло входить максимум trope школьников. Все страны, за исключением Венгрии и Югославии, воспользовались этим правом. Команды Венгрии и Югославии были представлены двумя участниками; от Болгарии как страны-организатора в олимпиаде участвовали две команды. Кроме того, помимо сборной команды Советского Союза, получили приглашение для участия в олимпиаде также команда г. Переславля-Залесского и команда Посольства СССР во Франции.
Состав команды Советского Союза был определен по результатам весенних сборов, которые состоялись в начале мая в Молодежном центре ЦК ВЛКСМ «Олимпиец» в г. Химки, и II Всесоюзной олимпиады по информанике. В итоге нашу страну в Болгарии представляли Илья Доголяцкий и Лев Новик, учащиеся школь № 239 г. Ленинграда и Андрис Чайпятис, учащие школь № 28 г. Каунаса. Руководителем команды был автор настоящего статьи.
Олимпиада проводилась в один тур. На своем заседании международное жюри, возглавляемое профессором П. Кендеровым (НРБ) и в состав которого входили также руководители всех команды, отбрало одну из шести заранее подготовленных задач. Эта задача и была предложена для решения всем участникам.
Задача I МОИ
Дана последовательность из 2N ячеек. Две соседние из них — пустые, а в остальных расположены N—1 символов А и N—1 символов В.
Пример для N=5:
А | В | В | А | А | В | В
Правило перемещения: содержимое любых двух соседних неупустых ячеек можно, сохраняя их порядок, перемещать в пустые ячеек.
Цель: использую правил перемещения, достичь конфигурации, в которой все символы А расположены левее всех символов В. Местоположение пустых ячеек после перемещения не имеет значения.
Задание. Составить программу, которая:
- вводит с клавиатуры начального конфигурацию в виде последовательности символов А, В и нулей для пустых ячеек, а также моделирует перемещения;
- для заданной начальной конфигурации определяет по крайней мере один план перемещений, с помощью которого можно достичь целы, или сообщает, что такого плана не существует (вывод должен содержать начальную конфигурацию, промежуточные конфигурации после каждого шага, а также заключительную конфигурацию);
- находит неокоторый план, достигающий целы за минимальное число шага.
Результаты: представьте по крайней мере одно решение для примера, приведенного выше.
Для решения задачи отводилось четыре часа. В распоряжение каждой участника предоставлялся персональный компьютер «Правец-16» с соответствующей периферийной Разрешалось также в процессе решения задачи использовать свои персональные компьютеры, и команда ФРГ и Посольства СССР во Франции работали на приведенных им номыкомотехниках.
Каждай участник олимпиады имел право при выполнении задания работы с любой системой программного обеспечения в состав программиного обеспечения персонального
65
компьютера: Си, Паскаль, Бейсик, Лого и т. п. Поскольку при выборе оптимальной задачи учитываясь независимость ее от архитектуры конкретиного персонального компьютера, то необходимости в использовании специализированных пакетов программ не было.
По окончании решения оптимизации задачи каждой учитываясь независимость ее от архитектуры конкретиного персонального компьютера, то необходимость в использовании специализированных пакетов программ и результаты ее выполнения, полученные при помощи персонального компьютера, а также гибкий диск с последней версей программы, исходным текстом и результатами тестирования.
Проверка решения осуществлялась членами координатной комиссии и руководителей команд. Окончательное подведение итогов проводилось на засеединении междунарного жюри.
В процессе проверки задач осуществлялось тестирование программ с использованием четырех специализированных членами координатной комиссии и руководителей команд. Окончательное подведение итогов проводилось на засеединении междунарного жюри.
Проверка решения осуществлялась членами координатной комиссии и руководителей команд. Окончательное подведение итогов проводилось на засеединении междунарного жюри.
В процессе проверки задач осуществлялась тестирование программ с использованием четырех специализированных членами координатной комиссии и руководителей команд. Окончательное подведение итогов проводилось на засеединении междунарного жюри.
Программы победителей оптимизации проверялись также при , чтобы оценить еще эффективность алгоритма, хотя сделать это членам междунарного жюри было несовсем просто.
Решение каждого учитывания оптимизации в ходе выполнения отдельных пунктов задачи оценывания соответствующего в 10, 40 и 40 баллов. 10 баллов жюри оставило в своей распоряжении для поощрения оригинальной решения, технически программирования и оформления программы и т. п.
При оценке первого задания 10 баллов начиналось за правильную организацию ввода данных и наличие проверки на корректность исходных данных. За второе 15 балами оценывалось нахождение хотя бы одного плана или 20 баллов нахождения если были найдены все планы; еще 20 баллов ставилось за вывод сообщения об отсутствии решения. Что касается третьего задания, то 15 баллов давалось на наличие в программе попытки минимизировать число шагов и