VI Всероссийская олимпиада школьников по информатике

Троицк, 1994 год

Задачи

Задача 1. Больница

В процедурном кабинете N кушеток. Каждый из 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. На месте не найденных результатов должен стоять символ "*".

Ниже приведен пример требуемой таблицы:
 12345678
1010*****
2123*****
...........................
20********

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

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

Система оценки

Максимальная оценка за задачу - 50 баллов.

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

Задача 3. Буквоед

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

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

Задание

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

  1. запрашивает имя входного файла и выводит на экран монитора в текстовом режиме изображение электронного табло, представляя горящие лампочки символами "*"
  2. решает задачу распознавания букв в предположении, что на табло изображена только одна буква
  3. решает задачу распознавания для произвольного количества букв

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

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

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

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

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

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

Примечания

  1. Все исходные данные корректны.
  2. Строки табло пронумерованы сверху вниз.
  3. В крайнем случае считывание данных можно организовать и с клавиатуры.
  4. Вместо замены "*" на экране на соответствующие символы в крайнем случае ответ можно выдать в следующем виде: для каждой буквы в новой строке напечатать номер строки и столбца первой лампочки первой серии этой буквы и соответствующий ей символ (символы).
  5. Если на вашем компьютере нет русских букв, используйте латинские буквы A, B, J, L, M, O, C, F.
  6. Файл данных для пункта (З) описывает произвольное количество букв, причем каждая из перечисленных букв может как встречаться несколъко раз, в том числе и в различных модификациях, так и отсутствовать.

Система оценки

  1. Ввод данных из файла и изображение их на экране - 10 баллов
  2. Всего за распознавание букв от 0 до 70 6аллов
  3. Работа с файлом, описывающим более одной буквы 20 баллов

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