Алгоритмы поиска

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

На доске выписано две последовательности из \(n\) различных целых чисел: \(A = [a_1, a_2, \ldots, a_n]\) и \(B = [b_1, b_2, \ldots, b_n]\).

Составим из них \(n^2\) дробей вида \(a_i / b_j\), сократим каждую дробь и отсортируем их по неубыванию.

Задано число \(q\) и \(q\) целых чисел \(c_1, c_2, \ldots, c_q\). Для каждого \(j\) следует выдать \(c_j\)-ю в неубывающем порядке дробь из получившихся.

Формат входных данных
На первой строке ввода находятся числа \(n\) и \(q\) (\(1 \le n \le 10^5\), \(1 \le q \le 10^5\), \(q \le n^2\)).

Дополнительно выполняется неравенство \(n\cdot q \le 10^5\).

На второй строке ввода находятся \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)).

На третьей строке ввода находятся \(n\) различных целых чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le 10^6\)).

На четвертой строке ввода находятся \(q\) различных целых чисел \(c_1, c_2, \ldots, c_q\) (\(1 \le c_i \le n^2\)).

Формат выходных данных
Выведите \(q\) строк. На \(j\)-й строке выведите \(c_j\)-ю по неубыванию дробь среди получившихся. Дробь \(p/q\) следует выводить в формате <<p q>>, дробь должна быть несократимой.

Замечание
В примере дроби исходно равны: \[\left[ \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \frac{3}{5}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \frac{2}{5} \right],\] после сокращения \[\left[ \frac{3}{2}, \frac{1}{1}, \frac{3}{4}, \frac{3}{5}, \frac{2}{1}, \frac{4}{3}, \frac{1}{1}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{1}, \frac{2}{3}, \frac{1}{2}, \frac{2}{5} \right],\] после сортировки \[\left[ \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{2}{1} \right].\]

В этой задаче Вам требуется найти максимальную по длине подстроку данной строки, такую что каждый символ встречается в ней не более k раз.

Входные данные
В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

Выходные данные
В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.

Примеры

№	Входные данные	Выходные данные
1	3 1 abb	2 1
2	5 2 ababa	4 1

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге ai страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

Томми читает уже m дней подряд. Книги он читает строго по порядку, начиная с книги с номером 1.  Каждый день он записывает на доску общее число страниц, которые прочитал к текущему дню.

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·10⁵) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a1, a2, ... an (1 <= a1<= 10¹⁰), где ai равно количеству страниц в i-й книге. В третьей строке следует последовательность d1, d2, ... dm (1 <= dj <= a1 + a2 +...+ an), где dj равно общему числу страниц, прочитанных Томми к j-му дню. Все dj заданы в порядке возрастания.

Выходные данные

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= ak), на которой остановился Томми в текущий день.

 

Примеры

№	Входные данные	Выходные данные
1	3 6 10 15 12 1 9 12 13 15 17	1 1 1 9 2 2 2 3 2 5 2 7
2	2 3 5 10000000000 5 6 9999999999	1 5 2 1 2 9999999994

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

Для достижения эстетического совершенства высаживаемого ряда деревьев требуется, чтобы среди любых P подряд идущих деревьев все деревья были разных видов. Если количество деревьев в ряду меньше P, то все они должны быть различны.

Требуется написать программу, которая находит максимальное количество деревьев в эстетически совершенном ряду, посаженном из закупленных саженцев.

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

Выходные данные
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

 

Примеры

№	Входные данные	Выходные данные
1	3 3 1 200  1	4

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

Примеры

№	Входные данные	Выходные данные
1	2.0000000000	1.000000000
2	18.0000000000	4.000000000

Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — d_t , здоровье — h единиц.

Бой происходит в пошаговом режиме, пока с обеих сторон есть живые солдаты. Каждый шаг боя представляет собой одновременный выстрел всех живых солдат с обеих сторон. Каждый солдат может атаковать любого противника, но только одного. Несколько солдат с одной стороны могут атаковать одного и того же вражеского солдата. Здоровье солдата уменьшается на суммарную силу атаки солдат, атакующих его в течение этого хода. Если здоровье солдата в конце хода стало меньше или равно нулю, он погибает.

Ваша задача — уничтожить армию неприятеля, задействовав минимальное число штурмовиков, вне зависимости от действий противника, либо определить, что уничтожить вражескую армию не получится.

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*10⁵),  d_e, d_t , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( d_e, d_t , h <= 10⁹). В следующей строке задано n натуральных чисел a_i — число единиц здоровья i-го солдата армии противника (a_i <= 10⁹).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.
 

Ввод	Вывод
3 3 1 1 2 1 2 3	3
4 10 2 1 2 1 2 1 2	5
3 1 1 2 5 1 2 3	-1

Учительница литературы просит помечать тавтологии — когда одно и то же слово стоит подряд два раза: «был был», «очень очень».

Напиши программу, которая в тексте заключает каждую такую пару в квадратные скобки.

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Слово — это последовательность букв (кириллица или латиница), цифр и подчёркиваний.

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

Тот же текст, но каждое повторение подряд двух одинаковых слов обёрнуто в квадратные скобки: [слово слово]. Пунктуация и все остальные символы сохраняются.

Примечание

Регистр при сравнении слов не учитывается: Очень очень — тоже повтор. В выводе регистр оригинала сохраняется.