Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе --> Алгоритм Флойда
---> 20 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 Отображать по:
#2519
Цирковое шоу
  
Источники: [ Командные олимпиады, ВКОШП, 2009, Задача J ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Шоу состоит из \(n\) небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление \(i\) начинается через \(s_i\) минут от начала шоу и продолжается \(t_i\) минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).

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

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

Первая строка входного файла содержит число \(n\) (\(1 \le n \le 200\)). Следующие \(n\) строк содержат пары чисел \(s_i\), \(t_i\). (\(0 \le s_i \le 10^9\), \(1 \le t_i \le 10^9\))

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

Выведите в выходной файл \(n\) чисел. Число номер \(i\) должно быть равно \(1\), если в \(i\)-ом представлении участвуют львы, или \(2\), если участвуют тигры, или \(0\), если не участвуют ни те ни другие.

Примеры
Входные данные
5
8 3
0 7
4 5
1 2
11 3

0 7
1 3
4 9
8 11
11 14
Выходные данные
2 1 0 1 2
#2598
Pink Floyd
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

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

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

Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤104, 2≤k≤104). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤bi,ei≤n, −105≤wi≤105). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.

Примеры
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
Выходные данные
6
5 6 5 7 2 3
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
Выходные данные
infinitely kind
#3342
Среднее расстояние (C)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вам дано описание дорожной сети страны. Ваша задача – найти среднюю длину кратчайшего пути между двумя городами. Средней длиной называется отношение суммы по всем парам городов (\(a\), \(b\)) длин кратчайших путей \(l_{a,b}\) из города \(a\) в город \(b\) к числу таких пар. Здесь \(a\) и \(b\) – различные натуральные числа в диапазоне от 1 до \(N\), где \(N\) – общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.

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

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа \(N\) и \(K\) (\(1 \leq N \leq 100, 1 \leq K \leq N(N-1)\)), где \(К\) – количество дорог. Каждая из следующих \(K\) строк содержит описание дороги с односторонним движением – три целых числа \(a_i\), \(b_i\) и \(l_i\) (\(1 \leq a_i,b_i \leq N\), \(1 \leq l_i \leq 1000\)). Это означает, что имеется дорога длины \(l_i\), которая ведет из города \(a_i\) в город \(b_i\).

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

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

Примеры
Входные данные
6 4
1 2 7
3 4 8
4 5 1
4 3 100
Выходные данные
25.000000
#3555
10E: Pink Floyd
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Найти самый длинный путь от одной вершины до другой в ориентрованном графе, либо определить, что существует сколь угодно длинный путь, либо определить, что пути не существует.

Группа Pink Floyd собирается отправиться в новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других — много ест и набирает вес.

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

Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.

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

Первая строка входного файла содержит три натуральных числа \(n\), \(m\) и \(k\) — количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (\(n \le 100\), \(m \le 10\,000\), \(2 \le k \le 10\,000\)). Города пронумерованы числами от \(1\) до \(n\).

Следующие \(m\) строк содержат описание рейсов, по одному на строке. Рейс номер \(i\) описывается тремя числами \(b_i\), \(e_i\) и \(w_i\) — номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (\(1 \le b_i, e_i \le n\), \(-100\,000 \le w_i \le 100\,000\)).

Последняя строка содержит числа \(a_1, a_2, ..., a_k\) — номера городов, в которых проводятся концерты (\(a_i \neq a_{i+1}\)). В начале концертного тура группа находится в городе \(a_1\).

Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число \(l\) — количество рейсов, которые должна сделать группа. Вторая строка должна содержать \(l\) чисел — номера используемых рейсов.

Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку „infinitely kind“.

Примеры
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
Выходные данные
6
5 6 5 7 2 3
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
Выходные данные
infinitely kind
#111745
pinkfloyd
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

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

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

Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤104, 2≤k≤104). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤bi,ei≤n, −105≤wi≤105). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.

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

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

Примеры
Входные данные
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
Выходные данные
6
5 6 5 7 2 3
Страница: << 1 2 3 4 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест