Вот задачи с олимпиады:

Задача 1. Граничные точки

Ограничение времени (сек/тест) 10

Максимальный балл 80-100



ДАНО N (3 ≤ N ≤ 100000) точек на плоскости, которые служат вершинами M (3 ≤ M ≤ 50000) непересекающихся треугольников (см. рис.). Треугольники образуют несвязную область. Некоторые части этой области могут соприкасаться в одной точке (в шейке), например, в 8-ой точке. Внутри областей могут быть дыры, не покрытые треугольниками.

НАЙТИ массивы номеров граничных точек, упорядоченных по часовой стрелке или против часовой стрелке.

Для примера, приведенного на рисунке, это могут быть массивы (9,10,11), (0,1,2,22), (3,4,5,20), (7,8,14,13,12,8,21,19,23), (15,17,16,18).

Необходимо найти все границы (без повторений). “Шейки” могут как разбивать границы области на части, так и нет (т.е. в примере на рис. для большей фигуры допустимо одно из следующих решений:

две границы: (19,21,8,7,23) и (12,13,14,8) или
одна граница: (19,21,8,12,13,14,8,7,23) или
одна граница: (19,21,8,14,13,12,8,7,23)
и т.п.)

Замечания:

1. Строго говоря, координаты точек для решения этой задачи не нужны.

Формат входных данных (input.txt)

В первой строке число N, затем в N строках координаты X,Y (-10000 ≤ X, Y ≤ 10000) точек, затем число треугольников M, затем M строк и в каждой строке по три целых числа – номера точек, на которые опираются треугольники (нумерация точек начинается с 0).

Формат входных данных (output.txt)

В первой строке число границ N. Затем в N строках номера граничных точек каждой границы.


Пример входного файла (input.txt)

Цитата

24 -2 2 -3 2 -3 1 -3 3 -1 2 -2 -1 -5 -2 -1 -3 1 1 1 3 1 5 3 5 3 3 4 1 3 1 4 -2 2 -2 4 -1 4 -3 -7 3 -5 1 -2 4 -2 1 -6 -3 18 21 3 4 14 8 12 8 5 4 8 5 7 20 5 6 5 6 7 6 19 20 19 3 20 9 10 11 1 0 2 0 2 22 21 8 4 12 13 14 16 15 17 15 16 18 19 21 3 6 7 23 19 6 23

Пример выходного файла (output.txt)

Цитата

5 0 1 2 22 3 4 5 20 7 8 14 13 12 8 21 19 23 9 10 11 15 17 16 18

Задача 2. Триангуляция невыпуклого многоугольника

Ограничение времени (сек/тест) 10

Максимальный балл 100-120



ДАНО N точек на плоскости упорядоченных по часовой стрелке, которые образуют границу невыпуклого многоугольника с шейкой (см. рис.). Это означает, что координаты некоторых точек совпадают, например, на рис. совпадают координаты точек (3,12), (4,11), (5,10).

ПОСТРОИТЬ триангуляцию многоугольника, т.е. разбить многоугольник на непересекающиеся треугольники, вершинами которых являются вершины разбиваемого многоугольника, и при этом на стороне любого треугольника не могут лежать вершины многоугольника (в примере на рисунке треугольник 0-2-3 – недопустим, его можно разбить на 2 треугольника). Треугольник не может иметь площадь, равную нулю.

Формат входных данных (input.txt)

В первой строке число N (3 ≤ N ≤ 1000) , затем в N строках координаты X,Y (X, Y – целые числа, -10000 ≤ X, Y ≤ 10000) точек.

Формат входных данных (output.txt)

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

Пример входного файла (input.txt)

Цитата

14 8 -1 7 -2 6 -3 5 -1 3 -2 2 -1 3 -4 -6 -5 -1 3 -2 -2 2 -1 3 -2 5 -1 7 0

Пример выходного файла (output.txt)

Цитата

6 7 9 8 7 6 5 2 1 3 1 0 12 0 13 12 7 5 9

Задача 3.1. Летающий путешественник


Ограничение времени (сек/тест) 5

Максимальный балл 90-110

НАЙТИ самый короткий по времени маршрут при путешествии самолетами. Учитывать только международные аэропорты и рейсы между ними:

· Международные аэропорты расположены в разных часовых поясах;

· Каждый аэропорт имеет расписание полётов в котором определены пункт назначения, время отлёта, время в пути; это расписание работает в зависимости от дней недели;

· Посадка на самолёт (а также пересадка с одного самолёта на другой) занимает определённое время, которое может быть разным для разных аэропортов.

Для формализации проблемы мы сделаем следующие предположения:

· Названия всех международных аэропортов представлены как последовательности не более чем 20 символьно-числовых знаков или символов подчёркивания (например: 'a'...'z', 'A'...'Z', '0'...'9' или '_'); все названия уникальны,

· Все рейсы определяются комбинацией кода компании и номера рейса с общей длинной не более 5-ти символов; все комбинации также уникальны,

· Все идентификаторы чувствительны к регистру,

· Все данные, которые являются датой имеют формат "hh:mm", где "hh" и "mm" цифры с '0' до '9' являющиеся часами и минутами соответственно; если не определено иное – время локальное.

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

Формат входных данных

Первая строка входного файла содержит идентификатор аэропорта вылета и аэропорта назначения маршрута разделённые пробелами. Стартовое время – время, когда путешественник прибывает в аэропорт вылета.

Вторая линия входного файла содержит целое число N. Это число обозначает количество аэропортов и не бывает меньше 2 и больше 100.

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

Заголовок состоит из идентификатора аэропорта, временной зоны аэропорта, времени посадки и целого числа М разделённых пробелами. Временная зона является разницей времени между локальным временем и временем по Гринвичу и имеет формат "shh:mm", где "s" обозначает знак разницы во времени и может быть "+" или "-". Время посадки – время которое необходимо для посадки на самолёт или для пересадки с одного рейса на другой в данном аэропорте. Целое число М определяет количество рейсов в расписание аэропорта (не более 300), рейсы описаны в отдельных строках, следующих за описанием аэропорта.

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

Задача всегда будет иметь решение для предоставленных данных.

Формат выходных данных

В первой строке выходного файла должно быть напечатано общее время в пути, которое считается с момента когда путешественник прибыл в аэропорт вылета до момента прилёта в аэропорт назначения в формате "d:hh:mm", где "d" – количество полных дней путешествия (ни одно путешествие не может длиться больше 9 полных дней).

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






Задача 4.”Число с различными цифрами”


Ограничение времени (сек/тест) 5

Максимальный балл 60-70

Найдите N-ое(1<=N<=8877690) по порядку число с различными цифрами. Первым таким числом считайте 1.

Входные данные
Во входном файле input.txt содержится одно число N.

Выходные данные
В первой строке выходного файла output.txt должно содержаться N-ое по порядку число с различными цифрами.

Пример

input.txt
100

output.txt
123



Задача 5. «Расписание»

Ограничение времени (сек/тест) 5

Максимальный балл 40-50

В компьютерных классах занимаются N групп студентов. В i-й группе оказалось Xi человек. Имеется M аудиторий, в j-й аудитории имеется Yj компьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается.

ТРЕБУЕТСЯ создать программу для поиска максимального количества групп, которые удастся одновременно распределить по аудиториям, чтобы всем учащимся в каждой группе хватило компьютеров, и при этом остался бы еще хотя бы один для преподавателя.

Формат входных данных
На первой строке входного файла Input.txt расположены числа N и M (1 ≤ N ≤ M ≤ 1000). На второй строке расположено N чисел - X1...XN (1 ≤ Xi ≤ 1000 для всех 1 ≤ i ≤ N). На третьей строке расположено M чисел - Y1...YM (1 ≤ Yj ≤ 1000 для всех 1 ≤ j ≤ M).

Формат выходных данных

Выведите в первой строке файла Output.txt число P - количество групп, которые удастся распределить по аудиториям. Во второй строке выведите распределение групп по аудиториям - N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. (Нумерация как групп, так и аудиторий, начинается с 1). Если i-я группа осталась без аудитории, i-е число должно быть равно 0. Если допустимых распределений несколько, выведите любое из них.