yandex code championship - qualifiers

gistfile1.txt

A. Развозка фанатов
Ограничение времени 	1 секунда
Ограничение памяти 	64Mb
Ввод 	стандартный ввод или input.txt
Вывод 	стандартный вывод или output.txt

После футбольного матча фанаты пытаются уехать домой на такси. Чтобы сэкономить, они объединяются в группы: фанат присоединяется к группе, если знает хотя бы одного человека из неё, группа хочет ехать исключительно в одной машине, а две разные группы отказываются ехать вместе. Таксопарк владеет ограниченным числом машин заданной вместимости. Определите, получится ли у таксопарка развезти экономных фанатов.
Формат ввода

В первой строчке задано число N — число фанатов, во второй число М — количество знакомств между фанатами. Далее следует M пар чисел от 0 до N-1, разделенных пробелом: каждая пара означает обоюдное знакомство между фанатами. Далее следует число K — количество типов машин, и K пар вида (вместимость машины, количество таких машин). Пары гарантированно уникальны.

1 <= N <= 1000

0 <= K <= 1000
Формат вывода

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

6
3
0 1
1 2
4 5
2
3 2
5 1

	

1

Пример 2
Ввод 	Вывод

6
0
1
6 5

	

0

Пример 3
Ввод 	Вывод

3
2
0 1
1 2
1
2 2




B. Прогулка по городу
Ограничение времени 	1 секунда
Ограничение памяти 	64Mb
Ввод 	стандартный ввод
Вывод 	стандартный вывод

Водитель приехал в новый город, который пока ещё не знает. Он захотел изучить все улицы города.

Чтобы запомнить улицу, ему достаточно посетить любой перекрёсток, который образует эта улица. Поэтому водитель решил посетить все перекрёстки города.

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

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

При запуске система пишет ровно одну строку с одним числом N - количество перекрестков в городе.

Далее система ожидает вывод программы - следующий перекресток, который необходимо посетить (более подробно формат описан в секции "Формат вывода"). В ответ на это система выдает строку с числами, разделенными через пробел. Первое число в строке K - число перекрестков, до которых можно доехать из текущего. Далее идут через пробел номера этих перекрестков.

Водитель всегда начинает с перекрестка с номером 0.

Ограничения:
3 ≤ N ≤ 500
1 ≤ K ≤ N-1
Максимальное количество итераций (количество посещенных вершин): 5000

Если превышено количество итераций, система остановит выполнение и результатом задачи будет PE.
Формат вывода

Система ожидает на выходе программы на каждой итерации ровно одну строку с одним числом - номером очередного перекрестка. Если ваша программа посетила все перекрестки, тогда необходимо вывести -1 вместо номера перекрестка. Это будет признаком того, что необходимо завершить работу. После этого система не будет ничего присылать на вход.

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

Некоторые улицы города могут быть односторонними. Ни одна улица не может начинаться и заканчиваться в одном и том же перекрестке. Все перекрестки в городе нумеруются с 0 до N-1 включительно.

Гарантируется, что все перекрестки возможно посетить за максимальное число итераций.

Пример:

3
> 0
1 1
> 1
1 2
> 2
1 0
> -1

Пояснения к примеру:
В примере символом > указан выход программы, который идет на вход системе. Следом за этой строкой идут входные данные в программу, которые выдает система в ответ на это.
В первой строке система сообщает, что в городе всего 3 перекрестка. Первым мы обязаны посетить перекресток с номером 0. В ответ система сообщает, что из него можно перейти только в один другой перекресток - с номером 1.
Далее за 3 шага мы посещаем все 3 перекрестка, поэтому дальше можно завершить работу. Для этого программа выводит число -1.




C. Стоянка запрещена
	Все языки 	Python 3.7.3 	Python 2.7
Ограничение времени 	1 секунда 	10 секунд 	10 секунд
Ограничение памяти 	256Mb 	256Mb 	256Mb
Ввод 	стандартный ввод или input.txt
Вывод 	стандартный вывод или output.txt
Описание

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

Из-за подобных ограничений в этом городе осталось всего Z водителей, каждый из которых в момент старта задачи находится в какой-то вершине графа дорожного движения. Система управления должна назначить наилучшего водителя из тех, которые успеют приехать в указанный интервал. Наилучшим водителем считается тот, который приедет на заказ максимально близко к началу интервала. Если таких водителей несколько, то любой из них.

Нужно для каждого водителя определить, успевает ли он приехать в указанный интервал, и если да - то к какому самому раннему моменту времени в указанном интервале он может приехать.

Формальное описание
Дано:

    Ориентированный граф G с N вершинами и K ребрами, вершины пронумерованы от 0 до N-1, 0 ≤ N ≤ 104, 0 ≤ K ≤ 104. Каждому ребру соответствует время поездки в нем - целое число W, 10 ≤ W ≤ 104.
    Позиция заказа на графе IDtarget
    Z позиций водителей на графе IDsourcez, 1 ≤ Z ≤ 104
    Время t0, 0 ≤ t0 ≤ 600 - целое число

Надо для каждого водителя найти такоe t_min что:

    существует такой маршрут от IDsourcez водителя к IDtarget, что водитель приезжает в tmin
    tmin ∈ [t0;t0+180]
    и это самый ранний возможный tmin : tmin ≤ ti для любого ti, удовлетворяющего пунктам 1 и 2;
    Или убедиться, что такого tmin не существует

Формат ввода

Граф задается в виде троек вершина-начало вершина-конец время-проезда

Входные данные, каждый пункт на своей строке

    K - число ребер
    K троек ID ID Weight - начальная вершина ребра, конечная вершина ребра, за сколько машина проезжает ребро.
    IDtarget t0 - вершина заказа [пробел] начало диапазона, когда надо приехать
    Z - кол-во водителей
    (Z раз) IDz вершина следующего водителя

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

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

Пример 1
Ввод 	Вывод

2
0 1 10
2 3 10
3 0
1
0

	

-1



D. Оптимизация транспортной системы Марса
Ограничение времени 	3 секунды
Ограничение памяти 	64Mb
Ввод 	стандартный ввод
Вывод 	стандартный вывод
Шёл 2058 год. Колонии первых поселенцев уже высадились на Марсе и стали его обживать, а Яндекс.Такси начала развертывание системы шатл-станций.  

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

Задача состоит в том, чтобы организовать эффективное (с минимальной стоимостью) питание всех шатл-станций.  

На вход программа получает общее число шатл-станций, стоимости строительства генераторов для каждой шатл-станции и описания всех возможных кабелей между шатл-станциями (номера соединяемых станций и стоимость прокладки кабеля).
Формат ввода
Первая строка содержит одно целое неотрицательное число шатл-станций N≤1000.  

Вторая строка содержит N чисел, задающих стоимости строительства генератора внутри соответствующей станции.  

Третья строка содержит одно целое неотрицательное число возможных кабелей K≤100000 между шатл-станциями.  

Последующие K строк (начиная с четвёртой) содержат описание одного кабеля - три целых неотрицательных числа: номер первой станции, номер второй станции и стоимость проведения.
Формат вывода
Одно целое число - минимальная стоимость питания всех шатл-станций для заднной конфигурации.
Пример 1
Ввод 	Вывод

1
77
0

	

77

Пример 2
Ввод 	Вывод

2
11 29
1
1 2 17

	

28

Примечания
Станции нумеруются с единицы.  
Числа внутри строки разделяются одним пробелом.  
Корректность входных данных проверять не требуется.