ОБЛАСТНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ
1997-98 учебный год
I ТУР

1. “Лямзики”. Лямзики — это протобионтные организмы, обитающие на далекой планете. Существует три вида лямзиков — красные, зеленые и голубые. Изначально в колонии могут находиться представители двух или всех трех видов. Но если два лямзика разных цветов встречаются, то они сливаются, образуя организм третьего цвета (например, встреча голубого и красного приводит к образованию зеленого). Наступает момент, когда колония становится одноцветной. Написать программу, которая по введенным целым неотрицательным значениям численности красных, зеленых и голубых лямзиков определяет все возможные конечные цвета колонии.

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

2. “DIVIDE ET IMPERA!” На плоскости задано N прямых. Напишите программу, которая определяет, на сколько кусков разбивают плоскость эти прямые.

Исходные данные хранятся в массиве и записаны в следующем порядке: a1, b1, c1, d1, …, aN, bN, cN, dN, где N <= 100, а пары чисел (ai, bi) и (ci, di) — вещественные координаты двух различных точек, через которые проходит прямая с номером i.

Пример работы правильной программы
ВВЕДИТЕ КОЛИЧЕСТВО ПРЯМЫХ: 3
Введите координаты точек, через которые проходит 1-я прямая:
0 0 0 2
Введите координаты точек, через которые проходит 2-я прямая:
0 2 2 0
Введите координаты точек, через которые проходит 3-я прямая:
2 0 0 0
Искомое количество кусков плоскости 7
ВВЕДИТЕ КОЛИЧЕСТВО ПРЯМЫХ: 3
Введите координаты точек, через которые проходит 1-я прямая:
–2 –2 2 2
Введите координаты точек, через которые проходит 2-я прямая:
0 –2 4 2
Введите координаты точек, через которые проходит 3-я прямая:
2 –2 6 2
Искомое количество кусков плоскости 4

3. “Два конвейера”. В цехе по производству напитков работают два конвейера. На первом конвейере напиток разливается по бутылкам, а на втором — происходит закупоривание бутылок. После схода с первого конвейера очередной бутылки она сразу же поступает на второй. Поскольку тара используется различная, то каждая бутылка имеет свое время ее заполнения и время закупорки. Требуется написать программу, которая для заданной последовательности бутылок:
А) Определяет время, через которое последняя бутылка в этой последовательности будет закупорена (закупоривать можно лишь наполненные бутылки).
Б) Находит такую перестановку заданных бутылок, при которой суммарное время разлива и закупорки бутылок было бы минимально, и определяет это время.

Технические требования

Формат входных данных
В первой вводимой строке содержится целое число N (1 <= N <= 1000) — количество бутылок. Далее идут N пар чисел X1 Y1 X2 Y2… XN YN. Здесь Xi означает время разлива, а Yi — время закупорки бутылки с номером i. Xi и Yi — неотрицательные целые числа, не превосходящие 1000000. Все числа разделяются пробелами и/или символами перевода строки.

Формат выходных данных
Первая выводимая строка должна содержать время, требуемое для исходной последовательности бутылок, вторая — минимально возможное время для пункта Б задачи. Третья строка должна содержать перестановку номеров бутылок от 1 до N, для которой достигается минимальное время.

Пример работы правильно написанной программы:
3
200 40
100 100
30 90
490
370
3 2 1

4. “Антивирус”. Для распознавания различных вирусов программа HIVTEST использует набор сигнатур. Если сигнатура вируса встречается в файле, то файл считается зараженным этим вирусом. Напишите программу, которая по заданному набору сигнатур определяет, какими вирусами инфицирован анализируемый файл, и печатает имена этих файлов.

Сигнатурой назовем последовательность байтов и символов '?' и '*'. Байт — это две идущие подряд шестнадцатеричные цифры. Например, 1F?1E* — сигнатура, *?FFF — не является сигнатурой. Байт (две шестнадцатеричные цифры) в сигнатуре означает, что на этом месте в файле должен быть именно этот байт. Символ '?' означает, что на соответствующем месте может быть любой байт. Символ '*' заменяет любую, в том числе и пустую, последовательность байтов. Считается, что сигнатура присутствует в файле, если она может быть правильно прочитана, начиная с некоторой позиции этого файла.

Технические требования
1. Число различных вирусов не более 10.
2. Имена вирусов различны и состоят не более чем из 20 латинских букв и цифр.
3. Длина сигнатуры вируса не превышает 100 символов.
4. Длина анализируемого файла не более 128 байт.
5. Знак > — приглашение к вводу имени файла.

Для удобства тестирования необходимо предусмотреть возможность анализа нескольких файлов при одном и том же наборе вирусов. Программа должна проверять корректность ввода сигнатур и файлов.

Пример работы правильной программы

Введите количество вирусов 4
Введите имя 1-го вируса SmallVirus
Введите сигнатуру 1-го вируса 2F3E?4F
Введите имя 2-го вируса BigVirus
Введите сигнатуру 2-го вируса A5*FF?00*A6*23??24
Введите имя 3-го вируса UnknownVirus
Введите сигнатуру 3-го вируса 1F?07А?5
Ошибка в сигнатуре!
Введите имя 4-го вируса Polymorph
Введите сигнатуру 4-го вируса 22*33
Вводите анализируемые файлы.
Для окончания работы введите пустую строку.
>22312F3E454F763318
SmallVirus
Polymorph
>2233
Polymorph
>

 

Рейтинг ресурсов УралWeb
Сайт создан в системе uCoz