В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.
Шоу состоит из \(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
Группа 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
Польская армия движется из Костромы в деревню Домнино. Два гетмана Стефан и Константин руководят армией. Стефан изучил карту дорог Костромской губернии и каждую ночь он ведет армию от одной деревни к некоторой другой по некоторой дороге. Константин достал карту секретных троп между деревнями и каждый день он возглавляет марш-бросок армии вдоль одной из этих троп. Каждый гетман перед маршем спрашивает дорогу у Ивана Сусанина. Таким образом, в первый день Стефан возглавляет поход, на следующий день - Константин, потом - снова Стефан и т.д.
Длина каждой дороги указана на карте Стефана. Поэтому Стефан знает минимальное расстояние от каждой деревни до Домнино, аналогично Константин знает минимальное расстояние до Домнино по своей карте. Иван Сусанин каждый раз выбирает дорогу для Стефана или тропу для Константина так, что минимальное расстояние между войском и Домнино по соответствующей карте все время строго убывает.
Помогите Ивану найти самый длинный путь в Домнино, удовлетворяющий этим условиям. Гарантируется, что Домнино достижимо из каждой деревни.
Первая строка входа содержит три целых числа N, S и T – количество деревень, номер начальной деревни и номер деревни Домнино (2 ≤ N ≤ 1000, 1 ≤ s, t ≤ N). Начальная точка не совпадает с Домнино.
Далее идут описание карты Стефана и карты Константина
Первая строка описания карты содержит число M – количество дорог или троп соответственно (1 ≤ M ≤ 100000). Каждая из следующих М строк содержит 3 целых числа a, b и l – описывающих дорогу/тропу между пунктами a и b с указанием длины l (1 ≤ a, b ≤ N; 1 ≤ l ≤ 106).
Выведите общую длину пути (вдоль дорог и троп), который Сусанин заставит пройти польскую армию. Если он может заставить армию ходить вечно, так и не достигая Домнино, то выведите -1.
5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2
-1
3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10
20
За один шаг к числу X разрешается прибавить или из числа X разрешается вычесть любое положительное число Y, десятичная запись которого является подстрокой десятичной записи числа X. Стоимость такой операции равна сумме цифр числа Y.
Необходимо за минимальную стоимость получить из числа a число b, при этом все промежуточные числа должны быть положительными и не должны превышать n.
Входной файл содержит три целых числа: n, a, b (1 ≤ a, b ≤ n ≤ 5000).
Если из числа a нельзя получить число b, выведите в выходной файл одно число -1.
Если такая последовательность преобразований существует, в первой строке выходного файла выведите минимальную стоимость требуемого преобразования. Во второй строке выходного файла выведите число k — количество шагов в преобразовании. В последующих k строках выведите сами шаги преобразования по одному в строке. Каждая строка должна иметь вид +число или –число, в зависимости от того, прибавляется или вычитается очередное число.
20 12 18
5 3 -2 +10 -2
100 5 43
29 8 +5 +1 +1 +1 +13 +26 -5 -4
50 5 43
-1