Раскрыть

Результаты очной олимпиады по программированию среди студентов, проходившей в ШГПИ 15-16 марта студенческого форума «Актуальные проблемы прикладной информатики, математики и методики обучения информатике и математике» .

Анонc студенческого форума | Обсуждение олимпиады

По результатам проверки решений задач призовые места были распределены следующим образом:

1 место. Кочарин Александр Евгеньевич (КГУ)
2 место. Бубнов Никита Александрович (КГУ)
3 место. Бельков Денис Михайлович (ШГПИ)
3 место. Городецкий Сергей Владимирович (ЧГПУ)

Поздравляем победителей олимпиады!

Вручение победителям почетных грамот и призов состоится 16 марта 2012 года на факультете информатики, математики и физики ШГПИ, при подведении итогов студенческого форума.

Задания для студенческой олимпиады по программированию.
ШГПИ, 15-16 марта 2012 г.

Вниманию участников предлагаются 3 задачи. За полное решение всех задач участник может набрать 23 балла (5+8+10). Жюри будет проверять решения участников на заранее подготовленных тестах, которые по окончании проверки решений будут выложены на веб-форуме ШГПИ, в разделе Обсуждение олимпиады, а также с помощью программы-тестера (задача №3).

1. Поиск строки (5 баллов)

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

Задание

Дана строка и текст. Найти все вхождения строки в этот текст. Поиск осуществляется с пропуском конца строки, как если бы весь текст представлял собой одну большую строку. Например, для строки aaa в тексте

abca
aaab
caav

имеется два вхождения.

Ограничения

Искомая строка не превышает длиной 10000 символов.
Максимальная длина строки текста 1000 символов.
Искомая строка и текст могут состоять из пробелов, знаков препинания, символов латиницы.
В тексте могут быть пустые строки.
Объем исходного текста - не ограничен
Максимальное время работы программы - 1c на обработку каждых 10000 совпадений, 1с на обработку каждых 50Мб исходного файла

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

Входной файл input.txt.
Первая строка файла представляет собой искомую строку. Последующие строки – строки текста, где ищется эта строка.

Выходной файл output.txt.
Выходной файл содержит координаты вхождения - номер строки и номер символа в строке текста, откуда начинается вхождение, либо сообщение (см. ниже). Если вхождений не найдено, то файл output.txt содержит строку no found. Счет строк и символов в строке начинается с 0.
Если вхождений не найдено, то файл output.txt строку no found.
Если искомая строка пуста, то выдается сообщение null string.
Если отсутствует текст, то выдается сообщение no text.

Примеры

input.txt	output.txt
vov vo vdfg,3vov.dsadasdasdasdvovv ovdasfasdfdsafffffff vo vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv fgvov	0 0 1 6 1 23 1 26 5 0 7 2

input.txt	output.txt
dfadsf	no text

input.txt	output.txt
abc a b cab ca bcab ca bcabca bc	0 0 2 1 3 1 4 2 5 1 6 2 6 5

2. Путешествие муравьишки (8 баллов)

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

Фабула

В детстве я любил наблюдать за муравьями… Осень, дождь. Маленький муравьишка пробирается в свой муравейник. Перед ним большая лужа. От ветра в нее нападали ветки деревьев. Перебираясь с ветки на ветку, муравей преодолевает препятствие и до темноты успевает попасть в свой дом.

Задание

Представим себе, что на плоскости случайным образом проведено множество отрезков. Некоторые отрезки пересекаются, образуя запутанный лабиринт. Вам, необходимо двигаясь по этим отрезкам, переходя от одного отрезка к другому, по точкам пересечения найти наиболее короткий путь (один из наиболее коротких) от отрезка A к отрезку B. Каждый шаг – это переход от одного отрезка к другому.

Ограничения

Отрезки располагаются в квадрате 10 на 10. Левый нижний угол квадрата расположен в начале координат.
Положение отрезка определяется четырьмя координатами его концов: x1,y1,x2,y2. Примем, что координаты концов могут быть только целыми числами, при этом координаты точек пересечения в общем случае таковыми не являются.
Два отрезка, расположенных на одной линии, в независимости от того, перекрываются они или нет, считаются различными, даже если один из отрезков полностью помещается в другом. В частности два и более отрезка могут совпадать – они все равно должны считаться разными.
Максимальное количество пересечений одного отрезка с другими равно 3.
Пункт 4 работает и в том случае, если отрезки перекрываются.
Максимальное количество отрезков - 1000.
Максимальное время работы программы - 1с.

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

Структура входного файла (input.txt)

Входной файл состоит из строк. Каждая строка содержит координаты одного отрезка, отделенные друг от друга произвольным количеством пробелов. В начале и конце строки также может стоять произвольное количество пробелов.
Принято следующее правило: в начале записываются координаты левого конца отрезка, потом правого (x2>x1). В случае, если x1==x2 – порядок записи не важен.
Последние две строки содержат координаты отрезка A и отрезка B в том же формате, что и координаты остальных. Координаты отрезков A и B также содержаться и в общем списке (первые n строк). Другими словами, если количество отрезков равно n, то количество значимых строк в файле input.txt равно n+2.

Структура выходного файла (output.txt)

Файл output.txt содержит информацию о кратчайшем пути от отрезка A до отрезка B.
Первая строка содержит число прошедших отрезков, включая первый и последний (N).
Следующие N строк файла содержат информацию об отрезках, которые надо пройти – координаты концов отрезка в том же формате, что и в исходном файле (input.txt). Координаты отрезков A и B включаются в этот список.
Далее идут N-1 строк, содержащих координаты точек пересечения отрезков, через которые проходит искомый путь (два вещественных числа через пробелы) – по одной точке пересечения на строку. Как легко догадаться, количество точек пересечения должно быть на единицу меньше (N-1), чем количество пройденных отрезков.

Сообщения программы

Программа выдает вместо результата сообщение, если путь, по какой либо причине не может быть найден.
Если путь между отрезками не найден (нет последовательности шагов, чтобы пройти от одного отрезка к другому), то программа выдает сообщение No pass.
Специальный случай, когда входной файл состоит из трех одинаковых строк (три одинаковых отрезка), также приводит к сообщению No pass.
В случае, если структура файла не соответствует тому, что было описано выше, программа выдает сообщение Bad data. Перечислим ситуации, на которые программа должна среагировать именно так:

Координаты отрезков не попадают в интервал от 0 до 9.
Не удалось считать координаты отрезков – не хватило данных (количество чисел не делится на 4, в строке посторонние символы).
Не выполняется условие x2>=x1.
Количество строк меньше 3.
Отрезки A или B отсутствуют в списке.

Если количество пересечений для одного отрезка превосходит 3, то программа выдает сообщение Too many intersections.

Примеры

input.txt	output.txt
0 0 4 4 0 3 3 0 1 5 4 2 0 3 4 7 3 8 5 6 0 0 4 4 3 8 5 6	4 0 0 4 4 0 3 3 0 0 3 4 7 3 8 5 6 1.500000 1.500000 0.000000 3.000000 4.000000 7.000000

input.txt	output.txt
0 0 9 9 2 0 6 9 0 0 9 9 2 0 6 9	2 0 0 9 9 2 0 6 9 3.600000 3.600000

input.txt

output.txt

6
0 0 5 0 
0 0 3 3 
1 2 7 2 
6 0 6 3 
5 1 9 1 
8 0 8 3 
0.000000 0.000000 
2.000000 2.000000 
6.000000 2.000000 
6.000000 1.000000 
8.000000 1.000000

3. По росту становись! (10 баллов)

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

Фабула

Простая задача - построить по росту отделение. Каждый знает свое место, быстро и четко его занимает по команде "Отделение, в одну шеренгу — СТАНОВИСЬ!".
... Для сержанта учебки это не более чем сладкий сон. Ведь строить ему - не солдат, а толпу новобранцев ...

Задание

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

Требования

Единственное допустимое действие - обмен местами двух рядом стоящих солдат, если они стоят не по росту.
На каждом шаге разрешено выполнять несколько одновременных обменов.
Пересечение пар при одновременном обмене - недопустимо.
Максимальное количество одновременных обменов - ограничено (см. input.txt).
Количество шагов должно быть минимальным при использовании максимального количества одновременных обменов. Исключением является ситуация, когда вычисленное общее количество обменов не кратно максимальному количеству одновременных обменов. Например, при вычисленном общем количестве обменов=20 и максимальном количестве одновременных обменов=3, допускается формирование 6 шагов по 3 одновременных обмена и 1 шага по 2 одновременных обмена.
Максимальное время работы программы - 1 секунда.

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

Структура входного файла (input.txt)
Первая строка содержит максимальное количество одновременных обменов на каждом шаге (см. п.4 Требований).
Вторая и последующие строки содержат рост солдат в сантиметрах (натуральные значения). Количество солдат в отделении - от 3 до 12.

Структура выходного файла (output.txt)
Каждая строка выходного файла содержит отсортированный по возрастанию порядковых номеров список одновременных обменов (через пробел) на очередном шаге.
Обмен идентифицируется порядковым номером первого солдата в паре. Например, если местами обмениваются солдаты с порядковыми номерами 3 и 4, то обмен будет идентифицирован числом 3.
Если невозможно выполнить п.5 Требований, то вместо набора шагов в первой строке выводится слово error, во второй - минимально возможное количество шагов в соответствии с п.5 Требований.