|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Санкт-Петербургские Олимпиады по Информатике |
Задачи международной олимпиады 1993 года
| Первый тур: | [Бусы] [Совладельцы] [Цветные прямоугольники] |
| Второй тур: | [Канадские авиалинии] |
|
|
| Максимальная оценка: | 20 баллов |
| Ограничение времени на тест: | 5 минут |
Имеются бусы, состоящие из N (N<=100) бусинок, некоторые из которых красного или голубого цвета, а остальные - белые. На рис. 1 и рис. 2 приведены два примера бус для N=29 (цифрами отмечены позиции первой и второй бусинок).
o x x o x o o x
o x x x
o o x o
o o @ o
x o @ @
x x o o
x x x x
x x o x
o o x o
x o o o
x o o o
o o o x
o x o o o @
Рис. 1 Рис. 2
о - красная бусинка Конфигурация бус задается последовательностью цветов
бусинок ("b" - голубая, "r" - красная, "w" - белая), начиная с бусинки
номер 1. Например, бусы на рис. 1 задаются последовательностью:
1 2 1 2
х - голубая бусинка
@ - белая бусинка
Порвем бусы и затем начнем снимать бусинки одного цвета с первого конца, пока не встретится бусинка другого цвета. То же самое проделаем со вторым концом (бусинки, снятые с разных концов, могут быть разного цвета). Требуется определить точку такого разрыва данных бус, при котором суммарное количество бусинок, собранных с обоих концов, максимально. Например, для бус на рис. 1 точка разрыва может находиться между 24 и 25 бусинками или между 9 и 10 бусинками; при этом суммарное количество бусинок в обоих случаях равняется 8.
При снятии бусинок с каждого из концов белая бусинка рассматривается как бусинка голубого или красного цвета по ситуации, то есть может сниматься как с голубыми, так и с красными.
Напишите программу, которая:
- Вводит данные из входного ASCII-файла с именем NECK- LACE.DAT, каждая
строка которого содержит конфигурацию бус, заданную в виде последовательности
цветов и записывает входные данные в выходной ASCII-файл с именем
NECKLACE.SOL. Пример входного файла NECKLACE.DAT:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb bbwbrrrwbrbrrrrrb
- Для каждой конфигурации бус определяет M - максимальное число собранных бусинок и положение одной из оптимальных точек разрыва.
- Выводит в качестве результата в выходной файл с именем
NECKLACE.SOL число M и точку разрыва. Ответы для разных
конфигураций отделяются пустой строкой. Пример выходного
файла NECKLACE.SOL:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb 8 between 9 and 10 bbwbrrrwbrbrrrrrb 10 between 16 and 17
|
|
| Максимальная оценка: | 30 баллов |
| Ограничение времени на тест: | 5 минут |
Некоторые компании являются совладельцами других компаний, так как приобрели часть их акций. Например, компания Форда владеет 12% акций компании Мазда. Говорят, что компания А контролирует компанию В, если имеет место по меньшей мере одно из следующих условий:
- А=В.
- А владеет > 50% акций В.
- А контролирует К (КЁ1) компаний С(1), Е, С(К) таких, что компания С(i) владеет соответственно Х(i)% акций компании В (для всех i от 1 до К), и Х(1)+Х(2)+ Е +Х(К)>50.
Задача, которую надо решить, заключается в следующем:
Дана последовательность троек чисел (i,j,p), означающих, что компания i владеет p% акций компании j. Требуется определить все пары чисел (h,s), при которых компания h контролирует компанию s. Общее число компаний не превышает 100.
Напишите программу, которая:
- Читает из входного ASCII-файла с именем COMPANY.DAT последовательность троек (i,j,p), где i, j и p - положительные целые числа. В файле могут содержаться последовательности троек чисел для нескольких тестов. Различные тестовые последовательности разделены пустой строкой.
- Находит все пары чисел (h,s) такие, что компания h контролирует компанию s.
- Записывает в выходной ASCII-файл с именем COMPANY.SOL все обнаруженные пары чисел (h,s), в которых h отличается от s. Пары (h,s) надо записать в последовательных строках в порядке возрастания h (каждая пара записывается в отдельной строке). Решения для различных тестовых наборов данных должны разделяться пустой строкой.
Пример:
| COMPANY.DAT | COMPANY.SOL |
2 3 25 1 4 36 4 5 63 2 1 48 3 4 30 4 2 52 5 3 30 1 2 30 2 3 52 3 4 51 4 5 70 5 4 20 4 3 20 |
4 2 4 3 4 5 2 3 2 4 2 5 3 4 3 5 4 5 |
|
|
| Максимальная оценка: | 50 баллов |
| Ограничение времени на тест: | 5 минут |
N прямоугольников различных цветов располагаются на белом прямоугольном листе бумаги, имеющем размеры А см в ширину и В см в длину. Стороны прямоугольников параллельны краям листа, а сами прямоугольники не выходят за пределы листа. В результате образуются различные одноцветные фигуры. Если два прямоугольника одного цвета имеют хотя бы одну общую точку, то они являются частями одной фигуры. Задача состоит в вычислении площади каждой из видимых одноцветных фигур для каждого цвета. А и В - четные положительные целые числа, не превосходящие 30.
Начало системы координат находится в центре листа, а оси параллельны краям листа.
Наборы данных для нескольких тестов записаны во входном ASCII-файле с именем RECTANG.DAT следующим образом:
А, В и N находятся в первой строке каждого набора данных и разделены пробелом.
В каждой из следующих N строк находятся:
- целочисленные координаты точки, в которую помещена левая нижняя вершина прямоугольника;
- за ними следуют целочисленные координаты точки, в которую помещена правая верхняя вершина прямоугольника;
- затем следует цвет прямоугольника, заданный целым числом от 1 до 64; белый цвет представлен числом 1.
Порядок строк соответствует порядку, в котором прямо- угольники размещались на листе от первого до последнего. Наборы данных для различных тестов разделены пустой строкой (см. пример).
Напишите программу, которая:
- Читает очередной набор данных из входного файла с именем RECTANG.DAT.
- Вычисляет площадь каждой из одноцветных фигур (см. пример).
- Записывает в выходной ASCII-файл с именем RECTANG.SOL цвет и площадь каждой одноцветной фигуры, как показано ниже в примере. Эти результаты должны записываться в порядке возрастания номера цвета. Результаты для различных тестов разделяются пустой строкой.
Пример:
| RECTANG.DAT | RECTANG.SOL |
20 12 5 -7 -5 -3 -1 4 -3 -3 5 3 2 -4 -2 -2 2 4 2 -2 3 -1 12 3 1 7 5 1 30 30 2 0 0 5 14 2 10 -7 0 13 15 |
1 177 2 39 4 23 12 1 1 630 2 70 15 200 |
|
|
| Максимальная оценка: | 50 баллов |
| Ограничение времени на тест: | 5 минут |
Вы победили в соревновании, организованном Канадскими авиалиниями. Приз - бесплатное путешествие по Канаде. Путешествие начинается с самого западного города, в который летают самолеты, проходит с запада на восток, пока не достигнет самого восточного города, в который летают самолеты. Затем путешествие продолжается обратно с востока на запад, пока не достигнет начального города. Ни один из городов нельзя посещать более одного раза за исключением начального города, который надо посетить ровно дважды (в начале и в конце пу- тешествия). Вам также нельзя пользоваться авиалиниями других компаний или другими способами передвижения. Задача состоит в следующем: дан список городов и список прямых рейсов между парами городов; найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям. Несколько наборов входных данных помещены в ASCII-файл C:\IOI\ITIN.DAT. Каждый набор содержит:
- в первой строке - количество городов N, в которые летают самолеты, и количество прямых рейсов V. N - положительное целое число, меньшее или равное 100. V - положительное целое число;
- в каждой из следующих N строк - название города, в который летают самолеты. Названия упорядочены с запада на восток, то есть i-ый по порядку город находится восточнее j-го тогда и только тогда, когда i> j (не существует городов на одном меридиане). Название каждого города - строка, состоящая из не более, чем 15 цифр и/или латинских букв, например: AGR34 или BELA
- в каждой из следующих V строк - названия двух городов из списка городов, разделенные пробелом. Если пара ГОРОД1 ГОРОД2 содержится в строке, это означает, что есть прямой рейс из ГОРОД1 в ГОРОД2, а также прямой рейс из ГОРОД2 в ГОРОД1.
Различные наборы входных данных разделены пустой строкой. После последнего набора данных пустой строки не будет. Пример файла входных данных C:\IOI\ITIN.DAT:
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
5 5
C1
C2
C3
C4
C5
C5 C4
C2 C3
C3 C1
C4 C1
C5 C2
Входные данные корректны, и их проверка не требуется. Решения, полученные для каждого набора входных данных, должны быть последовательно записаны в выходной ASCII-файл C:\IOI\ITIN.SOL следующим образом:
- в первой строке - общее количество городов из входного файла;
- в следующей строке - число M, равное количеству различных городов, посещаемых на маршруте;
- в следующих M+1 строках - названия городов по одному в строке в порядке их посещения.
Обратите внимание, что исходный город должен быть также выведен последним. Если для набора входных данных не существует решения, то для этого набора в выходном файле C:\IOI\ITIN.SOL должны быть только две записи: общее количество городов и сообщение "NO SOLUTION" (нет решения). Решения для разных наборов входных данных должны разделяться в выходном файле пустой строкой. Образец выходного файла C:\IOI\ITIN.SOL для приведенного выше примера:
8
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver
5
NO SOLUTION
Поместите вашу программу-решение в ASCII-файл с именем C:\IOI\DDD.xxx. Расширение .xxx равно .BAS для QBasic, .LCN для LOGO, .C для C, .PAS для PASCAL.