Анонc студенческого форума
Обсуждение олимпиады
Начало олимпиады 19.02.2011 года в 14 ч. (12.00 Москвы).
Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp_shgpi@list.ru) до 14 ч. 20.02.2011 г.
Файл с исходным текстом программы должен начинаться с головного комментария, содержащего следующую информацию: номер решаемой задачи, фамилию, имя и отчество автора решения, курс, наименование вуза и факультета, город, а также контактные данные (e-mail, по желанию - телефон, почтовый адрес).
Итоги олимпиады будут подведены до 1 марта 2011 г и опубликованы на сайте. Дополнительно, при участии в очной олимпиаде в рамках конференции победители заочной олимпиады получают 10% бонус по очкам.
Вниманию участников предлагаются 4 задачи. За полное решение всех задач участник может набрать 25 баллов (4+4+7+10). Жюри будет проверять решения участников на заранее подготовленных тестах, которые по окончании проверки решений будут выложены на веб-портале ШГПИ shgpi.edu.ru.
1. Похожие строки (4 балла)Автор: Пирогов В.Ю. ЗаданиеПусть имеются две последовательности символов s1 и s2. Пусть длины этих последовательностей соответственно равны L1 и L2. Назовем эти последовательности похожими, если величина k=(2*L)/(L1+L2) >=0.75. В формуле L – длина максимальной подпоследовательности, содержащейся как в последовательности s1, так и в последовательности s2.На входе даны: последовательность s1 и множество последовательностей s2. На выходе необходимо получить все последовательности s2, похожие на последовательность s1. Требование к последовательностям.
Форматы данныхИсходный файл input.txt. В первой строке файла input.txt содержится последовательность s1. В последующих строках - последовательности s2 (по одной на строку). Результирующий файл output.txt. Каждая строка output.txt состоит из трех частей: значение s1, значение s2, значение k. Части отделены друг от друга пробелами. Количество строк во входном файле не ограничено. Примеры
|
2. Байт-бильярд (4 балла)Автор: Слинкин Д.А. ЗаданиеРассмотрим осевой удар одного бильярдного шара по набору других шаров, расположенных на одной оси рядом или на некотором расстоянии друг от друга. В идеальной ситуации каждый шар передает свой импульс последующему, сам оставаясь на месте удара (эффект эстафеты). Даны две последовательности из числовых значений байтового диапазона (от 0 до 255, 8 бит). Представим каждый единичный бит числа бильярдным шаром, а нулевой - пустым пространством. Каждое последующее значение второй последовательности "падает сверху" на первую последовательность, обеспечивая одновременный удар восемью битами с эффектом эстафеты, перераспределяя биты между байтами и, возможно, выбивая за пределы первой последовательности некоторые биты из первого байта первой последовательности. Таким образом, "падение" каждого нового байта не только добавляет модифицированный байт к первой последовательности, но и, возможно, изменяет другие ее значения. Интересным побочным эффектом данного процесса является то, что "выбитый" байт всегда равен "упавшему сверху". Задача заключается в нахождении результирующего набора байтов, который формируется последовательным применением всех байтов второго набора к первому. Например, пусть первая последовательность содержит значения 9,226,17, а вторая - 7, 254. Применяем 7 к 9,226,17 (7 "роняем" сверху на 17,226,9), получаем 8,225,18,1. Теперь применяем 254 к 8,225,18,1, получаем 0,9,224,19,0. Ответ: 0,9,224,19,0. Форматы данныхФайл input.txt содержит две строки. В каждой строке содержится набор байтовых значений, отделенных друг от друга пробелом. Количество значений - неограниченно. Файл output.txt содержит строку байтовых значений - результат последовательного применения эффекта эстафеты к первой строке значениями второй строки исходного файла.
Примеры
|
3. Крестики-нолики (7 баллов)Автор: Пирогов В.Ю. ЗаданиеРассмотрим следующее обобщение игры в крестики-нолики.
В задаче примем, что начинают всегда крестики. Форматы данных
Входной файл input.txt содержит строку вида Выходной файл output.txt должен содержать все возможные варианты игры в которых выигрывают нолики. Каждый вариант игры содержится в отдельной строке. Ход обозначается (X,Y,P), где X,Y - координаты, P принимает значение 1 - "крестик", 0 - "нолик". Если вариантов выигрыша нет, то выходной файл должен содержать слово empty. Порядок выводимых строк неважен, но программа должна выдавать строки точно в указанном формате, так как для проверки будет использоваться программа автоматического сравнения текстовых файлов. ПримерыПример 1.
Пример 2
Пример 3
Пример 4.
|
4. Невезучий спелеолог (10 баллов)Автор: Слинкин Д.А. ФабулаЕсли не везет - то во всем. Туристическая прогулка начинающего спелеолога превратилась в жестокий квест. Уже трое суток блуждаю по пещерному лабиринту и, судя по ощущениям, поднимаюсь все выше и выше. Практически сели батареи в фонаре, еда кончилась два дня назад, но больше всего мучает жажда... Что это за звуки? Похоже на капли воды... бегу туда ... ДА! На низком (рукой достать) потолке пещеры медленно набухают и падают вниз капли. Судя по отсутствию сталактитов и сталагмитов вода здесь появилась совсем недавно. Удар геологическим молотком по потолку, брызги мокрого камня и вожделенная струйка льется в пересохший рот... уже не струйка... уже поток... треск камня, рев воды... что я наделал!! Волна оглушает и несет меня вниз, то практически затухая, то сбивая с ног... В голове мелькают картинки туристического буклета: "... незабываемый отдых на берегу высокогорного озера ...". Что-ж, если мне повезет выжить, то для "незабываемого отдыха" на гору уже не надо будет подниматься. А если не повезет... может тогда новое озеро у подножия горы назовут именем его создателя - моим именем... ЗаданиеДана квадратная матрица-лабиринт, заполненная нулями и единицами. Будем считать, что каждая ячейка матрицы является пространственным кубом. Нулем описывается свободный куб (проход, вход-выход), единицей - заполненный (стена, пол, потолок). В нижней, левой и правой частях матрицы имеется произвольное количество входов-выходов. В верхней части матрицы имеется единственный вход-выход, куда заливается вода. Для простоты будем считать, что вода заливается порциями, объем каждой порции равен объему одной ячейки матрицы, и новая порция не заливается, пока предыдущая полностью не распределится по лабиринту под действием гравитации. Распределение воды допускается только по горизонтали и вертикали. Задача заключается в определении минимально необходимого количества порций воды, которое требуется залить в матрицу-лабиринт для появления воды на любом из выходов лабиринта. Форматы данныхФайл input.txt содержит набор строк, описывающий квадратную матрицу-лабиринт. Каждая строка состоит только из символов 0 и 1. Количество символов первой строки определяет общее количество строк. Первая строка содержит единственный ноль - точку, с которой начинается заполнение лабиринта водой. Файл output.txt содержит единственное число - минимально необходимое количество порций воды, которое требуется залить в матрицу-лабиринт для появления воды на любом из выходов лабиринта.
Примеры
|