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

Санкт-Петербург, 6-11 апреля 1998 года

I тур

Задача 1. Хеш-функция

имя входного файла: hash.in
имя выходного файла: hash.out
время на один ход: 20 секунд
максимальный балл: 34

Для быстрого распознавания идентификаторов в современных трансляторах используются хеш-функции. Хеш-функция сопоставляет строке целое число из некоторого промежутка. Критерием оценки хеш-функции является количество коллизий, то есть ситуаций, когда различным встретившимся строкам сопоставляется одно и то же число.

Вы должны построить хеш-функцию для заданного множества слов русского языка и реализовать ее в программе, которая будет вычислять хеш-значения из интервала от 1 до 255 для всех слов из входного файла. Ваша функция будет оцениваться в зависимости от максимального количества слов, хеш-значения которых оказались одинаковыми: чем это количество меньше, тем лучше функция.

На время тура вам предоставляется файл words.txt, содержащий перечисленные в алфавитном порядке 10 000 слов. Слова из этого файла будут использоваться при тестировании вашего решения. Это означает, что во всех тестах слова будут выбираться только из этого множества. Во время тестирования файл words.txt будет вашей программе недоступен.

Для одного и того же слова хеш-значение, формируемое вашей программой, должно быть одинаковым для всех тесто. В противном случае задача считается нерешенной.

Размер исходного текста вашей программы не должен превышать 10 килобайт. Программы большего размера оцениваться не будут.

 

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

Входной файл содержит список неповторяющихся слов по одному в строке, выбранных из файла words.txt. Регистр букв в словах будет тем же, что и в файле words.txt.

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

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

 

Пример входного файла hash.in

мертвые

души

кому

на

Руси

жить

хорошо

герой

нашего

времени

Пример выходного файла hash.out

8

5

5

3

5

5

7

6

7

8

Примечание

Оценка хеш-функции в приведенном примере равна четырем.

Задача 2. Разделяй и властвуй

имя входного файла: divide.in
имя выходного файла: divide.out
время на один ход: 20 секунд
максимальный балл: 33

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





Тридесятое государство имеет форму прямоугольника, стороны которого тянутся с запада на восток и с севера на юг. Картограф изобразил карту государства в виде прямоугольника на системе координат с центром O, совпадающим с юго-западным углом страны и осями, параллельными осям координат. Засеки на карте изображены в виде отрезков различной длины, параллельных осям координат. При этом оказалось, что никакие два отрезка не пересекаются и не лежат на одной прямой.

 

 

Для удобства управления своей страной царь Салтан повелел разделить ее на непересекающиеся прямоугольные области с соблюдением следующих условий:

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

Напишите программу, помогающую картографическому приказу построить искомое разбиение.

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

В первой строке входного файла находятся координаты северо-восточного угла страны, Во второй строке указано количество засек N (N?1000). Каждая из следующих N строк содержит описание одной из засек в виде четверки числе x1, y1, x2, y2, что соответствует отрезку с концевыми точками (x1, y1) и (x2, y2). Все координаты являются неотрицательными целыми и не превосходят 10000.

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

В первую строку выходного файла выведите количество областей M в найденном разбиении. В последующих M строках должны находиться целочисленные координаты юго-западного и северо-восточного углов для каждой из областей разбиения. Числа внутри строки разделять пробелами.

 

Пример входного файла divide.in

5 5

3

4 1 2 1

2 2 2 3

2 4 0 4

Пример выходного файла divide.out

4

2 0 5 1

2 1 5 5

0 4 2 5

0 0 2 4

Задача 3. Приватизация

имя входного файла

rail.in

имя выходного файла:

rail.out

время тестирования

20 секунд

максимальный балл:

33

Железнодорожная сеть состоит из отдельных участков, соединяющих города попарно. Этими участками каждый из N имеющихся городов соединен с тремя другими городами. Две компании собираются приватизировать все эти участки, но антимонопольный комитет настаивает на том, чтобы из каждого города выходили дороги разных компаний.

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

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

В первой строке входного файла содержится натуральное число N - количество городов (N=5000) Далее для каждого города i (i=1,...,N) записана тройка различных чисел - номера тех городов, с которыми он связан. Соединение городов i и j, если оно существует, отражено в соответствующих строках. Между любыми двумя городами может проходить не более одной дороги.

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

В выходной файл требуется вывести список участков, предназначенных для приватизации одной из компаний (все остальные участки приватизируются другой компанией). Каждый участок задается в отдельной строке двумя числами - номерами тех городов, которые он соединяет. Числа должны разделяться пробелами. Если решения не существует, выходной файл должен содержать единственную строку "NO SOLUTION".

Пример входного файла rail.in

6

6 5 3

6 4 3

4 1 2

5 3 2

6 4 1

2 1 5

Пример выходного файла rail.out

1 6

2 4

3 4

5 6

II тур

 

Задача 4. Игра "Просто Филя"

имя входного файла: filya.in
имя выходного файла: filya.out
время на один ход: 5 секунд
максимальный балл: 50

Дано прямоугольное клеточное поле 41? 45 клеток. Каждая клетка покрашена в один из шести цветов. Цвета пронумерованы от 1 до 6. Левая верхняя и правая нижняя клетки поля имеют различный цвет. В результате поле разбивается на некоторое количество одноцветных областей. Две клетки одного и того же цвета, имеющие общую сторону, принадлежат одной и той же области.

Правила игры

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

 

3

4

4

5

6

6

6

3

3

5

5

6

6

1

4

3

5

6

2

4

6

2

6

5

6

5

4

6

2

4

3

2

6

5

6

3

6

6

1

1

1

1

 

 

5

4

4

5

6

6

6

5

5

5

5

6

6

1

4

5

5

6

2

4

6

2

6

5

6

5

4

6

2

4

3

2

6

5

6

3

6

6

1

1

1

1

Цель игры - включить в свою область как можно больше клеток. Игра заканчивается, когда все поле разобьется на две области или в течение 4 ходов ни одна область не увеличилась.

Задание

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

Критерии оценки

Качество вашей программы будет оцениваться в зависимости от количества клеток в вашей области после завершения тестовой игры.

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

Входной файл filya.in содержит 41 строку по 45 цифр в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Вам предоставляется пример входного файла.

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

Выходной файл filya.out содержит номер цвета хода.

Пример выходного файла

5

Примечание

Для отладки своей программы вы можете воспользоваться программой filya.exe, правила работы с которой описаны в файле read.me.

Задача 5. Поезда

имя входного файла

train.in

имя выходного файла:

train.out

время тестирования

20 секунд

максимальный балл:

33

В связи с увеличившимся числом аварий на железнодорожной трассе "Нью-Васюки-Петербург" руководство железнодорожной компании решило изменить график движения поездов. Тщательный анализ состояния полотна установил, что оптимальным является следующий график движения: сначала T1 минут поезд идет со скоростью V1 метров в минуту, затем T2 минут со скоростью V2 м/мин, ..., наконец, TN минут со скоростью VN м/мин. В течение интервала Ti (1? i? N) поезд может стоять.

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

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

В первых двух строках входного файла содержатся натуральные числа, задающие минимально допустимое расстояние L и количество участков пути N (100? L? 10000, 1? N? 1000). Далее следуют N пар целых чисел T1, V1, ..., TN, VN, описывающих график движения (1? Ti? 1000, 0? Vi? 1000).

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

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

Пример входного файла

1000

4

10 0

30 80

15 0

20 100

Пример выходного файла

27.5

Задача 6. Бал

имя входного файла

bal.in

имя выходного файла:

bal.out

время тестирования

20 секунд

максимальный балл:

17

Увы, на разные забавы

Я много жизни погубил!

Но если б не страдали нравы,

Я балы б до сих пор любил.

А.С.Пушкин

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

Напишите программу, находящую требуемое расположение дам.

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

Во входном файле содержатся два натуральных числа M и N (3? M? 1000, 1? N? 109).

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

В выходной файл для каждого угла требуется вывести число дам, стоящих в этом углу (0 или 1), а для каждой стены - количество дам, стоящих вдоль нее (не считая тех, что стоят в углах). Таким образом, в файле должно быть 2M чисел в соответствии со следующим порядком: сторона AMA1, угол A1, сторона A1A2, угол A2, ..., сторона AM-1AM, угол AM.

Числа в файле разделяются пробелами и/или переводами строки. В случае, если требуемым образом дамам разместиться невозможно, выходной файл должен содержать единственную строку NO.

Пример входного файла

3 10

Пример выходного файла

3 1

2 1

3 0