Разбойники с большой дороги Джон и Боб ограбили караван и в качестве добычи получили три золотых слитка. Решив поделить добычу по-братски, Джон и Боб взвесили слитки и выяснили, что они весят \(x_1\), \(x_2\) и \(x_3\) фунтов, соответственно.
Теперь Джон и Боб хотят поделить слитки так, чтобы каждому из них досталось равное количество золота. Им не хотелось бы пилить слитки, но деваться некуда. Обсудив ситуацию, они решили, что если смогут, поделят добычу как есть, а если нет, то сумеют-таки распилить один слиток на две части. Распилить два или все три слитка они уже не смогут.
Помогите Джону и Бобу выбрать, какой слиток распилить на две части, и на какие части его следует распилить, чтобы после этого можно было поделить добычу поровну.
Первая строка входных данных содержит три целых числа: \(x_1\), \(x_2\) и \(x_3\) (\(1 \le x_i \le 10^8\) , сумма весов слитков чётна).
Если невозможно распилить один слиток таким образом, что после этого можно поделить золото поровну, выведите −1.
Если Джон и Боб и так могут поделить золото поровну, выведите 0.
В противном случае на первой строке выведите число 1, если следует распилить первый слиток, 2, если следует распилить второй слиток, либо 3, если следует распилить третий слиток. На второй строке выведите два положительных целых числа: веса частей, на которые следует распилить слиток. В сумме две части должны давать исходный вес слитка. Так как суммарный вес золота чётен, слиток всегда требуется распиливать на части, имеющие целый вес. Если возможных решений несколько, выведите любое.
2 3 3
2 2 1
Каждое утро Антон едет на работу на автобусе.
Маршрут автобуса включает в себя \(n\) остановок, пронумерованных от 1 до \(n\) в порядке следования. Автобус проезжает от каждой остановки до следующей за одну минуту, а его временем стоянки можно пренебречь. Антон садится на первой остановке и выходит на последней.
В автобусе есть m сидений, которые расположены в один ряд и пронумерованы от 1 до \(m\), ближайшее к входу сиденье имеет номер 1, а самое дальнее — номер \(m\). На каждом сиденье может сидеть один пассажир, а также возле каждого сиденья может стоять один пассажир.
Когда человек входит в автобус, он садится на ближайшее ко входу свободное сиденье. Если они все заняты, он ищет ближайшее ко входу сиденье, рядом с которым никто не стоит, и встаёт у сидящего там человека над душой. Если такого места нет, он выходит из автобуса.
Каждый пассажир остаётся на своём месте до прибытия на нужную ему остановку. Стоящий пассажир остаётся стоять, даже если какое-то сиденье освободилось.
На каждой остановке из автобуса сначала выходят все пассажиры, которые собирались выйти на этой остановке, и только потом заходят новые.
Антон зашёл в автобус первым, он может сесть на любое сиденье и остаться на нём до конца поездки. Он хорошо знает, кто ещё будет ехать в автобусе, про каждого пассажира Антон знает, на какой остановке тот войдет в автобус и на какой выйдет. Помогите Антону выбрать место так, чтобы во время поездки у него как можно меньше суммарно стояли над душой.
В первой строке входных данных заданы три целых числа \(n\), \(m\) и \(k\) — количество остановок, количество сидений в автобусе и количество пассажиров, кроме Антона (\(2 \le n \le 10^9 , 1 \le m \le 2 \cdot 10^5 , 0 \le k \le 2 \cdot 10^5\) ).
В следующих \(k\) строках задано по 2 числа \(a_i\) и \(b_i\) , которые означают, что \(i\)-й пассажир собирается войти на \(a_i\)-й остановке и выйти на \(b_i\)-й (\(1 \le a_i < b_i \le n\)).
Если на одной остановке в автобус заходит несколько человек, они заходят в том порядке, в котором они перечислены во входных данных.
Выведите два числа на одной строке — минимальное суммарное время в минутах, в течение которого у Антона будут стоять над душой, и номер места, на которое для этого нужно сесть. Если таких мест несколько, выведите ближайшее ко входу.
10 2 3 1 10 3 9 7 10
3 2
Суровая зима в Санкт-Барнаурге длится \(n\) дней. Таня очень любит кататься на лыжах и часто выезжает на близлежащий горнолыжный курорт в Тбиатыкенте. Так, про некоторые дни последней зимы Таня помнит, что была в этот день на горнолыжном курорте — ведь она выкладывала своё фото со склона в тот день в социальной сети SkiForces. Про другие дни никакой информации нет.
Известно, что Таня всегда ездит на курорт одинаково: она выезжает утром некоторого дня, про- водит на курорте ровно \(k\) дней и возвращается вечером \(k\)-го дня поездки. При этом могло оказаться, что Таня снова поехала на курорт на следующий день после окончания предыдущей поездки. Те, дни, когда Таня не ездила на горнолыжный курорт, она провела в городе.
Зима закончилась, и подруги говорят Тане, что она слишком много катается на лыжах. Чтобы понять, так ли это, Таня хочет выяснить, каким могло быть максимальное количество зимних дней, которые провела в городе.
Таня могла первый раз поехать на курорт до начала зимы и могла закончить последнюю поездку после окончания зимы.
В первой строке находятся три целых положительных числа \(n, \ k\) и \(m\) — продолжительность зимы в днях, длительность одной поездки на горнолыжный курорт в днях и количество дней, в которые Таня точно была на курорте (\(1 \le k \le n \le 10^9 , 1 \le m \le 2 \cdot 10^5 , m \le n\)).
Во второй строке находятся \(m\) чисел \(d_1, \ d_2, \dots , d_m\) — номера дней в которые Таня точно была на курорте (\(1 \le d_i \le n\)). Каждый день перечислен не более одного раза.
Выведите единственное целое число — максимальное количество зимних дней, в которые Таня не была на горнолыжном курорте.
В первом примере Таня могла быть на курорте два раза: первый раз начиная за день до зимы и заканчивая в 1-й день зимы; второй раз начиная в последний день зимы и заканчивая в 1-й день после зимы.
Таким образом, Таня могла провести в городе второй и третий дни зимы.
Во втором примере Таня могла быть на курорте один раз, например, начиная со второго дня зимы и заканчивая пятым днём зимы. Таким образом, Таня могла провести в городе три дня — в первый, в шестой и в седьмой дни зимы.
4 2 2 1 4
2
7 4 3 4 3 5
3
5 1 5 5 4 3 2 1
0
13 3 6 3 5 6 8 9 11
4
Лёша готовит своего робота к тестированию IQ. В 2116 году тестирование IQ для роботов проходит следующим образом. Роботу демонстрируется прямоугольная таблица, содержащая \(n\) строк и \(m\) столбцов, каждая клетка которой покрашена в какой-либо цвет.
Затем экзаменатор \(q\) раз просит робота выполнить следующее задание. Экзаменатор указывает на некоторую клетку в таблице, а робот в качестве ответа должен выбрать две другие клетки. При этом должны выполняться следующие условия.
Лёша хочет научить своего робота справляться с заданием как можно лучше. Помогите ему запрограммировать робота.
В первой строке находятся целые числа \(n\) и \(m\) — количество строк и столбцов в таблице, соответственно (\(2 \le n, m \le 500 000; n \times m \le 10^6\) ).
Следующие \(n\) строк содержат по \(m\) строчных латинских букв — описание таблицы, \(j\)-й символ \(i\)-й из этих строк задает цвет клетки (\(i, \ j\)). Одинаковые буквы обозначают одинаковый цвет, а разные — разный.
В следующей строке находится число \(q\) — количество вопросов экзаменатора (\(1 \le q \le 200 000\)).
Следующие \(q\) строк содержат описание вопросов. В \(i\)-й из этих строк находятся два числа \(x_i\) и \(y_i\) — номер строки и столбца, на пересечении которых находится клетка, для которой требуется найти ответ (\(1 \le x_i \le n, 1 \le y_i \le m\)).
Для каждого вопроса выведите ответ в отдельной строке. Если невозможно найти пару клеток, удовлетворяющих всем условиям, выведите -1. Иначе выведите четыре числа \(r_1, \ c_1, \ r_2, \ c_2\) — описание двух выбранных клеток. Если оптимальных ответов несколько, выведите любой.
3 4 abbb baab babb 4 1 1 1 4 3 1 3 4
-1 1 1 2 4 3 2 2 1 2 4 3 2
Ученые работают на раскопках окаменелых останков древних существ на планете соседней звездной системы. В процессе исследования ученые пытаются понять, как именно цепочки ДНК различных существ составлялись из генов.
Цепочки ДНК всех исследуемых существ представляют собой последовательности нуклеотидов. Каждый нуклеотид обозначается строчной буквой латинского алфавита. Таким образом, цепочка ДНК представляет собой строку, составленную из строчных букв латинского алфавита.
Ген также представляет собой строку из строчных букв латинского алфавита. Известно, что в любом корректном наборе генов никакая строка не является префиксом другой строки.
Будем говорить, что цепочку ДНК \(d\) можно расшифровать с использованием набора генов \(G\), если d можно представить как результат последовательной записи одного или нескольких генов: \(d \ = \ g_1g_2 \dots g_k\), где \(g_i\) — гены из набора \(G\). Один и тот же ген может входить в расшифровку ДНК несколько раз.
Для обработки информации ученым требуется разработать компьютерную систему, которая будет поддерживать корректный набор генов \(G\) и массив цепочек ДНК существ \(D\). По мере анализа останков, ученые могут добавлять новый ген в набор \(G\) или добавлять новую цепочку ДНК в массив \(D\). Гарантируется, что ни в какой момент времени не существует двух генов, один из которых является префиксом другого.
После каждой операции ученые хотят знать, какие цепочки ДНК в массиве \(D\) можно расшифровать, используя текущий набор генов \(G\). После \(i\)-й операции система должна сообщать \(k_i\) — количество цепочек ДНК, находящихся в массиве \(D\), которые впервые стало можно расшифровать после \(i\)-й операции, а затем \(k_i\) чисел — номера этих цепочек. Результат очередной операции должен быть получен до того, как станет известна следующая операция.
Помогите ученым разработать такую систему.
В первой строке находится число \(n\) — количество операций, которые необходимо выполнить (\(1 \le n \le 100 000\)).
В следующих \(n\) строках находятся описания операций, \(i\)-я строка начинается с символа «+», если эта операция — добавление нового гена в набор \(G\), или с символа «?», если эта операция — добавление цепочки ДНК в конец массива \(D\). Далее через пробел находится строка \(x_i\) , состоящая из строчных латинских букв, которую необходимо использовать, чтобы получить строку \(s_i\) , которая задает добавляемый в этой операции ген или цепочку ДНК.
Для получения строки \(s_i\) из строки \(x_i\) , необходимо выполнить следующие действия. Если \(i \ = \ 1\), то \(s_i \ = \ x_i\) . Иначе пусть число впервые расшифрованных цепочек ДНК после предыдущей операции равно \(k_{i−1}\). Выполним \(k_{i−1}\) раз следующее действие: перенесем первый символ \(x_i\) в конец. Иначе говоря, выполним циклический сдвиг строки \(x_i\) влево на \(k_{i−1}\). Получившаяся строка равна \(s_i\) — ген или цепочка ДНК, которую необходимо добавить на \(i\)-й операции.
Все строки не пусты, суммарный размер строк во всех операциях не превышает \(10^6\)> .
Гарантируется, что ни в какой момент времени не существует двух генов, один из которых является префиксом другого.
Выведите \(n\) строк.
В \(i\)-й строке выведите сначала число \(k_i\) — количество цепочек ДНК, находящихся в массиве \(D\), которые впервые стало можно расшифровать после \(i\)-й операции, а затем \(k_i\) чисел — номера этих цепочек. Цепочки нумеруются с единицы в порядке добавления в массив \(D\). Номера цепочек в одной строке можно выводить в любом порядке.
В первых трех операциях \(s_1, s_2 \ и \ s_3\) совпадают с соответствующими строками во вводе. Поскольку \(k_3 \ = \ 1\), то для четвертой операции \(s_4\) получается из строки \(x_4\) = «dabdab» циклическим сдвигом влево на 1, таким образом, в четвертой операции в массив \(D\) добавляется строка \(s_4 \ = \ «abdabd»\). Наконец, \(k_4 \ = \ 0\), поэтому \(s_5 \ = \ x_5\).
5 ? abcabd + abc ? abcabc ? dabdab + abd
0 0 1 2 0 2 1 3