Сложные задачки

[isst]

Вот решил подкинуть Вам задачки посложнее. Просто кому интересно, тот пусть порешает, спэшл фор РомаХа)))

[isst]

Имя входного файла: input.txt или стандартный поток ввода
Имя выходного файла: output.txt или стандартный поток вывода
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Олимпиада всегда приносит много хлопот для жюри и оргкомитета, и очный тур Открытой
олимпиады не является исключением из этого правила. Пока пишутся условия, готовятся тесты,
создаются разборы и настраиваются компьютеры, очень легко забыть правильно рассадить участ-
ников олимпиады по аудиториям.
В этот раз, в целях рационального использования рабочих мест, оргкомитет олимпиады поставил
перед собой задачу — создать компактную рассадку школьников по M имеющимся аудиториям.
Рассадка называется компактной, если для любых двух различных аудиторий количества детей в
них отличаются не более чем на один.
В жюри олимпиады имеется человек с экстрасенсорными способностями, который может очень
точно предсказывать результаты будущих соревнований по программированию. Хотя результаты
заочного тура ещё не известны, он без труда определил, что на очный тур пройдут ученики из K
школ. Кроме того, было предсказано, что из i-й школы (1 <= i <= K) пройдёт в точности ni учени-
ков. Хотя отношение большей части оргкомитета к подобным прогнозам зачастую скептическое, они
имеют странное свойство сбываться, поэтому вам предлагается на всякий случай вычислить мак-
симально возможное количество участников, которые попадут в одну аудиторию при компактной
рассадке, если предсказание окажется верным.
Формат входных данных
В первой строке ввода находятся два целых числа M и K — количество аудиторий и ко-
личество школ, участвующих в очном туре олимпиады согласно предсказанию (1 <= M <= 109
,
1 <= K <= 100 000).
В следующей строке находятся K чисел n с индексом i
, разделённых пробелами, i-е из которых обозначает,
сколько участников предположительно приедет из i-й школы (1 <= n с индексом i <= 109
).
Формат выходных данных
Выведите одно число — максимальное количество людей в аудитории при компактной рассадке

[isst]

Имя входного файла: input.txt или стандартный поток ввода
Имя выходного файла: output.txt или стандартный поток вывода
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

***

С незапамятных времен Берляндией правили добрые и справедливые цари, а власть передавалась по наследству. Но вот настали тяжёлые времена, по воле рока династия прервалась, и страна
погрузилась в хаос. Некоторые города были захвачены враждующими друг с другом бандами головорезов, в других же городах какая-либо власть исчезла вовсе.
Всё началось с того, что в некоторых городах установилась власть преступных банд, причём
под властью каждой из банд изначально оказалось ровно по одному городу. Каждая банда избрала
в качестве столицы город своего первоначального зарождения. Начиная с того времени, каждый
год ровно одна из банд решала расширить свои владения, захватывая некоторый город, до этого не
бывший ни в чьём подчинении или находящийся под властью другой банды.
Для осуществления захвата вооружённый отряд данной банды выходил из своей столицы и
двигался к выбранному городу, захватывая все города на своём пути. Также известно, что столицы
всех банд были так серьёзно защищены, что через них невозможно было проехать (и уж тем более
не могло идти речи об их захвате). Поэтому на пути от столицы банды-захватчика до выбранного
города не могло быть столиц других банд.
Как уже неоднократно отмечалось различными историками, в описываемые времена в Берляндии было N городов, соединённых между собой N −1 дорогой с двусторонним движением, при этом
от каждого города можно было доехать до любого другого. Подобное устройство транспортной
системы естественным образом налагало ограничения на возможные маршруты путешествия.
События эти происходили уже очень давно, а хроники тех лет были утрачены в вихре смутного
времени. Теперь же к вам в руки попала карта Берляндии тех времён. Вы обнаружили, что на карте
отмечены столицы каждой из банд, а также для каждого города указано, какая банда им владела
на определённый момент времени (свободных городов к тому году уже не осталось).
Вычислите, при какой возможной последовательности захватов могло возникнуть описанное этой
картой распределение контроля банд над городами, или же определите, что карта содержит ошибку,
так как указанное на карте распределение власти банд над городами не могло быть получено с
помощью последовательности описанных выше захватов. Более того, среди возможных ответов вам
необходимо найти последовательность, состоящую из не более чем N захватов.

***

Формат входных данных
В первой строке входных данных через пробел указаны два целых числа N и M — количество
городов на карте Берляндии и количество преступных банд (1 <= M <= N <= 300 000).
В следующих N − 1 строках описываются дороги Берляндии. Каждая строка содержит два
различных целых числа ai и bi (1 <= ai
, bi <= N), обозначающих, что между городами с номерами ai
и bi существовала дорога с двусторонним движением.
В следующей строке входных данных через пробел указаны M различных целых чисел ci
(1 <= ci <= N): согласно карте, в городе с номером ci находилась столица банды i.
В последней строке входных данных находятся N разделенных пробелами целых чисел di, обозначающих, что город под номером i (1 <= i <= N) отмечен на карте как находящийся под властью
банды с номером di (1 <= di <= M). Гарантируется, что dci = i для всех i.

***

Формат выходных данных
Если существует такая последовательность захватов, которая приводит к указанному на карте
распределению контроля банд над городами, то в первой строке выведите слово «YES» (без кавычек).
В следующей строке выведите единственное целое число S — длину найденной последовательности
захватов (обратите внимание, должно выполняться неравенство 0 <= S <= N). В следующих S строках выведите по два различных числа xi и yi — номера городов, являющихся столицей банды,
захватывающей города в i-м году, и конечной целью захвата в i-м году соответственно.


Всякие там "xi", "yi" - это икс с индексом i, y с индексом i и т.д.

[Poma][a]

Не-не-не
Давай первую вообще не решать.. Она из олимпиады, которая щас идет

[isst]

Сообщение от Poma][a

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

Возможно . А насчет второй как?

[Poma][a]

И чёйта первая никак не тянет на "сложную"..
(теперь, блин, придется участвовать в открытой)..

А дык и вторая снова от туда.. Не.. Так дела не пойдут

[isst]

Сообщение от Poma][a

И чёйта первая никак не тянет на "сложную"..
(теперь, блин, придется участвовать в открытой)..

То есть ты первую решил? А можешь код скинуть посмотреть?

[Poma][a]

То есть ты первую решил?

Номер решения	Время	Размер	Задача	Язык	Результат	Пройдено тестов	Баллы	Просмотреть протокол
25995	2015/01/07 14:57:16	327	A	g++-32	OK	34	100	Просмотр

Скинуть не могу.. Ибо религия и все такое
Единственное.. Там ничего сложного.. Все твои предыдущие задачи намного сложнее..
Сумма и деление..

[Аватар]

1-ая вообще какая-то очень простая. А во 2-ой плясать от возможности соединения N точек N-1 отрезком. Там 2 варианта: одна центральная соединена отрезками с каждой из остальных, или последовательное соединение точки с точкой, две крайние соединены только с одной, остальные с двумя соседними.

[ACE Valery]

Не по теме: какие идиоты придумывают условия задач? Нафига столько ненужной воды?