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

К участию к заочной студенческой олимпиаде по программированию приглашаются студенты любых вузов. Олимпиада проводится в телекоммуникационном режиме. Задания олимпиады опубликованы на сайте ШГПИ www.shgpi.ru 27 февраля 2006 года в 14 часов. Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp_shgpi@list.ru) до 14 часов 28 февраля 2006 года. Альтернативно, решения задач могут быть вручены непосредственно членам комитета олимпиады (Пирогову В.Ю., Слинкину Д.А.).

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

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

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

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

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

Задачи для заочной олимпиады по программированию

Задача 1 (10 баллов).

Во время запуска многозадачная операционная система последовательно загружает отдельные программы-сервисы в фоновом режиме. Предположим, что ОС тратит фиксированный промежуток времени t для организации запуска любой программы, по окончании которого начинается загрузка самой программы, а ОС возвращается к выполнению своих функций. Каждый i-й сервис Si характеризуется собственным временем загрузки Ti, а также набором базовых сервисов, которые должны быть предварительно запущены для его корректного функционирования (считаем достаточным факт запуска и необязательной полную предварительную загрузку базовых сервисов). Будем считать ОС загруженной по окончании загрузки всех ее сервисов. Найти такую последовательность загрузки сервисов, чтобы время загрузки операционной системы было минимальным. Если такая последовательность не может быть вычислена из-за прямой или косвенной взаимозависимости сервисов, сообщить об этом. Определить время загрузки ОС.

Например: Даны сервисы S1, S2, S3 и S4, причем S4 зависит от S1 и S2, а S3 от S1. Время запуска операционной системой каждого сервиса t=50. T1=375, T2=100, T3=270, T4=300. Тогда последовательность запуска сервисов – S1 S2 S4 S3, при этом время загрузки операционной системы минимально и равно 470.

Формат файла input.txt

Время запуска сервиса операционной системой

Имя_сервиса1 Время_запуска сервиса1 Базовый_сервис1_1 Базовый_сервис1_2 ...

...

Имя_сервисаN Время_запуска_сервисаN Базовый_сервисN_1 Базовый_сервисN_2 ...

Содержимое input.txt для вышеприведенного примера:

50

S1 375

S2 100

S3 270 S1

S4 300 S1 S2

Формат файла output.txt

Последовательность загрузки сервисов

Время загрузки операционной системы

Или фраза

Операционная система не будет загружена из-за взаимозависимости сервисов

Содержимое output.txt для вышеприведенного примера:

S1 S2 S4 S3

470

Задача 2 (10 баллов).

Некая файловая система поддерживает права на чтение и запись, а также возможность наследования прав пользователей на каталоги. Это означает, что если на каталог пользователю предоставляется или отнимается право чтения или записи, то это право или запрет на него автоматически распространяется на все нижележащие подкаталоги. По умолчанию считается, что пользователи не имеют прав на файловую систему. Первая строка исходного файла input.txt содержит полное имя каталога X (в формате файловых систем UNIX), права на который следует определить. Каждая последующая строка исходного файла содержит имя пользователя Ai, его права на каталог Xi и полное имя каталога. Комбинации AiXi уникальны, то есть в исходном файле не может существовать несколько строк, определяющих права одного и того-же пользователя на один и тот-же каталог. Право (запрет) на чтение и запись описываются с помощью набора знаков r+, r-, w+, w-. В каждой строке результирующего файла output.txt сохраняются имя пользователя и одна из фраз: “только чтение”, “только запись”, “чтение и запись”, “нет прав” в зависимости от прав данного пользователя на каталог X.

Пример исходного файла input.txt:

/etc/httpd/conf/

user2 r+w+ /

user1 w+ /

user2 r- /etc/

user1 r+ /etc/

user1 w- /etc/httpd/

user1 w+ /etc/httpd/conf/

user3 r+w- /etc/X11/

Пример результирующего файла output.txt:

user2 только запись

user1 чтение и запись

user3 нет прав

Задача 3 (10 баллов).

Правила “игры в слова” заключаются в том, что играющие по очереди называют слово, первая буква которого равна последней букве предыдущего слова. Во входном файле input.txt находится набор слов (по одному слову в каждой строке). Разработать программу, которая выводит в результирующий файл output.txt цепочку, состоящую из последовательности слов с максимальным количеством букв (без учета пробелов между словами цепочки), сформированную по правилам “игры в слова”. Каждое слово исходного набора может быть включено в результирующую последовательность не более одного раза. Если таких цепочек несколько, то вывести все. Дублирующие цепочки должны быть исключены из рассмотрения.

Например

Файл input.txt

папа

арбуз

абракадабра

авиация

ад

домик

Файл output.txt

папа абракадабра авиация

папа абракадабра ад домик