Пруд черепахи Тортиллы сильно изменился с момента последнего посещения Буратино. Теперь он представляет собой прямоугольное поле из \(w\) столбцов и \(h\) строк, в некоторых клетках которого расположены кувшинки. На этих кувшинках в солнечные дни греются многочисленные дети, внуки и правнуки Тортиллы.
На пруду находится набор из n связных кувшинок. Набор кувшинок называется связным, если от любой кувшинки можно дойти до любой другой, переходя по кувшинкам, смежным по стороне.
Черепахи очень любят ходить друг к другу в гости. Когда одна черепаха решает нанести визит другой, она строит некоторый маршрут, проходящий через смежные по стороне кувшинки и соединяющий ее кувшинку с кувшинкой своей знакомой. Однако неподвижный образ жизни черепах накладывает серьезные ограничения на возможные маршруты — перед началом движения черепаха выбирает некоторые два из четырех возможных направлений перемещения (вверх, вниз, влево, вправо) и затем может переходить с кувшинки на кувшинку только в одном из этих двух направлений.
Например, на приведенном ниже рисунке черепахе с кувшинки \(A\), желающей нанести визит черепахе с кувшинки \(B\), нужно выбрать направления вверх и влево, чтобы иметь возможность проложить маршрут. С другой стороны, черепаха с кувшинки C не имеет возможности добраться до кувшинки \(A\), так как на любом пути, соединяющем их кувшинки, потребуется перемещаться по меньшей мере в трех направлениях.
По итогам семейного совещания Тортилла приняла решение последовательно добавить к \(n\) имеющимся кувшинкам \(q\) новых.
Ваша задача — до начала добавлений и после каждого добавления определить, является ли набор кувшинок удобным для черепах. Тортилла гарантирует вам, что после каждого очередного добавления набор кувшинок остается связным.
В первой строке находятся два целых числа \(h\), \(w\) — количество строк и столбцов в клетчатом поле, которым является пруд (\(1 \le h, w \le 10^5\)).
В следующей строке находится целое число n — количество кувшинок в пруду в начальный момент (\(1 \le n \le 10^5\)).
В последующих \(n\) строках находится по два целых числа \(r_i , c_i\) — для каждой кувшинки заданы номера строки и столбца, на пересечении которых она находится (\(1 \le r_i \le h, 1 \le c_i \le w\)).
В следующей строке находится целое число \(q\) — количество кувшинок, которые собирается добавить Тортилла (\(0 \le q \le 100 000\)).
В последующих \(q\) строках в аналогичном формате заданы пары целых чисел \(nr_i\) , \(nc_i\) , обозначающие соответственно номер строки и номер столбца клетки с очередной добавленной кувшинкой (\(1 \le nr_i \le h, 1 \le nc_i \le w\)).
Гарантируется, что никакие две кувшинки во входных данных не совпадают. Гарантируется, что исходно и после каждого добавления набор кувшинок является связным.
Выведите \(q+1\) строку, каждая из которых представляет собой либо слово «YES», либо слово «NO», в зависимости от того, является ли на очередной момент времени система кувшинок удобной для черепах или нет. Первая строка должна содержать ответ для начального расположения кувшинок, каждая из последующих должна содержать ответ после очередного добавления кувшинки.
5 10 8 1 4 2 4 2 5 2 6 1 6 3 5 3 4 4 4 4 1 5 2 7 3 7 3 6
NO YES YES NO YES
3 3 5 1 1 1 2 1 3 2 3 3 3 4 2 1 3 2 3 1 2 2
YES NO NO NO YES
Дед Афанасий решил подлатать забор вокруг своего деревенского участка. В прошлом году он как раз строил сарай, так что доски для ремонта у него остались.
Забор состоит из n сегментов, каждый из которых представляет собой доску высотой \(a_i\) . У деда есть тележка, на которой лежит стопка из m досок, про каждую из которых известна ее длина \(b_i\) .
Дед Афанасий идет вдоль забора и катит перед собой тележку с досками. Если он хочет увеличить высоту текущего сегмента, он может взять доску с тележки и прибить ее сверху. Тогда новая высота сегмента будет равна сумме изначальной высоты сегмента и длины прибитой доски. Дед не хочет прибивать больше одной доски к каждому сегменту забора, чтобы сохранить его прочность.
Собираясь увеличить высоту сегмента забора, Афанасий поступает следующим образом. Он либо использует для увеличения сегмента верхнюю доску с тележки, либо выкидывает одну или несколько верхних досок с тележки и использует следующую доску. Силы у Афанасия уже не те, поэтому он никогда не возвращается назад вдоль забора и никогда не подбирает выкинутые ранее доски.
Перед началом работы дед задумался, какую максимальную высоту может иметь забор после починки. Высотой забора Афанасий считает высоту самого низкого сегмента забора. Помогите деду Афанасию узнать, какую максимальную высоту забора он сможет получить.
В первой строке входного файла находится целое число n — количество сегментов в заборе (\(1 \le n \le 10^5\) ). Во второй строке содержатся n целых чисел \(a_1, a_2, \dots , a_n\) — высоты сегментов забора, перечисленные в том порядке, в котором мимо них пройдет дед Афанасий (\(1 \le a_i \le 10^8 \)).
В третьей строке находится целое число \(m\) — количество досок на тележке (\(1 \le m \le 10^5\) ). В четвертой строке содержатся m целых чисел \(b_1, b_2, \dots , b_m\) — длины досок на тележке, начиная с верхней (\(1 \dots b_i \le 10^8\) ).
В первую строку выходного файла выведите два целых числа \(h\) и \(k\) — максимальную возможную высоту забора и количество досок, которые деду следует использовать при починке. В следующих \(k\) строках выведите по два целых числа \(x_i\) и \(y_i\) , которые означают, что к \(x_i\)-му сегменту забора деду следует прибить доску с номером \(y_i\) .
Если существует несколько способов починить забор требуемым образом, выведите любой из них.
3 10 5 10 1 5
10 1 2 1
6 2 5 4 1 7 5 7 2 3 1 3 2 4 6
5 3 1 2 3 3 4 6
Андрей Сергеевич работает сторожем в зоопарке. Однажды утром он пришел на работу и обнаружил анонимную записку, в которой сообщалось, что ночью хулиганы поменяли таблички на двух клетках. Андрей Сергеевич должен срочно решить проблему и поменять таблички обратно. К сожалению, Андрей Сергеевич хорошо разбирается в охране зоопарка, но не столь силен в зоологии, так что понять по внешнему виду животного, что это за зверь, он не в силах.
К счастью, на каждой табличке помимо наименования животного написан также порядковый номер. Номера на всех табличках разные. Обойдя зоопарк, Андрей Сергеевич составил его карту. В зоопарке есть n перекрестков, соединенных m дорожками. Чтобы встречные потоки посетителей не мешали друг другу наслаждаться посещением зоопарка, по каждой дорожке разрешено перемещаться ровно в одном направлении, от начала дорожки к ее концу. При этом от одного перекрестка до другого идет максимум одна дорожка, не существует дорожки, которая начинается и заканчивается на одном и том же перекрестке. Рядом с каждой дорожкой расположена ровно одна клетка с животным.
Перекрестки в зоопарке пронумерованы от 1 до \(n\), Андрей Сергеевич для каждой дорожки записал номер перекрестка, на котором она начинается, номер перекрестка, на котором она заканчивается, и номер на табличке, в настоящий момент находящейся на клетке с животным около этой дорожки.
Около входа в зоопарк расположен список тематических маршрутов, рекомендуемых сотрудниками зоопарка. Каждый тематический маршрут задается начальным перекрестком, конечным перекрестком и последовательностью дорожек, по которым следует пройти, чтобы изучить соответствующих животных. Первая дорожка в маршруте начинается на его начальном перекрестке, каждая следующая дорожка начинается на перекрестке, где заканчивается предыдущая, а последняя дорожка завершается на конечном перекрестке маршрута. Каждая дорожка задается номером таблички на клетке с животным, расположенной около соответствующей дорожки. Никакой маршрут не проходит через один перекресток два раза. По каждой дорожке в зоопарке проходит хотя бы один тематический маршрут.
Андрею Сергеевичу тут же пришла в голову гениальная мысль: используя информацию о тематических маршрутах, он может выяснить, какие две таблички хулиганы поменяли местами. Но, к сожалению, задача оказалась для него слишком сложной. Помогите сторожу выяснить, какие две таблички поменяли местами, чтобы он успел восстановить порядок до открытия зоопарка.
Выясните, какие две таблички можно поменять местами, чтобы все тематические маршруты в зоопарке действительно существовали. Гарантируется, что это можно сделать.
В первой строке содержится два целых числа \(n\) и \(m\) — количество перекрестков и количество дорожек, соответственно (\(1 \le n, m \le 10^5\)). Все перекрестки пронумерованы от \(1\) до \(n\).
Следующие m строк содержат по три целых числа \(a_i
, b_i\) и \(c_i\) — номер перекрестка, где
начинается очередная дорожка, номер перекрестка, где она заканчивается, и номер на табличке
на расположенной на этой дорожке клетке
(\(1 \le a_i
, b_i \le n, a_i \ne b_i
, 1 \le c_i \le m\)). Все номера на
табличках различны.
В следующей строке содержится целое число \(k\) — количество тематических маршрутов по зоопарку (\(1 \le k \le 10^5\)).
Следующие \(2k\) строк описывают маршруты. Первая строка описания маршрута содержит три целых числа \(l_i , s_i\) и \(t_i\) — число дорожек в маршруте, номер перекрестка, где маршрут начинается и номер перекрестка, где он заканчивается (\(1 \le l_i \le n, 1 \le s_i , t_i \le n, s_i \ne t_i\)). Во второй строке содержится \(l_i\) чисел — последовательность номеров на табличках на клетках, вдоль которых проходит этот маршрут.
Суммарная длина всех маршрутов не превышает \(100 000\). Никакой маршрут не проходит через один перекресток два раза. По каждой дорожке в зоопарке проходит хотя бы один тематический маршрут.
Выведите два различных числа — номера табличек на клетках, которые Андрей Сергеевич должен поменять местами, чтобы все тематические маршруты снова существовали. Если существует несколько решений, то выведите любое из них.
Карта зоопарка из примера и тематические маршруты приведены на следующем рисунке.
6 6 1 2 1 2 3 3 3 6 6 1 4 4 4 5 5 5 6 2 2 3 1 6 1 5 6 3 1 6 4 3 2
3 5
Городской школьник Лёша поехал на лето в деревню и занялся выращиванием цветов. Он посадил \(n\) цветков вдоль одной длинной прямой грядки, и они успешно выросли. Лёша посадил различные цветки, \(i\)-й от начала грядки цветок имеет вид \(a_i\), где \(a_i\) - целое число, номер соответствующего вида в «Каталоге юного агронома».
Теперь Лёша хочет сделать фотографию выращенных им цветов и выложить ее в раздел «мои грядки» в социальной сети для агрономов «ВКомпосте». На фотографии будет виден отрезок из одного или нескольких высаженных подряд цветков.
Однако он заметил, что фотография смотрится не очень интересно, если на ней много одинаковых цветков подряд. Лёша решил, что если на фотографии будут видны три цветка одного вида, высаженные подряд, то его друзья — специалисты по эстетике цветочных фотографий — поставят мало лайков.
Помогите ему выбрать для фотографирования как можно более длинный участок своей грядки, на котором нет трех цветков одного вида подряд.
В первой строке содержится целое число \(n (1 \le n \le 200 000)\) — количество цветков на грядке.
Во второй строке содержится n целых чисел \(a_i (1 \le a_i \le 10^9 )\), обозначающих вид очередного цветка. Одинаковые цветки обозначаются одинаковыми числами, разные — разными.
Выведите номер первого и последнего цветка на самом длинном искомом участке. Цветки нумерются от 1 до \(n\).
Если самых длинных участков несколько, выведите описание любого из них.
6 5 6 6 6 23 9
3 6
В парке развлечений «Пуперленд» открылся огромный верёвочный парк. Особая гордость парка — трасса, состоящая из \(n\) платформ, соединённых \(n − 1\) верёвками: первая платформа соединена со второй, вторая — с третьей, \(\dots\) , \(n − 1\)-я — с \(n\)-й, верёвка, соединяющая \(i\)-ю платформу с \(i + 1\)-й имеет длину \(l_i\) .
В парке серьёзно относятся к технике безопасности, так что для трассы были разработаны следующие правила эксплуатации:
- для всех \(i\) от \(2\) до \(n − 1\) на \(i\)-й платформе разрешается находиться не более, чем \(p_i\) людям одновременно; (первая и последняя платформы достаточно надёжны, и на них может находиться произвольное число людей);
- на верёвке, протянутой между \(i\)-й и \(i + 1\)-й платформами, разрешается находиться не более, чем \(r_i\) людям одновременно;
- для каждой верёвки известно минимальное безопасное расстояние \(d_i\) метров, такое что двум людям, одновременно идущим по этой верёвке, нельзя приближаться друг к другу ближе, чем на это расстояние.
Все люди разные и будут проходить трассу с разной скоростью. Пронумеруем посетителей от 1 до \(m\) в том порядке, в котором они выстроились в очередь. Для \(j\)-го посетителя известна скорость \(v_{i,j}\) м/c — максимальная скорость, с которой он может проходить по верёвке, соединяющей \(i\)-ю и \(i + 1\)-ю платформы. Таким образом, \(j\)-й посетитель может перемещаться по \(i\)-й верёвке с любой скоростью от 0 до \(v_{i,j}\) , соблюдая при этом условия про минимальное расстояние до других посетителей, идущих по той же верёвке.
Администрация парка не ожидала такого наплыва посетителей и теперь опасается, что все посетители могут не успеть пройти трассу до закрытия парка. Помогите им посчитать минимальное время, которое потребуется всем посетителям, чтобы пройти трассу
В первой строке заданы два целых числа \(n (2 \le n \le 100)\) и \(m (1 \le m \le 100)\) — число платформ на трассе и число посетителей.
Во второй строке заданы \(n − 2\) целых числа \(p_2, \dots , p_{n−1} (1 \le p_i \le 100)\) — ограничения на число людей на платформах. Обратите внимание, что если \(n = 2\), то эта строка пуста.
В следующей строке задано \(n − 1\) целое число \(r_1, r_2, \dots , r_{n−1} (1 \le r_i \le 100)\) — ограничение на число людей на \(i\)-й верёвке.
В следующей строке задано \(n − 1\) целое число \(l_1, l_2, \dots , l_{n−1} (1 \le l_i \le 100)\) — длины верёвок в метрах.
В следующей строке задано \(n − 1\) целое число \(d_1, d_2, \dots , d_{n−1}\) — ограничение в метрах на расстояние между людьми на \(i\)-й верёвке. Гарантируется, что \(1 \le d_i \le l_i\).
В оставшихся \(n − 1\) строке находится по \(m\) целых чисел: \(\)v_{1,1}, v_{1,2}, \dots , v_{1,m}\(\) \(\)v_{2,1}, v_{2,2}, \dots , v_{2,m}\(\) \(\)\dots\(\) \(\)v_{n−1,1}, v_{n−1,2}, \dots , v_{n−1,m},\(\) где \(v_{i,j}\) — скорость в м/с \(j\)-го посетителя на \(i\)-й верёвке (\(1 \le v_{i,j} \le 100\)).
Выведите единственное число — время в секундах, которое необходимо, чтобы все посетители прошли трассу
Ваш ответ должен иметь относительную или абсолютную погрешность не больше \(10^{−6}\).
Таким образом, он будет засчитан, если \(|a−p|/max(a,1) \le 10^{−6}\) , где \(p\) — ваш ответ, а \(a\) — правильный ответ
2 1 1 30 2 2
15.0
3 2 1 2 2 10 10 5 5 2 2 1 2
17.5