Раскрыть

Заочная студенческая олимпиада по программированию

К участию к заочной студенческой олимпиаде по программированию приглашаются студенты любых вузов. Олимпиада проводится в телекоммуникационном режиме. Задания олимпиады будут опубликованы на сайте ШГПИ www.shgpi.edu.ru 20.02.2007 года в 14 ч. (12.00 Москвы). Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp_shgpi@list.ru) до 14 ч. (12.00 Москвы) 21.02.2007 г.

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

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

Итоги олимпиады будут подведены до 1 марта 2007г и опубликованы на сайте www.shgpi.edu.ru. Участники заочной олимпиады приглашаются к участию в молодежной научно-практической конференции “Актуальные проблемы прикладной информатики и методики преподавания информатики”. Научные материалы победителей будут опубликованы бесплатно. Дополнительно, при участии в очной олимпиаде в рамках конференции победители заочной олимпиады получают 10% бонус по очкам.

Задачи для заочной студенческой олимпиады по программированию

Вашему вниманию предлагается четыре задачи, объединенных в две группы. Это означает, что решение одной задачи группы может помочь в решении другой. В то-же время задачи являются достаточно независимыми и для решения любой из них не требуется решение других. При верном и качественном решении задач участник олимпиады может набрать максимум 30 баллов.

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

Вопросы по условиям задач можно задавать с помощью электронной почты (olimp_shgpi@list.ru), в форуме http://forum.shadrinsk.net с помощью личных сообщений пользователям Vladislav_133 (задачи 1.1, 1.2.) и xdsl (задачи 2.1, 2.2, оргвопросы), либо в соответствующей теме форума (http://forum.shadrinsk.net/viewtopic.php?p=282153#282153).

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

Задача 1.1. Архиватор.

Количество баллов – 4. Прохождение крэш-тестов – дополнительно 1 балл.

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

В тексте сжатого файла придется хранить частотный словарь. Обычно хранят только коды символов, отсортированных по их частотам.
Если количество различных символов в тексте превышает 127, то сжатие отсутствует.
При сжатии слишком маленьких файлов получается обратный эффект - т.е. сжатый файл оказывается длиннее не сжатого. Впрочем это характерно для большинства современных архиваторов.

Задача: написать программу, сжимающую текстовые файлы по данному методу.

Структура командной строки:

Исполняемый_файл <имя_исходного_файла> <имя_сжатого_исходного_файла>

Например: arch.exe text.txt text.dat

Отсутствуют ограничения на длину исходного и сжатого файлов. Если выходной файл с указанным именем уже существует, программа переписывает его.

На рисунке представлена структура такого файла.

Обозначения:

A – один байт, содержит длину частотного словаря в байтах.

B - частотный словарь. Байты отсортированы согласно их встречаемости (частоте).

Если частота у двух символов одинакова, первым идет символ с большим кодом ASCII. При анализе текста следует учитывать и управляющие символы, в частности символы конца строки: коды 13 и 10 в ОС Windows, 10 – в Unix(Linux).

C - байты сжатого текста.

Пример.

Рассмотрим текстовый файл в кодировке cp-1251, предназначенный для ОС Windows :

АБ

СД

Обращаем ваше внимание, что в тексте имеются коды перевода строк 13 и 10 (0D и 0A), по два для каждой строки (после каждой строки). В результате сжатия получится файл, содержащий следующую последовательность байт (в шестнадцатеричном виде):

06 0D 0A 91 84 81 80 25 A2 21

06 - количество элементов в частотном словаре

0D - код перевода строки

0A - код конца строки

91 - код символа C

84 - код символа Д

81 - код символа Б

80 код символа A

Далее идут байты, содержащие упакованные биты номеров символов. Рассмотрим их в двоичном формате.

25 - 0010 0101 A2 - 1010 0010 21 - 0010 0001

Размер частотного словаря составляет 6 байт, следовательно для обозначения символа использовано 3 бита.

101 - 5, т.е. символ А

100 - 4, т.е. символ Б

000 - 0, т.е. символ с кодом 0D

001 - 1, т.е. символ с кодом 0A

010 - 2, т.е. символ C

011 - 3, т.е. символ Д

000 - 0, т.е. символ с кодом 0D

001 - 1, т.е. символ с кодом 0A

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

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

Исходный текст.

Результат сжатия.

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

Задача 1.2. Деархиватор.

Количество баллов – 4. Прохождение крэш-тестов – дополнительно 1 балл.

Написать программу-деархиватор, распаковывающий сжатый файл (см. Задача 1.1.).

Структура командной строки:

Исполняемый_файл <имя_сжатого_исходного_файла> <имя_распакованного_файла>

Например: dearch.exe text.dat text.txt

Если выходной файл с указанным именем уже существует, программа переписывает его. Не накладываются никакие ограничения на длину сжатого и распакованного файлов. Как было сказано в условии задачи 1, в последнем байте сжатого файла могут быть не используемые биты. При распаковке это приводит к появлению в конце распакованного файла посторонних символов. Это допускается условием задачи!

Все сообщения программы выводятся в консоли (командной строке).

Задача 2.1. Лабиринт

Количество баллов – 5. Прохождение крэш-тестов – дополнительно 2 балла.

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

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

Первая строка содержит два натуральных числа через пробел: MaxX – размер лабиринта по горизонтали и MaxY – размер лабиринта по вертикали.

Следующие MaxY строк задают матрицу лабиринта с помощью символов 0 (проход) и 1 (стена).

Затем в каждой строке перечисляются координаты точек лабиринта (натуральные значения через пробел), до которых следует найти кратчайший путь. Координаты задаются от 1, т.е. координата левого верхнего угла равна (1;1), а координата правого нижнего - (MaxX;MaxY).

Пример файла input.txt:

10 5

0000000000

1111110100

1000010100

0101010101

0000000001

8 2

2 3

1 4

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

Пример файла output.txt:

(1;1) (2;1) (3;1) (4;1) (5;1) (6;1) (7;1) (7;2) (7;3) (7;4) (7;5) (6;5) (5;5) (4;5) (3;5) (3;4) (3;3) (2;3)

(1;1) (2;1) (3;1) (4;1) (5;1) (6;1) (7;1) (7;2) (7;3) (7;4) (7;5) (6;5) (5;5) (5;4) (5;3) (4;3) (3;3) (2;3)

(1;1) (2;1) (3;1) (4;1) (5;1) (6;1) (7;1) (7;2) (7;3) (7;4) (7;5) (6;5) (5;5) (4;5) (3;5) (2;5) (1;5) (1;4)

Задача 2.2. «Волшебный» лабиринт

Количество баллов – 10. Прохождение крэш-тестов – дополнительно 3 балла.

При прохождении «волшебный» лабиринт изменяет свою структуру после каждого шага, опуская одни и поднимая другие перекрытия. После определенного количества шагов видоизменения волшебного лабиринта прекращаются и он превращается в обычный лабиринт. Найти все кратчайшие пути от левого верхнего угла двумерного «волшебного» лабиринта до заданных точек. Запрещены перемещения по диагоналям и возврат в точки, которые уже были посещены. По соображениям гуманности запрещены перемещения в те точки лабиринта, в которые на текущем шаге будут опущены перекрытия :). Отсутствуют ограничения на размеры лабиринта, количество видоизменений на каждом шаге, количество шагов, при которых осуществляется видоизменение структуры лабиринта и количество точек, которых следует достичь.

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

Следующие MaxY строк задают матрицу лабиринта с помощью символов 0 (проход) и 1 (стена).

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

Следующие N строк содержат по одной карте видоизменений лабиринта. Структура карты: count X1 Y1 M1 X2 Y2 M2 ..., где count – количество видоизменений лабиринта на текущем шаге, а тройки Xi Yi Mi определяют само видоизменение: Xi Yi – координаты видоизменения; Mi – 0 (перекрытие поднялось) или 1 (перекрытие опустилось). Координаты задаются от 1, т.е. координата левого верхнего угла равна (1;1), а координата правого нижнего- (MaxX;MaxY).

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

Пример файла input.txt:

5 5

01000

01111

10000

01010

00000

1 2 1 0

3 1 2 0 1 3 0 1 3 0

4 5 1 1 4 2 0 5 3 1 3 1 1

2 3 2 0 1 5 1

5 5

4 3

3 1

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

Пример файла output.txt:

(1;1) (1;2) (1;3) (2;3) (3;3) (3;4) (3;5) (4;5) (5;5)

(1;1) (2;1) (3;1) (4;1) (4;2) (4;3)

(1;1) (1;2) (1;3) (2;3) (3;3) (4;3)

(1;1) (2;1) (3;1)

Наверх