VI Всероссийская олимпиада

1994 год, г. Троицк Московской области

Задача 1. БОЛЬНИЦА (автор В.В.Прохоров)

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

Заболевание передается не только при непосредственном контакте с больным, но и при контакте с зараженными поверхностями предметов, которые становятся таковыми при соприкосновении с зараженными поверхностями других предметов.

Необходимо исключить инфицирование здоровых пациентов и увеличение количества зараженных кушеток после принятия процедур.

Для решения проблемы можно использовать стерильные простынки, поскольку сквозь ткань данная инфекция не передается. Из-за дефицитности простынок ТРЕБУЕТСЯ определить алгоритм их перестилания на кушетках, обеспечивающий выполнение указанных требований при минимально возможном расходе простынок. Разрешается стелить на кушетку друг на друга не более Р простынок.

Компьютерная программа должна:

- запрашивать параметры M, N, К, L, Р;

- выдавать минимальное требуемое количество простынок;

- выдавать оптимальный в указанном смысле процесс застилания кушеток и принятия процедур, где

<Процесс>::=<Процедура>,<Процедура>, ...

<Процедура>::=<Номер пациента> /<Простынка> /<Простынка> /.../ <Номер кушетки>

<Простынка>::=<Номер простынки><Ориентация простынки>

Здесь <Ориентация простынки> - "a", если простынка лежит лицевой стороной вверх, и "b"- в противном случае.

Пример. При M=1, N=З, K=0, L=1, P=2 программа должна выдавать минимальное количество "2" и, например, последователъность 1/1а/1, 1/2а/2, 1/2а/1b/З.

Примечания.

1. Контакт больного пациента с зараженной поверхностью ни к каким неприятным последствиям не приводит.

2. Общее время проведения процедур, их очередность, время ожидания пациентами очереди значения не имеют.

Оценка задачи

Максимальное количество баллов - 50.

Задача 2. ПАРКЕТ (автор С.Г.Волченков)

Комнату размером N*M единиц требуется покрыть одинаковыми плитками паркета размером 2*1 единиц без пропусков и наложений (M<=20, N<=8, M,N - целые). Пол можно покрыть паркетом различными способами. Например, для М=2, N=З все возможные способы укладки приведены на рисунке:

Задание:

Требуется определить количество всех возможнмх способов укладки паркета для конкретных значений M<=20, N<=8. Решением задачи является таблица, содержащая 20 строк и 8 столбцов.

Элементом таблицы является число, являющееся решением задачи для соответствующих M и N. На месте не найденных результатов должен стоять символ "*".

На рисунке приведен пример требуемой таблицы:

1

2

3

4

5

6

7

8

1

0

1

0

*

*

*

*

*

2

1

2

3

*

*

*

*

*

3

*

*

*

*

*

*

*

*

...

...

...

...

...

...

...

...

...

20

*

*

*

*

*

*

*

*

Таблица должна быть выровнена по столбцам и помещена в текстовый (АSCII) файл с именем "имя.RЕS", который обязательно сдается вместе с остальными файлами данного тура.

Примечание.

Результат решения задачи будет оцениваться по содержимому файла "имя.RES".

Оценка задачи:

Максимальное количество баллов - 50.

Чем больше правильно заполненных элементов таблицы, тем выше результат.

Задача З. БУКВОЕД (автор Е.В.Андреева)

Во входном файле содержится закодированное изображение электронного табло, состоящего из 25 строк и 80 столбцов лампочек. Известно, что на табло высвечивалась одна или несколько заглавных печатных букв: А, В, Ж, Л, М, О, С, Ф, Ю. Символы, отличные от перечисленных букв, на табло отсутствовали.

Две горящие лампочки, соседствующие на табло по горизонтали, вертикали или диагонали, принадлежат одной и той же букве. Буквы могут быть любого размера, толщины, начертания ("рукописные" буквы не допустимы). Буквы расположены вертикально. Изображения букв не касаются и не пересекаются. "Линии", образующие буквы, не имеют разрывов и полостей

Задание.

Написать программу, которая

1) запрашивает имя входного файла и выводит на экран монитора в текстовом режиме изображение электронного табло, представляя горящие лампочки символами '*';

2) решает задачу распознавания букв в предположении, что на табло изображена только одна буква;

3) решает задачу распознавания для произвольного количества букв.

Описание входных данных

Непрерывный ряд горящих лампочек одной строки, слева и справа от которого нет горящих лампочек, назовем серией. Каждая серия определяетея тремя числами: номером строки, номером столбца, в котором начинается серия, и количеством лампочек в серии. Изображение, находившееся на табло, было записано в текстовый файл путем описания множества всех его серий.

Первое число в файле - общее количество серий. Далее следуют тройки чисел, задающие серии. Числа в файле разделены пробелами или концами строк. Сначала в файле описаны все серии первой строки табло слева направо, затем второй, третьей и т.д. строк.

Описание вывода результата

После каждого нажатия клавиши 'пробел' в изображении одной из букв, выведенных на экран, символы '*' следует заменить на символ, соответствующий этой букве, например, 'А' для буквы А или 'Ю' для Ю, до тех пор пока все буквы на экране не будут разпознаны. В случае неоднозначного распознавания 6уквы вашей программой допустимо после нажатия клавиши 'пробел' заменить символы '*' в изображении этой буквы на два или даже три символа (например, на 'О','А' и 'Л'), распределяя их по изображению буквы.

Если вашей программе не удалось распознать ту или иную букву, то символы '*' в ее изображении следует заменить на символ '?'.

Примечания:

1. Все исходные данные корректны.

2. Строки табло пронумерованы сверху вниз.

З. В крайнем случае считывание данных можно организовать и с клавиатуры.

4. Вместо замены '*' на экране на соответствующие символы в крайнем случае ответ можно выдать в следующем виде: для каждой буквы в новой строке напечатать номер строки и столбца первой лампочки первой серии этой буквы и соответствующий ей символ (символы).

5. Если на вашем компьютере нет русских букв, используйте латинские буквы A, B, J, L, M, O, C, F.

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

Подсказка

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

Оценка задачи

1. Ввод данных из файла и изображение их на экране 10 баллов

2. Всего за распознавание букв от 0 до 70 6аллов

Однозначное распознавание буквы (одним символом) З балла за каждую

Распознавание буквы с помощью двух символов 2 балла за каждую

Распознавание буквы с помощью трех символов 1 балл за каждую

Замена символов '*' в букве на символ '?' 0 баллов

Неверное распознавание буквы -1 балл за каждую

3. Работа с файлом, описывающим более одной буквы 20 6аллов

Всего 100 баллов