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

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

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

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

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

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

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

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

Заочный тур

Задача: составитель аппликатуры для шестиструнной гитары

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

На вход программе подается мелодия в специальном формате. На выходе программа формирует табулатуры с аппликатурой. При составлении аппликатурной сетки программа должна

Однако, если стоит выбор между большим количеством межпозиционных переходов внутри тактов и большим количеством переходов на границах тактов, то следует выбирать последнее.

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

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

Входной формат

Для этой задачи был разработан специальный формат входных данных, являющийся достаточно вольной вариацией формата LilyPond.

Далее при описании синтаксиса будут применяться следующие обозначения:

Пример: «{The | A} [good] task» означает, что первым из слов должно быть либо «The», либо «A», за ним может следовать необязательное слово «good», и далее обязательно должно быть слово «task».

Первая строка входного файла — это описание тональности и размера. Формат строки note {major | minor} length/length. Note — это латинские буквы, соответствующие нотам: «a» —ля, «b» —си, «c» —до, «d» —ре, «e» —ми, «f» —фа, «g» —соль. Также после имени ноты (без пробела) могут располагаться суффиксы «is» и «es», соответствующие знакам «диез» и «бемоль».

«length» — это длительность, выраженная в долях единицы: 1  —целая, 2  —половинка, 4  —четверть, 8  —восьмая, 16  —шестнадцатая, 32  —тридцать вторая. За данными числами может следовать символ «.» (точка), что означает относительное увеличение длительности на половину: «4.» — это четверть с точкой, которой не хватает еще одной восьмой до половинной длительности.

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

Формат отдельной ноты таков: {note}[length]. Если при данной ноте не указана ее длительность, то она (длительность) наследуется от предыдущей ноты. Если у самой первой из нот не указана длительность, то она предполагается равной одной четверти.

Аккорды — это несколько нот, разделенных пробельными символами и заключенных в угловые скобки (<>). Сразу после аккорда (без пробела) может следовательность длительность этого аккорда, внутри аккорда длительности не указываются. Пример: <c e g>1 — это тоническое трезвучие (или одно из его обращений) для тональности до-мажор; длительность этого аккорда — целая нота.

Паузы имеют тот же формат, что и ноты, только вместо символа ноты стоит символ «R».

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

Такая схема, естественно, не охватывает всего многообразия нот, поэтому существуют символы повышения и понижения текущей ноты на октаву: «'» и «,» соответственно. Символы следуют сразу за спецификацией ноты, без пробелов. Повышение/понижение производится относительно текущего вычисленного значения ноты и, естественным образом, влияет на все последующие ноты. Если нужно повысить или понизить ноту сразу на несколько октав, символы повышения/понижения указываются несколько раз подряд (без пробелов между ними). Пример: последовательность «c'2 fis c ges» имеет следующую нотную запись

Задача: программа-подспорье для начинающего преподавателя информатики у нерадивых учеников

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

Ваша задача — написать программу, которая будет сравнивать два исходных текста на языке C не обращая внимание на добавленные/убранные/измененные комментарии и переименование переменных.

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

int i = 0;
for (i = 0; i < 10; i++) {
	printf("%d\n", i);
}
и
int var = 0;
for (var = 0; var < 10; var++) {
	printf("%d\n", var);
}

В более сложном варианте программа должна распознавать и случаи «переброса переменных»:

int i = 0, j = 0;
while (i < 10) {
	j = i * i;
	printf("%d:\t%d\n", i, j);
	i++;
}
и
int square = 0, num = 0;
while (num < 10) {
	square = num * num;
	printf("%d:\t%d\n", num, square);
	num++;
}