Курчатовская Олимпиада по информатике 2010 года

Правила проведения

Курчатовская олимпиада по информатике состоит из двух туров: заочного и очного. Очный тур будет происходить в Москве, в конце февраля 2010 года. Отбор участников очного тура происходит по результатам заочного тура. В олимпиаде может принимать участие любой школьник, обучающийся в 1-11 классе любой школы России.

Правила проведения заочного тура таковы: желающим предлагается две задачи, которые решаются дома, и не позднее 25 февраля 2010 года решения отсылаются по электронному адресу olymp09[at]inse.ru. Решения, присланные позднее 25 февраля, не рассматриваются ни при каких обстоятельствах. Дата поступления решений определяется днём получения нами вашего электронного письма. В присланных решениях должно содержаться следующее:

Требования к программам: программы могут быть написаны на любом из существующих процедурных компилируемых языков программирования под любую свободно-распространяемую операционную систему для PC или под Miscrosoft Windows. Исходный текст программы должен быть хорошо отформатирован и откомментирован. Запрещается использовать внешние библиотеки, не входящие в состав поставки компилятора, а также библиотеки компилятора, предназначенные специально для решения поставленной перед вами задачи. Очень приветствуется переносимость написанной программы на другие компиляторы/платформы.

Важное замечание: не обязательно делать обе программы. Если вы сделали только одну, или даже половину программы — присылайте получившееся нам, мы разберемся.

Очный тур будет проходить на территории РНЦ «Курчатовский Институт» в конце февраля 2010 года. Участники, допущенные до очного тура, будут извещены об этом по электронному адресу, с которого было отослано решение. Также, список участников будет опубликован на этой странице после окончания заочного тура.

Победители и лауреаты будут награждены ценными призами и красивыми грамотами.

Заочный тур

Задача: кубик Рубика

Существует всем известная головоломка, популярная во всех странах мира, вне зависимости от вероисповедания и национальной принадлежности, изобретенная венгерским скульптором Рубиком. Популярность этой головоломки такова, что были придуманы ее различные вариации, кроме стандартно 3x3, существует даже вариант с элементами не стандартной квадратной формы, а состоящий из прямоугольников разных размеров. Кубик собирают на время, а самые быстрые попадают в книгу рекордов Гинеса. Есть даже научные исследования и публикации по сборке кубика. Проводится научный поиск и доказательство минимального количества шагов, за который кубик может быть собран из любой начальной комбинации.

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

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

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

Исходные данные должны вводится из файла, в текстовом виде.

Результат (или серия, результатов) выводится в другой текстовый файл. Визуализация и графический интерфейс приветствуются, но не являются обязательными. Возможность задания дополнительных ограничений на просчитываемую программой схему на усмотрения автора, но оригинальное решение может существенно поднять балы за выполненное задания. Так как получившиеся обозначения и форматы ввода данных могу различатся, они должны быть четко задокументированны. Так же должен быть предоставлен тестовый набор входных данных, строящий схему.

И последнее важное замечание. Задание предполагает создание инструмента для построения произвольных схем, возможно новых и не обязательно совпадающих с теми, что указаны в приведенных ссылках.

Задача: Анализатор текстов на языке Си.

Необходимо реализовать анализатор текстов, написанных на языке Си. Предполагается что тексты состоят из трех типов "лексем": комментарии, строки и текст.

комментарий
Бывает двух видов: однострочные и многострочные. Однострочный начинается в любом месте с двух слешей ('//') и заканчивается с окончанием строки в которой он появился. Многострочный начинается с символов '/*' и заканчивается первым появлением символов '*/''/*' (была опечатка).
строки
Строки, это последовательность символов заключенная между парой двойных ковычек.Сами двойные ковычки могут встретиться в строке если перед ковычкой стоит обратный слеш ('\'). Но будте осторожны, сам слеш может появлятся в тексте как два слеша подряд. Т.е. '\"' - это двойная ковычка, а '\\' слеш. Последовательности, вроде, '\\\\\\\"' тоже имеют право на жизнь.
текст
Все остальное.

И все было бы просто, но синтаксисом наличие конструкций, похожих на текст в комментариях, а похожих на комментарии в тексте не запрещено.

И так, программа должна принемать входные данные в виде файла на языке Си. На выходе должен образовываться файл в XML-подобном виде:
<file name="имя входного файла">
<text>какой-то кусок программы, в котором угловые скобки заменены при выводе на их экевиваленты:
'<' - &lt;
'>' - &gt; </text>
<string> какая-то строка </string>
<text>еще какой-то текст </text>
<comment>комментарий </comment>
<text>еще какой-то текст </text>
</file>

Для примера, теги были выведены с начала строки, но для реальной программы лексемы не обязаны начинаться с начала строки, и файл выдачи должен повторять структуры исходной программы по переводам строки.

Удачи!