Задания для заочной студенческой олимпиады по программированию.
ШГПИ, 21-22 февраля 2012 г.
Анонc студенческого форума
Обсуждение олимпиады
Начало олимпиады 21.02.2012 года в 14 ч. (12.00 Москвы).
Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования
и исполняемый файл) будут приниматься по электронной почте
(olimp@shgpi.edu.ru) до 14 ч. 22.02.2012 г.
Файл с исходным текстом программы должен начинаться с головного комментария, содержащего следующую информацию:
номер решаемой задачи, фамилию, имя и отчество автора решения, курс, группу, специальность,
наименование вуза и факультета, город, а также контактные данные (e-mail, по желанию - телефон,
почтовый адрес).
Например:
// задача 1
// Иванов Иван Иванович
// 2 курс, 286 группа, спец. ПОВТ (230105.65 Программное обеспечение вычислительной техники и автоматизированных систем)
// ФГБОУ ВПО Шадринский государственный педагогический институт, г. Шадринск
// email - iii@shgpi.edu.ru
// ...
...
Итоги олимпиады будут подведены до 1 марта 2012 г и опубликованы на форуме и на веб-портале ШГПИ
shgpi.edu.ru. Дополнительно, при участии в очной олимпиаде в рамках конференции, победители заочной олимпиады получают 10% бонус по очкам. Ах да, еще мы награждаем победителей небольшими, но приятными призами ;).
В оргкомитет олимпиады входят два человека: Пирогов Владислав Юрьевич
(к.ф-м. н, профессор, зав. кафедрой Прикладной Информатики и Экономики, ник в
форуме - Vladislav_133) и Слинкин Дмитрий Анатольевич
(к.п.н, доцент, преподаватель программирования кафедры Программирования и Сетевых Технологий,
зав. Вычислительным Центром ШГПИ, ник в форуме - xdsl).
Оргкомитет олимпиады самостоятельно придумывает и прорешивает олимпиадные задачи. Любые совпадения условий задач нашей олимпиады с олимпиадными задачами всероссийских и международных олимпиад чаще всего случайны. Изредка сторонние олимпиадные задачи берутся за основу при создании наших задач. Для проверки решений мы обычно формируем набор тестов, которые публикуем по окончании олимпиады.
Получить доступ к условиям задач олимпиад прошлых лет (2006-2011 годов) и попробовать свои силы в их решении можно с помощью системы эталонных решений Solver
(http://shgpi.edu.ru/solver/).
Анонсы, обсуждения, тесты, решения заочных олимпиад прошлых лет доступны здесь:
2009 год (https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=46),
2010 год (https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=184),
2011 год (https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=502)
Вниманию участников предлагаются 4 задачи. За полное решение всех задач участник
может набрать 22 балла (4+6+(8+1)+3). Жюри будет проверять решения участников
на заранее подготовленных тестах, которые по окончании проверки решений будут
выложены на веб-форуме ШГПИ, в разделе Обсуждение олимпиады.
|
1. Пандемия (4 балла)
Автор: Слинкин Д.А.
Фабула
2013 год. Разрушительный полиморфный вирус начал свое победное шествие
по глобальной сети. Ни единой стабильной сигнатуры, произвольные самомодификации,
знание нюансов большинства операционных систем, маскировка под известные программы и сервисы, заражение
при первом сетевом контакте и все более развивающийся искусственный интеллект сделали его поистине чумой 21 века.
Все антивирусные
системы оказались бессильными. Парализация работы банковских и поисковых систем,
систем управления предприятиями и транспортом,
пользовательских десктопов, планшетов и смартфонов поставила под угрозу все
существование нашей техногенной цивилизации.
И только ты способен остановить эту чуму. Ты выловил и изолировал один из первых его прототипов. Ты модернизировал
его, приручил и сделал охотником на своих собратьев. Время пришло, выводи его в сеть ...
Задание
Вирус и антивирус стартуют с разных систем. Механизмы их работы идентичны, но поведение различно. При передаче
данных от одной машины другой вирус и антивирус пытаются заразить целевую систему. Вирус не может заразить систему,
которую уже захватил антивирус. Антивирус заражает любую систему и уничтожает найденный в ней вирус. Задание заключается
в определении момента купирования или уничтожения пандемии, т.е. когда запланированные коммуникации между
системами не изменят количество зараженных систем.
Форматы данных
Каждая компьютерная система идентифицируются строчной буквой латиницы.
Файл input.txt в первой строке содержит идентификаторы систем, с которых стартуют вирус и, соответственно, антивирус.
В последующих строках - факты однонаправленных коммуникаций между системами в виде идентификаторов двух систем
в каждой строке (передача данных - слева направо). Пары идентификаторов пишутся слитно.
Файл output.txt содержит 4 строки.
В первой - номер строки (нумерация с 0) файла input.txt, в которой находится
последняя коммуникация между системами, после которой можно говорить о купировании
или уничтожении пандемии.
Во второй - список имен незараженных систем (слитно, в алфавитном порядке)
на момент окончания обработки исходного файла.
В третьей - список имен зараженных вирусом систем (слитно, в алфавитном порядке)
на момент окончания обработки исходного файла.
В четвертой - список имен зараженных антивирусом систем (слитно, в алфавитном порядке)
на момент окончания обработки исходного файла.
Примеры
| input.txt | output.txt |
|---|
za
ab
ba
cd
ab
ze
de
ea
ef
ad
fa
|
8
c
efz
abd
|
|
| input.txt | output.txt |
|---|
za
ab
bc
za
zb
cf
xz
|
0
x
z
abcf
|
|
|
|
2. Крипто (6 баллов)
Автор: Слинкин Д.А.
Задание
Закодировать строку текста по следующим правилам:
- "Весом" цифры будем считать основание системы счисления кода (от 2 до 35).
- "Весом" кода будем считать сумму весов всех цифр кода.
- "Вес" получившегося кода должен быть минимально возможным.
- Кодирование производится слева-направо, посимвольно.
- Каждый уникальный символ (байт) строки преобразовывается в уникальный числовой код
в выбранной программистом системе счисления.
Числовой код первого уникального символа строки равен 0, второго - 1,
третьего - 2 и т.д. Например, для строки dcbaabcd код симовола d равен 0,
c - 1, b - 2, a - 3.
- Количество цифр, которым кодируется каждый символ,
одинаково для всех символов строки.
Форматы данных
Исходный файл input.txt содержит строку длиной до 100000 байт,
которая включает в себя любые символы ASCII,
кроме символов перевода строки с кодами 10 и 13
Результирующий файл output.txt содержит один или несколько вариантов закодированной
строки. Количество строк зависит от количества
комбинаций параметров кодирования, обеспечивающих минимальный "вес" кода. Порядок
вывода строк - по возрастанию "веса" цифр.
Примеры
| input.txt | output.txt |
|---|
Privet, Vasja!
|
00000001001000110100010101100111100010011010101110011100
0001020310111213202122232130
|
| input.txt | output.txt |
|---|
ababcdcde
|
010123234
|
|
|
3. Сокровища заколдованного замка (8+1 баллов)
Автор: Пирогов В.Ю.
Фабула
Было это давным-давно, в тридевятом царстве тридевятом государстве. Жил там престарелый граф. Жил одиноко. В молодости граф участвовал во многих военных походах. По слухам в его замке хранилось вывезенное из других стран богатство. Когда настала пора умирать, граф объявил, что в замке его хранится несметное сокровище. Сокровище хранилось в отдельном здании, сверху напоминающем цирк. Внутренняя часть здания состояла из коридоров, стены которых представляли собой окружности, центр которых находился в комнате, где и хранилось сокровище. Между коридорами были пробиты проходы (арки), а сами коридоры в некоторых местах были перегорожены глухими стенами. Граф объявил, что здание это заколдовано и только тот сможет получить сокровище и остаться в живых, кто доберется до него самым кратчайшим путем. С тех пор прошло много лет, многие храбрецы пытались добыть несметные богатства, но увы, никто из них не вернулся из того заколдованного здания.
Задание
Лабиринт представляет собой n (n>=1 and n<=30) концентрических окружностей (стен). Будем считать (для простоты), что радиусы соседних окружностей отличаются на одну и ту же величину. Кроме того окружности разделены на m равных секторов (m>=2 and m<=30). На рисунке 1 представлена окружность, в которой n=3 и m=4. Будем нумеровать окружности от центра от 0 до n-1. Сектора нумеруются от 0 до m-1, направление обхода по часовой стрелке (см. рисунок 1). Положение внутри лабиринта определяется двумя координатами: номером окружности (ближайшей от центра), номером сектора. Например, 2 0, 11 10 и т.д. Положение внутри центральной окружности не зависит от сектора, т.е. координаты 0 0, 0 1, 0 2, 0 3 определяют одно и то же положение – центральную комнату, где хранится сокровище.
Рисунок 1.
В окружностях (стенах) имеются проходы (арки). Не более одного прохода на сектор. Таким образом, можно передвигаться по коридорам между окружностями и переходить между коридорами через арки. Кроме того в коридорах могут быть стены-перегородки. На рисунке 2 проходы обозначены символом ‘равно’, а перегородки символом ‘крестик’. Положение проходов и перегородок также определяется координатами. Для проходов (см. рисунок 2) имеем координаты 2 0, 1 2, 0 0. Координаты перегородок для рисунка 2: 2 1, 1 3.
Рисунок 2.
Написать программу, позволяющую найти кратчайший путь (какой-либо один) извне к центру лабиринта.
Форматы данных и примеры
На входе программы файл, содержащий информацию о лабиринте: первая строка – количество стен (окружностей), вторая строка – количество секторов, третья строка координаты проходов (число через пробел, должно быть четное число чисел), четвертая строка координаты перегородок (число через пробел, должно быть четное число чисел).
Рассмотрим входной файл для лабиринта, представленного на рисунке 2.
Файл input.txt:
3
4
2 0 1 2 0 0
2 1 1 3
Выходной файл (output.txt) должен содержать информацию о количестве шагов, и один
вариант самого короткого пути до центра. Для данного случая результат будет следующий.
Файл output.txt:
7
2 0;2 3;2 2;1 2;1 1;1 0;0 0;
Спецификация программы
- Если программой не найден ни один путь к центру, то на выход должно выдаваться сообщение No pass!.
- Внешняя стена может содержать несколько арок, как и другие стены. Это означает, что путь может начинать по проходу любой из этих арок.
- Структура файл input.txt.
- Между элементами в строках может стоять произвольное количество пробелов и знаков табуляции. Произвольное количество пробелов и знаков табуляции может стоять в начале и конце строки.
- Третья пустая строка означает отсутствие арок в лабиринте и должна правильно обрабатываться (сообщение No pass!).
- Четвертая пустая строка означает отсутствие перегородок в лабиринте.
- Список координат проходов и перегородок может содержать повторяющиеся значения. В этом случае программа должна игнорировать дубли.
- Случаи, вызывающие сообщение об ошибке (Error!).
- Отсутствие информации о количестве стен и секторов должно вызывать сообщение об ошибке.
- Наличие в строке не цифровых символов, кроме управляющих символов и пробелов должно вызывать сообщение об ошибке.
- Наличие нескольких (больше одного) чисел в первой и второй строке должно вызывать сообщение об ошибке.
- Не попадание числа стен и секторов в указанные ранее интервалы должно вызывать сообщение об ошибке.
- Указание не существующих координат для арок и перегородок должно вызывать сообщение об ошибке.
- Не четное количество чисел в третьей и четвертой строке должно вызывать сообщение об ошибке.
Дополнительное задание
Ваша программа может быть улучшена, за что вы получите дополнительно 1 балл. Улучшение будет заключаться в том, чтобы выдавать во второй и последующих строках выходного файла все возможные пути к центральной комнате. В первой строке по-прежнему должно стоять количество шагов в кратчайшем пути до центральной комнаты.
|
|
4. Странное законодательство (3 балла)
Автор: Пирогов В.Ю.
Фабула
В некотором маленьком островном государстве Акирема был принят закон о политических партиях. По этому закону один человек не может состоять более чем в одной партии. Партии, члены которых состоят в других партиях, не должны регистрироваться.
Была объявлена перерегистрация партий. В центризбирком были поданы списки членов партий. Списки подавались в закодированном виде. Каждому гражданину было заранее присвоено некоторое кодовое положительное число. Подобный код был присвоен и партии. Таким образом, в списках были лишь числа. Первым шло число – код гражданина, вторым – код партии. Списки составлялись не аккуратно, так что числа располагались произвольно, например, так
2 20 2010 5
10
1 67
3
Впрочем, строго соблюдалось очевидное правило: количество чисел в списках было четным. Глава центризбиркома был заядлый программист. Он быстро написал программу, которая выявила партии, не подлежащие регистрации.
Задание
Выявить партии, не подлежащие регистрации.
Форматы данных
Примем, что количество совершеннолетних граждан Акиремы не превышает 30000, а количество партий по законодательству ограничено 100.
Исходный файл input.txt содержит пары подряд идущих чисел,
первое из которых - код человека, второе - код партии.
Числа друг от друга отделяются произвольным количеством пробелов и переводов строк.
Результирующий файл output.txt содержит список партий, подлежащих регистрации.
Примеры
| input.txt | output.txt |
|---|
1
1 2 2
3 3 4 4
5
5 1 4
|
2 3 5
|
|