Задания для заочной студенческой олимпиады по программированию.
ШГПИ, 19-20 февраля 2011 г.

Анон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.

Требование к последовательностям.

  1. Последовательности состоят только из символов латинского алфавита. Нарушение этого требования для строки s1 должно приводить к сообщению об ошибке: «Where is the first word?» , если строка пустая (состоит только из пробелов), «The first word is incorrect?» – в остальных случаях. Нарушение этого правила для последовательностей s2 должно приводить к игнорированию такой последовательности.
  2. Перед началом последовательности и в конце ее может стоять произвольное количество управляющих символов: пробелов, символов табуляции и т.п.
  3. Заглавные и прописные буквы латинского алфавита не различаются (‘a’=’A’ и т.п.).

Форматы данных

Исходный файл input.txt.

В первой строке файла input.txt содержится последовательность s1. В последующих строках - последовательности s2 (по одной на строку).

Результирующий файл output.txt.

Каждая строка output.txt состоит из трех частей: значение s1, значение s2, значение k. Части отделены друг от друга пробелами.

Количество строк во входном файле не ограничено.

Примеры

input.txtoutput.txt
aaabcd
   aaabc
aaa

aaabcd
aabcd
daaabcduu
ddaaabcduu
aaabc d
aaabcd aaabc   0.9091
aaabcd aaabcd   1.0000
aaabcd aabcd   0.9091
aaabcd daaabcduu   0.8000
aaabcd ddaaabcduu   0.7500
input.txtoutput.txt
AbCd
abcd
AbCd abcd   1.0000 

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 содержит строку байтовых значений - результат последовательного применения эффекта эстафеты к первой строке значениями второй строки исходного файла.

Примеры

input.txtoutput.txt
9 226 17
7 254
0 9 224 19 0
input.txtoutput.txt
1 2 4 8 16
32 64 128
1 2 4 8 16 0 0 0
input.txtoutput.txt
1 2 4 8
8 12 14 15
0 1 0 2 0 4 0 8

3. Крестики-нолики (7 баллов)

Автор: Пирогов В.Ю.

Задание

Рассмотрим следующее обобщение игры в крестики-нолики.

  1. Игра производится в квадрате N на N клеток. Для задачи N<=3 и N>=2.
  2. Игра заканчивается
    а) когда заканчиваются свободные клетки
    б) когда крестики или нолики выстаиваются по вертикали, горизонтали или диагонали в отрезок длиной не меньше M. При этом M<=N и M>=2.

В задаче примем, что начинают всегда крестики.

Форматы данных

Входной файл input.txt содержит строку вида
N X Y M
где X, Y - координаты первого крестика. Примем также, X>=0, X<N, Y>=0, Y<N.

Выходной файл output.txt должен содержать все возможные варианты игры в которых выигрывают нолики. Каждый вариант игры содержится в отдельной строке. Ход обозначается (X,Y,P), где X,Y - координаты, P принимает значение 1 - "крестик", 0 - "нолик". Если вариантов выигрыша нет, то выходной файл должен содержать слово empty. Порядок выводимых строк неважен, но программа должна выдавать строки точно в указанном формате, так как для проверки будет использоваться программа автоматического сравнения текстовых файлов.

Примеры

Пример 1.

input.txtoutput.txt
2 0 0 2
empty

Пример 2

input.txtoutput.txt
3  0  0  2
...
(0,0,1)(2,2,0)(2,0,1)(0,1,0)(0,2,1)(1,0,0)
...
+ 0
0  
+0+
Выходной файл содержит 492 строки.
Выше приведен пример одной из них.
Слева приведено конечное положение для этого варианта (выиграли нолики)
Скачать файл output.txt (18Kb)

Пример 3

input.txtoutput.txt
3  0  0  3
...
(0,0,1)(0,1,0)(0,2,1)(1,1,0)(1,0,1)(2,1,0)
...
+  
000
++ 
Выходной файл содержит 7896 строк.
Выше приведен пример одной из них.
Слева приведено конечное положение для этого варианта (выиграли нолики)
Скачать файл output.txt (431Kb)

Пример 4.

input.txtoutput.txt
3 1 2 3
...
(1,2,1)(2,2,0)(0,2,1)(1,1,0)(0,1,1)(0,0,0)
...
++0
 0 
0+ 
Выходной файл содержит 10176 строк.
Выше приведен пример одной из них.
Слева приведено конечное положение для этого варианта (выиграли нолики)
Скачать файл output.txt (557Kb)

4. Невезучий спелеолог (10 баллов)

Автор: Слинкин Д.А.

Фабула

Если не везет - то во всем. Туристическая прогулка начинающего спелеолога превратилась в жестокий квест. Уже трое суток блуждаю по пещерному лабиринту и, судя по ощущениям, поднимаюсь все выше и выше. Практически сели батареи в фонаре, еда кончилась два дня назад, но больше всего мучает жажда...

Что это за звуки? Похоже на капли воды... бегу туда ... ДА! На низком (рукой достать) потолке пещеры медленно набухают и падают вниз капли. Судя по отсутствию сталактитов и сталагмитов вода здесь появилась совсем недавно. Удар геологическим молотком по потолку, брызги мокрого камня и вожделенная струйка льется в пересохший рот... уже не струйка... уже поток... треск камня, рев воды... что я наделал!! Волна оглушает и несет меня вниз, то практически затухая, то сбивая с ног... В голове мелькают картинки туристического буклета: "... незабываемый отдых на берегу высокогорного озера ...". Что-ж, если мне повезет выжить, то для "незабываемого отдыха" на гору уже не надо будет подниматься. А если не повезет... может тогда новое озеро у подножия горы назовут именем его создателя - моим именем...

Задание

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

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

Форматы данных

Файл input.txt содержит набор строк, описывающий квадратную матрицу-лабиринт. Каждая строка состоит только из символов 0 и 1. Количество символов первой строки определяет общее количество строк. Первая строка содержит единственный ноль - точку, с которой начинается заполнение лабиринта водой.

Файл output.txt содержит единственное число - минимально необходимое количество порций воды, которое требуется залить в матрицу-лабиринт для появления воды на любом из выходов лабиринта.

Примеры

input.txtoutput.txt
10111
10110
11010
11011
11111
3 
input.txtoutput.txt
111011
100001
111001
111011
100000
111111
1 
input.txtoutput.txt
111011
000000
111011
111000
100011
111111
4 
input.txtoutput.txt
11101111
10101111
10101000
10100011
10000110
11111000
00000000
11100001
9