Олимпиада по программированию в ШГПИ
18 марта 2009 года, 11.00-16.00, ауд. 219А

В рамках всероссийского студенческого научно-практического форума «Актуальные проблемы прикладной информатики и методики обучения информатики» проводится олимпиада по программированию для студентов вузов.

В процессе работы студент имеет возможность использовать веб-ориентированную систему Solver для проверки правильности своих собственных решений.

Доступ к веб-ориентированной системе Solver расположен по адресу: http://contests.shgpi

Предупреждение: использование веб-ориентированной системы Solver не является обязательным и позиционируется как вспомогательное.

Документация: студент имеет право пользоваться документацией, расположенной по адресу http://vc.shgpi/doc.html

Правила проведения олимпиады по программированию

Олимпиада по программированию проводится 18 марта 2009 года с 11.00 до 16.00 в аудитории 219А. С 11.00 до 11.30 студенты имеют возможность подготовить своё рабочее место, проверить наличие и корректную работу компиляторов, интерпретаторов и сред программирования. При возникновении проблем или пожеланий просьба обращаться к комитету олимпиады.

Подготовка олимпиадных заданий и проверка решений возлагаются на комитет олимпиады, в состав которого входят Пирогов В.Ю., к.ф-м.н, профессор, зав. кафедрой прикладной информатики Шадринского пединститута и Слинкин Д.А., к.п.н, доцент, начальник вычислительного центра Шадринского пединститута.

Комитет олимпиады оставляет за собой право поощрять (до +3 баллов) высокоэффективные решения.

Для решения задач каждый студент может использовать языки программирования Pascal (FreePascal, TurboPascal, Delphi), C++ (GCC, BCPP, Visual C++, C++Builder), PHP5 (Linux, консоль), JavaScript (версия 1.5, firefox, ввод-вывод данных ч/з элемент textarea).

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

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

Для Windows:

c:\ivanov\1\решение задачи 1
c:\ivanov\2\решение задачи 2
c:\ivanov\5\решение задачи 5

Для Linux:

/home/student/ivanov/1/решение задачи 1
/home/student/ivanov/2/решение задачи 2
/home/student/ivanov/5/решение задачи 5

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

Подведение предварительных итогов олимпиады запланировано на 19 марта 2009 года, 9.00. Информация о предварительных результатах будет опубликована в аудитории 219А, а также на интернет-форуме ШГПИ (https://shgpi.edu.ru/forum).

С 10.00 до 11.00 19 марта 2009 года каждый студент может подать апелляцию оргкомитету олимпиады. При возникновении разногласий между студентом и оргкомитетом олимпиады, суть претензий студента и спорный программный код будут выложены для общего обсуждения на интернет-форум ШГПИ.

С 11.00 до 12.00 19 марта 2009 года оргкомитет олимпиады вынесет решения по апелляционным требованиями и опубликует окончательные итоги олимпиады в аудитории 219А, на интернет-форуме и веб-портале ШГПИ (http://shgpi.edu.ru).

С 12.00 до 13.00 19 марта 2009 года — разбор решений олимпиадных задач.

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

Олимпиада по программированию в ШГПИ
18 марта 2009 года, 11.00-16.00, ауд. 219А

Правила формирования исходных файлов данных

Определения.

Под разделителями будем понимать пробелы (код символа 32) и табуляции (код символа 9).

Под переводом строки будем понимать либо последовательность из двух символов с кодами 13 и 10, либо единственный символ с кодом 10, либо конец исходного файла.

Под строкой будем понимать набор символов (от 0 до произвольного количества), который заканчивается переводом строки.

Под пустой строкой будем понимать строку, которая состоит только из разделителей или вообще не содержит символов.

Правила формирования содержимого исходных файлов.

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

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

Исходный файл может содержать произвольное количество пустых строк, если не сказано иное.

Условия олимпиадных задач.

1. В поисках пиратского клада,
четвертый сезон (8 баллов)

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

Максимальное кол-во баллов: 8

Ты нашел карту! Карту пещеры с сокровищами старого пирата! Это ХОРОШАЯ новость. Но есть и ПЛОХАЯ: у тебя появились конкуренты, у которых нет карты, но есть готовность обойти всю пещеру, заглянуть во все уголки и найти сокровища! А теперь ОЧЕНЬ ПЛОХАЯ НОВОСТЬ - они уже там... Единственный способ опередить конкурентов - проложить кратчайший маршрут от входа пещеры до сундука с сокровищами. К счастью стены пещеры сложены из рыхлого известняка и при необходимости могут быть разрушены. Конечно, это тебя задержит, но если сокровище прямо за стеной, то добраться до него, разрушив стену, выйдет иной раз значительно быстрее, чем блуждание по лабиринту. Итак, задача ясна. В руках кирка и фонарь, за плечами - мешок для сокровищ, осталось наметить путь (а лучше - несколько) и вперёд - к богатству и процветанию!

Дано: исходный файл input.txt, содержащий план пещеры (вид сверху) с отмеченными стенами, точкой входа в пещеру и точкой расположения сундука с сокровищами. Свободный проход обозначается цифрой 0, стена — цифрой 1, точка входа в пещеру - цифрой 2, местоположение сундука с сокровищами - цифрой 3. Будем считать, что точки 2 и 3 соответствуют свободному проходу. Дополнительно, точка 2 всегда находится на границе плана. Первая строка исходного файла содержит одно натуральное значение - количество перемещений по свободным проходам, эквивалентное одному разрушению стены. Каждая последующая строка исходного файла содержит набор цифр (0, 1, 2 или 3) без разделителей между цифрами. Количество цифр в строке - от 1 до 100. Количество цифр в различных строках одинаково. Количество строк с планом пещеры - от 1 до 100. В остальном файл input.txt подчиняется правилам формирования исходных файлов данных (см.выше).

Задача заключается в нахождении всех возможных кратчайших путей от точки входа в пещеру до сундука с сокровищами. Из любой точки плана можно переместиться влево (L), вправо (R), вверх по плану (U), и вниз по плану (D). Найденный путь представляет собой комбинацию символов (без разделителей) L, R, U и D, описывающих перемещение по плану пещеры. Полученный набор кратчайших путей (по одному пути в каждой строке) должен быть лексикографически отсортирован по возрастанию и выведен в файл output.txt

Пример input.txt: 7 001000000100 001000000101 000101000101 013101001100 010001010101 011111110101 001000010101 100010001111 000011011011 001000210011

Соответствующий файл output.txt: LLLULLUULUUUURRD LLLULULULUUUURRD LLLUULLULUUUURRD LLLUUUUULU UULULLUULU UULULUULLU UUULLLUULU UUULLUULLU

2. С кочки на кочку (7 баллов).

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

Максимальное кол-во баллов: 7

Пусть имеется квадрат. Координаты левого нижнего и правого верхнего углов квадрата равны соответственно x1,y1 и x2,y2 (целые числа). Для простоты предположим, что длина стороны квадрата не превышает 1000. В квадрате располагаются точки xi,yi (естественно x2>xi>x1, y2>yi>y1). Положим, что координаты точек могут принимать только целые значения. Необходимо, передвигаясь (перескакивая) по точкам из левого нижнего угла попасть в правый верхний угол. При этом известно, что длина прыжка не может превышать некоторое значение r. Программа должна выдать путь передвижения, так чтобы этот путь был минимальным из всех возможных.

Структура файла input.txt.

Строка 1 – значение r. Значение r может быть произвольно, т.е. можно прыгать и через точки.

Строка 2 – координаты левого нижнего угла (два числа через пробел).

Строка 3 – координаты правого верхнего угла (два числа через пробел).

В остальных строках содержатся координаты точек, по которым должны производится прыжки (числа пишутся через пробел). Какой-либо порядок в перечислении координат точек отсутствует.

Структура файла output.txt.

Строка 1 – длина найденного оптимального пути (именно длина, а не количество шагов). В общем случае это вещественное число.

Остальные строки содержат координаты точек (по одной точке на строку, два числа через запятую) представляющие собой маршрут пути из точки x1,y1 в точку x2,y2.

Замечание 1.

При заданном расположении точек может быть несколько маршрутов, длина пути по которым будет одинакова. Ваша программа должна выдать только один из них, все равно какой. Длина пути в первой строчке файла output.txt и позволит быстро определить, правильно вы решили задачу или нет.

Замечание 2.

Поскольку количество путей между точками x1,y1 и x2,y2 может быть громадным, ваш алгоритм должен разумно отбрасывать заведомо неправильные решения, так, чтобы программа выполнялась за приемлемое время. В противном случае комиссия вынуждена будет снять значительную часть очков, положенных за правильное решение задачи.

Замечание 3.

Если при заданном r невозможно определить маршрут от левого нижнего угла к правому верхнему углу квадрата, то выходной файл output.txt должен содержать в первой строке слово empty.

Пример 1.

Файл input.txt 3 1 1 11 11 2 3 3 2 4 4 4 2 7 2 8 3 9 4 2 5 4 6 9 6 6 7 8 7 9 8 6 9 8 10 9 10

Файл output.txt 16.180340 1 1 2 3 4 4 4 6 6 7 6 9 8 10 9 10 11 11

Пример 2.

Файл input.txt 14 1 1 11 11 2 10 8 2

Файл output.txt 16.557901 1 1 8 2 11 11

3. В поисках пиратского клада, второй сезон (4 балла)

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

Максимальное кол-во баллов: 4

В библиотеке твоего дяди, одного из немногих оставшихся в живых кровных родственников старого пирата, нашёлся пергамент с картой острова в Карибском море, испещрённый странными точками. На оборотной стороне карты ты также обнаружил набор точек, который, к твоему изумлению, сложился в рисунок, крайне похожий на подпись старого пирата... А не может-ли эта подпись совпасть с одним или несколькими из наборов точек на карте, и ты наконец узнаешь, где находится пиратский клад?! Или хотя-бы что-то, что поможет тебе в дальнейших поисках?

Дано: исходный файл input.txt содержит два набора строк, разделённых пустой строкой. Оба набора состоят из цифр от 0 до 9 и представляют собой прямоугольные матрицы. Количество строк и столбцов в матрицах - от 1 до 100. Будем считать цифру 1 точкой, а остальные цифры - ничего незначащим шумом. Первый набор является подписью старого пирата, а второй - набором точек на карте острова в Карибском море. В остальном файл input.txt подчиняется правилам формирования исходных файлов данных (см.выше).

Результирующий файл output.txt должен содержать координаты левого верхнего угла всех совпадений подписи старого пирата с наборами точек на карте. Координаты должны описываться двумя числами (от 1) через пробел - номером строки и номером столбца.

Пример input.txt: 912 101 111 141 121 210800 131008 111410 101101 101111 000101 310181 131417 111110 121910 121715

Соответствующий файл output.txt: 1 1 3 4 7 1 7 3

4. Ротация (4 балла)

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

Максимальное кол-во баллов: 4

В текстовом файле input.txt содержится набор строк. В каждой строке содержится десятичное четырехбайтовое беззнаковое число. Числа представлены в строке в десятичном формате. В каждой строке стоит только одно число. Перед числом и после него может стоять произвольное количество пробелов.

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

Число, на которое следует осуществить сдвиг, располагается в первой строке файла input.txt. Сдвиг означает, что в каждом из чисел биты должны быть сдвинуты на указанное число в сторону старших бит. При этом все биты, выходящие за границы числа ai, переходят в следующее число (из ai в ai+1), в младшую его часть. Биты из числа an (последнего числа) переходят в число a1 (цикличность). Результирующий файл output.txt должен содержать результирующую последовательность чисел – по одному в каждой строке.

Замечание 1.

Первое число, т.е. число, расположенное в первой строке, определяет лишь величину сдвига и над ним операция не производится. Т.е., например, если в файле 100 строк, то в операции сдвига участвуют только 99 чисел.

Замечание 2.

Решения, не использующие массивы, получат +1 балл.

Пример 1. Input.txt 66 1 1 1 1 1 Output.txt 4 4 4 4 4

Пример 2. Input.txt 31 1 2 3 4 5 Output.txt 2147483650 0 2147483649 1 2147483650

5. Оптимальный выбор (2 балла)

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

Максимальное кол-во баллов: 2

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

Например, в последовательности

2 4
4 2
3 1
5 6

Последовательностью с максимальной длиной будет

2 4
3 1
5 6

Т.е. длина максимальной последовательности равна трем. Другая последовательность

4 2
3 1
5 6

также удовлетворяет условию. Вывести можно любую из них.

Итак, на входе программы файл input.txt, содержащий пары чисел. Каждая пара в своей строке.

На выходе программы файл output.txt, содержащий в первой строке искомое число, представляющее максимальную длину такой последовательности пар, в которой каждое число встречается только один раз. В следующих строках – пары чисел последовательности.

Пример.

Файл Input.txt. 2 4 4 2 3 1 5 6 7 8 8 9 2 8 5 10 7 2 1 3 6 9

Файл output.txt 4 2 4 3 1 5 6 7 8