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

Санкт-Петербург, 2-9 апреля 1997 года 04.04.97

 

 

Задача 1. Текст на заборе

Мэр города Речуйска распорядился штрафовать за употребление нежелательных слов и обнародовал список этих слов с размером штрафа за каждое. Все эти слова состоят из букв "I", "N", "W".

Некто строит незамкнутый забор длиной N досок. Имеются доски, на каждой из которых написана одна из букв "I", "N" или "W". Получившийся забор будет содержать надпись из вышеназванных букв. За каждое нежелательное слово, образуемое какими-либо последовательно стоящими буквами (при прочтении слева направо), придется заплатить штраф, причем столько раз, сколько раз оно встречается на заборе.

Например, если запрещенными словами являются IN - штраф 1 рубль и WIWI - штраф 100 рублей, то за построение забора WIWIWINI будет назначен штраф 201 рубль.

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

Ограничения

Входные данные

Первая строка файла входных данных INPUT.TXT содержит длину забора N, вторая - количество слов в списке мэра M. В каждой из последующих M строк записано нежелательное слово и через пробел - соответствующий штраф. Все слова попарно различны, состоят только из больших букв латинского алфавита "I", "N" или "W".

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

Выходные данные

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

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

8

8

W 10

I 10

N 30

WI 1

WW 10

II 11

WIW 2

IWI 3

98

IWIWIWIW

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

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

Частичные решения задачи, которые находят только значение минимального штрафа без построения забора, будут оцениваться из максимальной оценки 20 баллов. Такие решения могут выводить в выходной файл только значение штрафа.

Время тестирования - 20 секунд на каждый тест.

   

Задача 2. Числообменник

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

Например, пусть . Тогда после перестановки чисел в позициях 1 и 4 (между ними стоят 2 числа) и чисел в позициях 1 и 5 (между ними стоят 3 числа) получится последовательность 5, 2, 3, 1, 4.

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

Ограничения:

.

Входные данные

Файл исходных данных INPUT.TXT содержит (в указанном порядке): N, M, . Все числа в файле разделяются пробелами и (или) символами перевода строки.

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

Выходные данные

В выходном файле OUTPUT.TXT должно находиться искомое число.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

5

2

3 2

24

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

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

Частичные решения задачи (количество перестановок ? 2 147 483 648) будут оцениваться исходя из 15 баллов.

Время тестирования -20 секунд на каждый тест.

Задача 3. Простые гири

Имеются гири с массами: 1 г, 2 г, ..., N г (N? 500000). Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.

Входные данные

Входной файл INPUT.TXT содержит число N.

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

Выходные данные

В выходной файл OUTPUT.TXT выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

7

1 6

7 4

5 2

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

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

Время тестирования -20 секунд на каждый тест.

 

Задача 4. INTERNETомания

Компания "Новые русские сети" разработала электронную энциклопедию "Мир Internet", состоящую из L одинаковых по объему томов, и желает распространить ее на все N серверов сети Internet. Передача данных по каналам связи начинается с сервера компании и может осуществляться с любого сервера отдельными томами в произвольном порядке. Каждый из M имеющихся каналов связи соединяет два сервера и имеет заданную пропускную способность, одинаковую в обоих направлениях и определяемую временем передачи по нему одного тома. Между любой парой серверов может быть не более одного канала. Информация на любом сервере становится доступной для считывания другими серверами через T минут после окончания приема всей энциклопедии. Возможна как одновременная передача произвольных томов сразу нескольким серверам, так и одновременное считывание различных томов сразу с нескольких серверов. На рисунке приведен пример возможной сети для N = M = 3, L = 3, T = 1.

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

Входные данные

Входные данные расположены в файле с именем INPUT.TXT в следующем порядке:

Время задержки T и время передачи задаются вещественными числами. Все числа во входном файле разделяются пробелами и (или) символами перевода строки в соответствии с представленным ниже примером. Все входные данные корректны.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать два числа. Первое число - минимальное время рассылки, а второе - номер сервера, который последним получит энциклопедию (если таких несколько, то любого из них).

Ниже приведен пример файлов INPUT.TXT и OUTPUT.TXT для сети, изображенной на рисунке. Пунктирными стрелками показано направление передачи данных.

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT:

3 3 3 1.0

1 2 3.0

2 3 3.0

3 1 6.0

13.00

3

 

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

Время тестирования - 20 секунд на каждый тест.

 

Задача 5. Энциклопедия

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

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

Таким образом, каждый том имеет вид:

<Имя_статьи><Пробел><Тело_статьи>

<Имя_статьи><Пробел><Тело_статьи>

. . .

<Имя_статьи><Пробел><Тело_статьи>

В теле словарной статьи могут встречаться ссылки на другие статьи вида:

<Разделитель><Имя_статьи><Пробел>"(см."[<Имя_тома>]")"

Здесь <Разделитель> - это любой печатный символ, не являющийся буквой.

Примечание. В определениях использованы следующие обозначения: (а) текст, заключенный в кавычки, должен находиться во входных и выходных данных в том же виде; (б) конструкции <...> замещаются соответствующими значениями; (в) запись [...] означает, что соответствующие элементы могут отсутствовать.

Требуется

Разработать диалоговую систему ЭНЦИКЛОПЕДИЯ, автоматизирующую работу со справочником. Система должна удовлетворять следующим требованиям.

1. Ввод команд осуществляется из командной строки, которая отделяется сверху от остального текста на экране пустой строкой. Приглашение для ввода команды выдается после запуска системы и после исполнения любой команды (кроме команды выхода из системы ). Приглашение состоит из имени текущего тома и символа ">"; сразу после запуска системы текущий том - это первый из перечисленных в файле INPUT.TXT.

2. Система должна выполнять следующие команды:

Формат команды

Описание

"DIR"

Вывести список томов справочника

"VOLUME"<Пробел><Имя_тома>

Сменить текущий том

"LIST"[<Пробел><Имя_тома>]

Вывести оглавление тома

"TYPE"<Пробел>[<Имя_тома>":"]<Имя_статьи>

Вывести статью на экран

"REF"<Пробел><Номер_ссылки>

Вывести статью по номеру ссылки

"CLS"

Очистить экран

"VERIFY"

Проверить корректность системы ссылок

"EXIT"

Завершить работу

Если имя тома опущено, то команда выполняется для текущего тома. Никакая команда, кроме VOLUME, не меняет текущего тома.

По команде TYPE система должна вывести на экран текст статьи с разбивкой на строки длиной не более 80 символов каждая; разбиение производится по пробелам. Строки должны быть максимально возможной длины. Наличие пробела в первой позиции строки не допускается.

Если статья содержит ссылки на другие статьи, то при ее выводе система должна вывести пронумерованный список различных ссылок в том порядке, в котором они встречаются в тексте статьи, с именами томов, если они находятся в других томах. Список отделяется от текста статьи пустой строкой. Формат вывода списка:

"1."<Пробел><Имя_статьи>[","<Пробел>"том"<Пробел><Имя_тома>]

"2."<Пробел><Имя_статьи>[","<Пробел>"том"<Пробел><Имя_тома>]

. . .

По команде LIST выводится пронумерованный список всех статей тома в том порядке, в котором они встречаются в томе. Формат вывода списка такой же, как для команды TYPE (раздел вывода имени тома отсутствует.

Команда REF может выполняться только сразу после выполнения одной из команд TYPE, REF или LIST; работает аналогично команде TYPE для статьи с заданным номером из списка ссылок (имен статей), выведенного непосредственно предшествующей командой (TYPE, REF или LIST).

По команде VERIFY система должна проверить все тома энциклопедии на отсутствие ссылок на несуществующие статьи. В случае отсутствия таких некорректных ссылок следует выдать сообщение

"Все ссылки корректны"

В противном случае выдать список несуществующих статей, на которые есть ссылки, с именами статей, в которых эти ссылки имеются. Формат вывода списка:

"Есть ссылки на несуществующие статьи:"

"1. Из "<Имя_тома>":"<Имя_статьи>" ссылка на "<Имя_тома>":"<Имя_статьи>"

"2. Из "<Имя_тома>":"<Имя_статьи>" ссылка на "<Имя_тома>":"<Имя_статьи>"

. . .

Здесь после "Из " указывается статья, в которой имеется некорректная ссылка, а после "ссылка на " - то, на что эта ссылка указывает.

3. Все тома, перечисленные в файле INPUT.TXT, существуют и находятся в текущем каталоге DOS.

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

"Нет такой команды"

"Том не найден"

"Статья не найдена"

"Неверный номер ссылки"

4. При входе в систему и по окончании работы необходимо выводить приветствия и прощания "Привет!" и "До свидания." соответственно.

5. В названиях команд (DIR, VOLUME, ...) и именах томов большие и маленькие буквы неразличимы (в отличие от всех других ситуаций). Регистр букв при выводе имен томов, приглашений и сообщений об ошибках выберите по своему усмотрению.

6. Размеры всей энциклопедии не превышают 10Кбайт.

7. Текст статьи со списком ссылок заведомо целиком помещается на экран компьютера.

Примеры

Пример файла INPUT.TXT:

Computer

English

Пример тома COMPUTER (файл COMPUTER.TXT):

компьютер -устройство для обработки информации. Основные части: процессор (см.), память (см.), монитор (см.), клавиатура (см.Computer), винчестер (см.),дисковод (см.).

процессор - основная микросхема (см.), мозг компьютера.

память - устройство для хранения временных данных.

клавиатура - устройство для ввода информации, имеет свой процессор (см.).

Также клавиатура (см.Music).

монитор - устройство для изображения текстовой и графической информации.

микросхема - маленькая, но умная железка.

винчестер - устройство для хранения данных. Также оружие-winchester (см.English).

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

Пример тома ENGLISH (файл ENGLISH.TXT):

animal - a living thing that can feel and move about (dog, bear (см.), fish).

amoeba (pl. -bae) - a very simple form of living found in the water.

amour - a secret (см.) love (см.) affair.

bear - a large, heavy animal (см.) with rough hair.

love - a feeling of affection, passion (см.) or desire between the sexes.

passion - strong feeling or enthusiasm.

passionate - easily giving way to strong feelings (e.g. love (см.)).

Winchester - Oliver F. Winchester (1810-1880), US gun manufacturer.

(смысл приведенных в примерах текстов не имеет для решения никакого значения).

Пример сеанса работы

Ниже приведен один из вариантов диалога с системой для нашего справочника, заданного файлами INPUT.TXT, COMPUTER.TXT и ENGLISH.TXT. Пример является иллюстративным и не исчерпывает все возможные ситуации.

Привет!

Computer>DIR

Computer

English

Computer>VOLUME English

English>list

1. animal

2. amoeba

3. amour

4. bear

5. love

6. passion

7. passionate

8. Winchester

English>TyPe amoeba

amoeba (pl. -bae) - a very simple form of living found in the water.

English>TYPE animal

animal - a living thing that can feel and move about (dog, bear (см.), fish).

1. bear

English>REF 2

Неверный номер ссылки

English>REF 1

Неверный номер ссылки

English>LIST computer

1. компьютер

2. процессор

3. память

4. клавиатура

5. монитор

6. микросхема

7. винчестер

English>TYPE Computer:винчестер

винчестер - устройство для хранения данных. Также оружие - winchester (см.English).

1. winchester, том English

English>VOLUME COMPUTER

Computer>TYPE компьютер

компьютер -устройство для обработки информации. Основные части: процессор (см.),

память (см.), монитор (см.), клавиатура (см.Computer), винчестер (см.),дисковод

(см.).

1. процессор

2. память

3. монитор

4. клавиатура

5. винчестер

6. дисковод

Computer>REF 4

клавиатура - устройство для ввода информации, имеет свой процессор (см.). Также

клавиатура (см.Music).

1. процессор

2. клавиатура, том Music

Computer>REF 2

Том не найден

Computer>VERIFY

Есть ссылки на несуществующие статьи:

1. Из Computer:винчестер ссылка на English:winchester

2. Из Computer:клавиатура ссылка на Music:клавиатура

3. Из Computer:винчестер ссылка на English:winchester

4. Из English:amour ссылка на English:secret

5. Из Computer:компьютер ссылка на Computer:дисковод

 

Computer>EXIT

До свидания.

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

Жюри независимо оценивает реализацию отдельных команд в системе.

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

 

Задача 6. Подсветка фонтана

Плоское дно фонтана описывается замкнутой ломаной линией без самопересечений, причем никакие три вершины ломаной не лежат на одной прямой. Для организации подсветки фонтана между двумя заданными углами (вершинами) по дну проложен гибкий натянутый кабель (см. рис.). Требуется написать программу, вычисляющую длину этого кабеля.

Входные данные

Исходные данные записаны в файле INPUT.TXT в следующей последовательности:

Координаты вершин являются вещественными числами.

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

Выходные данные

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

Пример файла INPUT.TXT:

Пример файла OUTPUT.TXT

7

2 0

5 0

6 3.5

5 6

4 2

3 7

0 5

3 7

7.5

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

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

Время тестирования - 20 секунд на один тест.