реализация

В пекарне «У Матроны» работает один пекарь, и за утро он должен испечь n заказов пирожков. Для каждого заказа известно время ti — сколько минут займёт его приготовление.

Пирожки нельзя долго держать на прилавке: клиент заберёт свой заказ горячим, только если время ожидания не превысило времени его приготовления. Иначе пирожки остынут — и клиент уйдёт расстроенным.

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

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

 

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

В первой строке — целое число n (1 ≤ n ≤ 105) — количество заказов.

Во второй строке — n целых чисел ti (1 ≤ ti ≤ 109), разделённых пробелами, — время приготовления каждого заказа.

 

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

Одно целое число — максимальное количество довольных клиентов.

Рамазан решил заняться серьезным бизнесом — выращиванием капусты.

Поле для выращивания капусты представляет собой бесконечное клетчатое поле. В каждой клетке поля может быть посажен один кочан капусты.

Рамазан засадил только часть поля. Он запланировал использовать несколько прямоугольных участков поля, причём оказалось, что некоторые из них могут пересекаться. Клетка поля принадлежит посадкам, если она лежит хотя бы в одном из прямоугольников.

Формально, Рамазан выбрал \(n\) прямоугольных участков \((x_i^{L}, y_i^{L}, x_i^{R}, y_i^{R})\) (\(x_i^{L} \leq x_i^{R}\), \(y_i^{L} \leq y_i^{R}\), \(1 \leq i \leq n\)). Клетка \((x, y)\) содержит капусту, если существует хотя бы один выбранный прямоугольник \(i\) (\(1 \leq i \leq n\)), такой что \(x_i^{L} \leq x \leq x_i^{R}\) и \(y_i^{L} \leq y \leq y_i^{R}\).

В прошлом Рамазан был программистом (и победителем), поэтому он решил использовать роботов с искусственным интеллектом для периодической обработки посадок. Один робот может обслуживать произвольный горизонтальный участок клеток \((x_1^{robot}, x_2^{robot}, y^{robot})\), то есть все клетки \((x, y)\), такие что \(x_1^{robot} \leq x \leq x_2^{robot}\) и \(y = y^{robot}\).

Важно, чтобы роботы ездили только по участкам с посадками. Он понял, что для минимизации количества роботов важно использовать горизонтальные участки, которые нельзя расширить. Рамазан будет использовать робота на участке клеток \((x_1^{robot}, x_2^{robot}, y^{robot})\), если:

• Все клетки \((x, y)\), такие что \(x_1^{robot} \leq x \leq x_2^{robot}\) и \(y = y^{robot}\) принадлежат посадкам;

• Клетка \((x_1^{robot} - 1, y^{robot})\) не принадлежит посадкам;

• Клетка \((x_2^{robot} + 1, y^{robot})\) не принадлежит посадкам.

Ваша задача собрать важную статистику о роботах, которые будут работать на плантации. Будем говорить, что пара \((x_1, x_2)\) обслуживается в ряду \(y\), если существует робот, работающий ровно на участке \((x_1, x_2, y)\).

• Найдите все пары \((x_1, x_2)\), которые обслуживаются в каком-нибудь ряду.

• Для каждой такой пары \((x_1, x_2)\) найдите количество рядов, в которых она обслуживается.

• Для каждой такой пары \((x_1, x_2)\) найдите максимальное количество подряд идущих рядов, в которых она обслуживается. Другими словами, найдите максимальное число \(k\), такое что существует отрезок \(k\) подряд идущих рядов \([y_1, y_2]\) (\(y_2 - y_1 + 1 = k\)), такой что для любого ряда \(y_1 \leq y \leq y_2\), пара \((x_1, x_2)\) обслуживается в ряду \(y\).

Формат входных данных
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число \(t\) (\(1 \leq t \leq 200\,000\)) — количество наборов входных данных. Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных дано единственное целое число \(n\) (\(1 \leq n \leq 200\,000\))  — количество выбранных прямоугольных участков.

В следующих \(n\) строках дано по четыре целых числа \(x_i^{L}\), \(y_i^{L}\), \(x_i^{R}\), \(y_i^{R}\) (\(1 \leq x_i^{L} \leq x_i^{R} \leq 10^9\), \(1 \leq y_i^{L} \leq y_i^{R} \leq 10^9\)) — описания выбранных прямоугольных участков.

Обозначим за \(N\) сумму \(n\) по всем наборам входных данных в одном тесте. Гарантируется, что \(N \leq 200\,000\).

Формат выходных данных
Для каждого набора входных данных сначала выведите единственное целое число \(p\) (\(p \geq 1\)) — количество пар \((x_1, x_2)\), которые обслуживаются в каком-нибудь ряду.

В следующих \(p\) строках выведите по четыре целых числа \(x_1\), \(x_2\), \(cnt\), \(k\) (\(1 \leq x_1 \leq x_2 \leq 10^9\), \(0 \leq cnt, k \leq 10^9\)). Число \(cnt\) должно быть равно количеству рядов, в которых обслуживается пара \((x_1, x_2)\). Число \(k\) должно быть равно максимальному количеству подряд идущих рядов, в которых обслуживается пара \((x_1, x_2)\).

Все пары \((x_1, x_2)\) должны быть различны. Каждая пара, которая обслуживается в каком-нибудь ряду, должна быть выведена ровно один раз. Можно вывести пары в произвольном порядке.

Система оценки
Для набора входных данных обозначим за \(w\) ширину поля, то есть \(w = \max\limits_{i=1}^{n} x_i^{R}\), за \(h\) высоту поля, то есть \(h = \max\limits_{i=1}^{n} y_i^{R}\).

• Если для теста ваше решение неправильно находит множество пар \((x_1, x_2)\), которые обслуживаются в каком-нибудь ряду, решение получает вердикт <<Неправильный ответ>>.

• Если во всех тестах подзадачи и необходимых подзадач решение

  • правильно находит множество, но не все \(cnt\) верны, оно получает \(50\%\) баллов за подзадачу.

  • правильно находит множество и все \(cnt\), но не все \(k\) верны, оно получает \(75\%\) баллов за подзадачу.

  • правильно находит множество, все \(cnt\) и все \(k\), оно получает \(100\%\) баллов за подзадачу.

Обратите внимание, что для получения частичных баллов за подзадачу, все равно необходимо вывести какие-нибудь значения \(cnt\) и \(k\) для каждой пары \((x_1, x_2)\), но не обязательно верные.

В первом наборе входных данных будут использоваться роботы на участках \((2, 3, 2)\), \((2, 4, 3)\), \((3, 4, 4)\). Таким образом, пары \((2, 3)\), \((2, 4)\), \((3, 4)\) обслуживаются в каком-нибудь ряду, причем каждая из них обслуживается ровно в одном ряду.

Во втором наборе входных данных будут использоваться роботы на участках \((2, 2, 1)\), \((2, 4, 2)\), \((2, 2, 3)\). Таким образом, пары \((2, 2)\), \((2, 4)\) обслуживаются в каком-нибудь ряду. Пара \((2, 2)\) обслуживается в рядах \(1, 3\), пара \((2, 4)\) обслуживается ряду \(2\).

Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0» и «1». Обрадованный этим подарком, он тут же начал эту строку изучать — искать в ней гармоничные части. Для начала Васю интересует только количество различных непустых гармоничных подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а строка «13» — нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых символов с начала и с конца.

Формат входных данных
В первой строке дано одно число n — длина подарка (1 ≤ n ≤ 2 · 10⁵ ). Во второй строке дана строка s длины n — Васин подарок. Гарантируется, что s состоит только из нулей и единиц.
Формат выходных данных
Выведите единственное число — количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64- битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.

Для поиска полезных ископаемых ученые разработали специальный сканер.

Представим область для поисков как таблицу из \(k\) строк и \(n\) столбцов. Нумерация строк идет от \(1\) до \(k\) сверху вниз, нумерация столбцов от \(1\) до \(n\) слева направо. В каждой клетке таблицы могут находиться полезные ископаемые.

Сканер работает следующим образом: он может быть запущен в столбце \(p\) и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца \(p\), верхние \(k-1\) клетку столбца \(p-1\), верхние \(k-2\) клетки столбца \(p-2\), и так далее. На рисунке показана зона сканирования для поля с \(k = 3\), \(n=5\) и всех значений \(p\).

Вам даны значения, которые вернул сканер для всех \(p\), обозначим за \(b_p\) значение в столбце \(p\). Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения \([2, 1, 2, 3, 2]\), то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число \(10^9+7\). Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести \(0\).

Формат входных данных
В первой строке даны два числа \(n\), \(k\) — количество столбцов и строк, соответственно (\(1 \le n \le 200\), \(1 \le k \le 7\)).

Во второй строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) — значения, которые вернул сканер (\(0 \le b_i \le k^2\)).

Формат выходных данных
Выведите единственное число — остаток от деления количества различных корректных таблиц на \(10^9 + 7\).

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(m\) — количество элементов в первом и во втором массиве, соответственно (\(1 \leqslant n, m \leqslant 100\,000\)).

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

 

Головоломка состоит из \(n\) треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:

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

Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.

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

Формат входных данных
В первой строке дано одно целое число \(t\) — номер теста.

В второй строке дано одно целое число \(n\) — количество треугольников в головоломке (\(4 \le n \le 30\)).

В следующих \(n\) строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты целые и по модулю не превышают \(10^5\). Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

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

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

Замечание
В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными \(1\). Из любых четырех треугольников можно собрать один.

Рома, Саша и Алиса решили модернизировать знаменитый алгоритм шифрования RSA. Они считают, что ограничение на модуль \(n\), используемый в RSA, должно быть произведением двух различных простых чисел, избыточно. Вместо этого они планируют использовать \(n\), которое представляет собой произведение степеней \(k\) двух различных простых чисел: \(n = p^kq^k\).

Будем называть нетривиальным разложение числа \(n\) на множители, такое, что множителей хотя бы два, и каждый из них строго больше \(1\). Оказалось, что в случае \(n = p^kq^k\) у числа \(n\) может быть несколько различных нетривиальных разложений на множители. Например, \(100 = 2^2 5^2\) имеет восемь нетривиальных разложений: \(100 = 2\cdot 50\), \(100 = 2\cdot2\cdot25\), \(100 = 2\cdot2\cdot5\cdot5\), \(100=2\cdot5\cdot10\), \(100 = 4\cdot25\), \(100=4\cdot5\cdot5\), \(100=5\cdot20\) и \(100=10\cdot10\).

Теперь ребята задаются вопросом: пусть \(n = p^kq^k\), сколько существует различных нетривиальных разложений \(n\) на множители?

Формат входных данных
На вход подается одно целое число \(n\) (\(6 \le n \le 10^{18}\), гарантируется, что \(n=p^kq^k\) для двух различных \(p\) и \(q\) для целого \(k > 0\)).

Формат выходных данных
Выведите одно число "— количество нетривиальных разложений \(n\) на множители.

У Кати есть веревочка длиной \(n\) сантиметров.

Катя \(k\) раз выполняет следующую операцию: выбирает самую длинную веревочку из тех, что у неё есть, и разрезает ее на две веревочки. Катя каждый раз разрезает веревочку на две веревочки примерно равной длины, длина каждой из получившихся веревочек измеряется целым числом сантиметров. А именно: если длина веревочки, которую разрезает Катя, четная и равна \(2u\), то после разрезания получается две веревочки длины \(u\), а если она нечетная и равна \(2v+1\), то после разрезания получаются веревочки длиной \(v\) и \(v+1\).

Когда Катя закончила разрезать веревочку, она разложила получившиеся веревочки в порядке невозрастания длины и хочет ответить на \(q\) запросов: какая длина \(t_i\)-й веревочки в получившемся порядке.

Например, пусть \(n=100\) и \(k=5\). Тогда у Кати последовательно есть наборы веревочек следующей длины: \([100]\), \([50, 50]\), \([50, 25, 25]\), \([25, 25, 25, 25]\), \([25, 25, 25, 13, 12]\), \([25, 25, 13, 13, 12, 12]\).

Формат входных данных
На первой строке ввода дано целое число \(n\) (\(2 \le n \le 10^{18}\)).

На второй строке дано целое число \(k\) (\(1 \le k \le n-1\)).

На третьей строке дано целое число \(q\) (\(1 \le q \le k + 1\), \(1 \le q \le 5000\)).

На четвертой строке даны \(q\) целых чисел \(t_1, t_2, \ldots, t_q\) (\(1 \le t_1 < t_2 < \ldots < t_q \le k + 1\)).

Формат выходных данных
Выведите \(q\) чисел, \(i\)-е из выведенных чисел должно быть равно длине \(t_i\)-й по невозрастанию длине веревочки, которая в итоге есть у Кати.

В реальных компьютерных сетях также используется понятие максимальной единицы передачи (MTU, maximum transmission unit) - размер блока данных, который может быть передан на отрезке сети между двумя устройствами. Этот размер зависит от ограничений используемой технологии
передачи данных на нижнем уровне.
В данной задаче требуется составить оптимальный план передачи пакетов с учётом MTU между разными маршрутизаторами и вычислить минимальное время передачи на его основе.
Нужно иметь в виду, что окно передачи работает по "скользящему" принципу, то есть после получения подтверждения доставки первых байтов окна оно сдвигается вправо на размер доставленной информации.

Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), время передачи до следующего маршрутизатора в миллисекундах и MTU в байтах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.

Выходные данные
Минимальное время передачи в миллисекундах.
Примечание: считать, что между получением каждого пакета и отправкой подтверждения с конечного устройства всегда проходит 1 мс.
Примечание 2: считать, если объём данных, который требуется отправить с одного маршрутизатора на другой, превышает MTU, то данные делятся на пакеты, равные максимальной единице передачи или меньше, и отправляются с задержкой в 1 мс.
В рамках данной задачи считать, что потери отсутствуют и все отправленные пакеты достигают получателя, а также что размер окна фиксированный и составляет 10240 байт. Также следует пренебречь временем передачи данных между конечными узлами и ближайшими
маршрутизаторами и размером пакета ACK (считать, что он меньше любого MTU).

Примеры

№	Входные данные	Выходные данные
1	5 3 10.0.0.0 8 2 10 100 20.0.0.0 8 3 10 100 10.0.0.0 8 5 10 10240 1 10.0.0.0 8 4 10 100 1 30.0.0.0 8 4 10 100 1 40.0.0.0 8 1 10 100 1 10.0.0.0 8 4 20 10240 40.1.1.1 1 10.1.1.1 4 102400	410

Примечание
Если отправлять пакеты с 1-го маршрутизатора на 5-й, то время передачи каждых 10240 байт с учётом подтверждения займёт 41 мс. Если же отправлять с 1-го через 2-й, то 10240 байт окна передачи будут делиться на 103 блока и суммарное время доставки для первого окна
увеличится до 133 мс, а для всего объёма данных - более 1000 мс.

Для передачи пакетов в глобальной компьютерной сети используются специальные устройства - маршрутизаторы. Они подключены к нескольким линиям связи и на основе содержащихся в их памяти таблиц маршрутизации определяют, по какому из направлений передавать приходящие пакеты.
IPv4 - 4-я и первая, получившая широкое распространение, версия протокола IP (Internet Protocol).
Адреса в этой версии представляют собой 4 октета - блока по 8 бит. В человекочитаемом представлении адреса принято записывать в форме 4-х десятичных чисел от 0 до 255, разделённых точками.
Поскольку маршрутизатор имеет несколько интерфейсов (физических разъёмов, куда подключены кабели связи), в таблице маршрутизации задано соответствие каждого интерфейса той или иной сети. Сеть определяется парой из IP-адреса и битовой маски (в которой N старших бит заполнены единицами, а 32-N младших заполнены нулями). Для проверки того, можно ли маршрутизировать
пакет в какую-либо сеть, битовая маска применяется к адресу сети и адресу узла назначения из пакета с помощью побитового И. Если получившийся результат совпадает, то пакет можно отправить на соответствующий интерфейс.
Протокол управления передачей TCP (transmission control protocol) - протокол более высокого уровня по сравнению с IP, предназначенный для доставки данных в неизменном виде. Для решения этой задачи в нём применяется ряд принципов, один из которых - подтверждение
получения данных. Для подтверждения от получателя к отправителю направляется специальный пакет с признаком ACK, в котором указан диапазон полученных байтов.
При этом для исключения перегрузок сети при передаче больших объёмов данных применяются "окна" передачи. Окном называется максимальный объём данных, который может быть отправлен от отправителя получателю без подтверждения получения. По мере подтверждения получения данных окно смещается вправо и отправляются новые данные.

Входные данные
В первой строке записано натуральное число N, не превышающее 100 - количество маршрутизаторов. Далее записано N таблиц маршрутизации в следующем формате: в первой строке число N1 - количество маршрутов в таблице, далее N1 строк, где через пробел
указаны адрес сети, маска (целое число от 1 до 32), номер маршрутизатора, куда будет отправлен пакет (номера считаются с 1 по порядку описания), и время передачи до следующего маршрутизатора в миллисекундах.
После описания таблиц маршрутизации в следующей строке записаны через пробел адрес узла-отправителя, номер маршрутизатора, к которому он подключён, адрес узла-получателя, номер маршрутизатора, к которому подключён получатель, и объём данных (в байтах), который требуется передать.

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

Примечание
102400 = 10240*10, значит, для передачи данных потребуется 10 итераций (сдвигов окна передачи). Каждые 10 Кбайт будут проходить следующую цепочку: отправка с первого маршрутизатора на второй - 10мс, затем со 2-го на 4-й ещё 10 мс, затем 1 мс задержки на
отправку подтверждения и сама передача подтверждения напрямую с 4-го маршрутизатора на 1-й - ещё 10 мс. Таким образом, на передачу каждых 10 Кбайт будет уходить 31 мс.
 

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

По заданным \(n\) и \(k\) постройте множество из \(k\) различных натуральных чисел с суммой \(n\), которое является генератором квадратов, либо выясните, что такого нет.

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

 

Миссия космолёта “Юрий Гагарин” определена - посещение трех звёздных систем в глубоком космосе. Эти звёзды находятся на Земном небосводе в созвездии Орион:

•  звезда Беллатрикс (250 световых лет от Земли)
•  звезда Бетельгейзе (643 световых года от Земли)
•  парная звёздная система Ригель (773 световых года от Земли)

Маршрут путешествия должен предусматривать посещение их в порядке удаления от Земли. Однако гиперсветовой прыжок не может пока быть выполнен с приемлемой точностью на расстояние 20 и более световых лет. Спланированная трасса полёта должна состоять из серии
прыжков, каждый прыжок менее безопасного расстояния. Вторым ограничением является то, что промежуточные точки трассы должны находиться в окрестности массивного тела, т.е. звезды. Такие звёзды в навигации называются контрольными пунктами.
Необходимо учитывать, что управление выходом из гиперпространства невозможно без существенного искривления его в точке назначения гравитационным воздействием звезды контрольного пункта. Эта особенность налагает дополнительное ограничение на каждый
выполняемый гиперпрыжок: траектория прыжка не должна проходить меньше одного светового года от звёздной системы, не являющейся контрольным пунктом.
Задача : построить трассу в трёхмерном пространстве с минимально возможным количеством гиперпрыжков, при соблюдении указанных выше ограничений. Если таких трасс несколько, то следует выбрать ту, в которой суммарная длина трассы меньше.

Входные данные
Первая строка : натуральное число N - количество звезд, внесённых в лоцию (от 3 до 100).
Далее N строк, каждая содержит три целых числа, записанных через пробел: координаты X Y Z, заданные в световых годах. Все значения координат не превышают 10000. Точка старта (0 0 0) - звезда Солнце - не указана в лоции.
Три посещаемые звёздные системы находятся в лоции в порядке ожидаемого посещения, в строках с номерами 1, 2 и 3.

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

 

Примеры

№	Входные данные	Выходные данные
1	3 10 10 10 20 20 20 30 30 30	3 51.962 1 2 3
2	5 20 0 0 10 0 0 40 0 0 30 0 0 50 0 0	4 40.000 2 1 4 3

Художник Тюбик учит Незнайку рисовать. Он дал ему сетку с H строками и W столбцами. Все клетки сетки изначально выкрашены в белый цвет. Тюбик попросил Незнайку закрасить N из этих ячеек в черный цвет. I-я (1<=i<=N) ячейка, которую закрасил Незнайка, является ячейкой в a_i-й строке и b_i -м столбце. Для каждого целого числа j (0<=j<=9), определите сколько в сетке подпрямоугольников размером 3×3 содержит ровно j черных ячеек после того, как Незнайка закрасил N ячеек?

Входные данные
В первой строке заданы 3 целых числа: H, W (3<=H,W<=10⁹) и N (0<=N<=min(10⁵,H×W)). Далее идут N строк по 2 числа в каждом a_i (1<=a_i<=H) и b_i (1<=b_i<=W), 1<=i<=N, (a_i,b_i)≠(a_j,b_j), i ≠ j.

Выходные данные
Выведите 10 строк. В (j + 1)-й (0<=j<=9) строке должно быть указано количество подпрямоугольников размером 3 × 3 сетки, содержащей ровно j черных ячеек.
 

 

Примеры

№	Входные данные	Выходные данные
1	4 5 8 1 1 1 4 1 5 2 3 3 1 3 2 3 4 4 4	0 0 0 2 4 0 0 0 0 0
2	10 10 20 1 1 1 4 1 9 2 5 3 10 4 2 4 7 5 9 6 4 6 6 6 7 7 1 7 3 7 7 8 1 8 5 8 10 9 2 10 4 10 9	4 26 22 10 2 0 0 0 0 0
3	1000000000 1000000000 0	999999996000000004 0 0 0 0 0 0 0 0 0

 

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

Каждый день на планете Кирнес состоит из h часов. Каждый час состоит из m минут, причём m обязательно чётное. Известно, что на данный момент n товарных поездов отправляются с вокзала ежедневно по разу в день: i-й поезд отправляется в h_i часов и m_i минут.

Поскольку между Кирнесом и Сириусом активный пассажиропоток, то было решено пустить ровно по 2 электрички каждый час. Более того, по всем транспортным нормам необходимо, чтобы промежутки времени между отправлением электричек были равны \( {m \over 2}\)минутам. То есть для любой электрички предыдущая должна была отправиться ровно за \({m \over 2}\) минут до неё, а следующая должна отправиться ровно через \({m \over 2}\) минут после. Кроме этого, электричку надо подать на платформу за k минут до отправки. Пока электричка стоит на платформе, с неё не могут отправляться товарные поезда. При этом разрешается подавать электричку на платформу в ту же самую минуту, когда с неё отправляется предыдущий товарный поезд. А также поезда отправляются настолько быстро, что разрешено отправить электричку и следующий за ней товарный поезд в одну и ту же минуту.

Поскольку электрички отправляются каждый день с интервалом в \({m \over 2}\) минут, то первая электричка отправится с вокзала в 0 часов и t минут, причем t < \({m \over 2}\) . Обратите внимание, что если t < k, то платформа вокзала будет занята и последние k − t минут предыдущего дня.

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

Составление такого расписания оказалось трудной задачей для правительства планеты, поэтому это было поручено вам. Найдите такое время t для запуска первой электрички, чтобы количество товарных поездов, которые потребуется отменить, было минимальным.

Формат входных данных
Первая строка содержит четыре целых числа n, h, m, k (1 ≤ n ≤ 100 000, 1 ≤ h ≤ 10⁹, 2 ≤ m ≤ 10⁹, 1 ≤ k ≤ \({m \over 2}\)) — число товарных поездов, количество часов и минут на планете Кирнес, а также время, которое электричка стоит у платформы. Гарантируется, что число минут m четное.
В следующих n строках вводится по два целых числа hi и mi (0 ≤ h_i < h, 0 ≤ m_i < m) — время отправления i-го поезда, часы и минуты соответственно. Гарантируется, что все товарные поезда отправляются в разное время.

Формат выходных данных
Выведите два числа: минимальное количество отмененных товарных поездов и t — время запуска первой за день электрички в минутах.
Во второй строке через пробел выведите номера отменяемых товарных поездов.

Примеры

№	Входные данные	Выходные данные
1	2 24 60 15 16 0 17 15	0 0
2	2 24 60 16 16 0 17 15	1 0 2

Замечание

В первом примере первую электричку надо отправить в 0:00. Тогда поезд в 16:00 отправится сразу после электрички, а электричку в 17:30 надо будет подать на платформу сразу после отправления товарного поезда в 17:15.
Во втором примере подать электричку на платформу надо за 16 минут до отправления. Сделать это без отмены какого-то товарного поезда не получится: если отправлять электричку в t ∈ [1, 15], то в 16:00 электричка уже должна быть на платформе, а с нее в это время отправляется первый товарный поезд. Если t ∈ {0, [16, 29]}, то второй товарный поезд в 17:15 не сможет уехать с платформы, потому что на ней уже будет стоять следующая электричка.
Если отменить второй поезд, то можно выбрать t = 0, тогда поезда будут отправляться в 0 и 30 минут каждый час, а столкновения с первым товарным поездом не будет. Также можно отменить только первый поезд и выбрать, например, t = 13.
 

Федот — дизайнер, ему поручена ответственная работа по художественной укладке плитки черного и белого цвета. Его последнее задание — уложить черные и белые плитки в квадрате n × n.

Федот любит свою работу и всегда тщательно готовится к каждому проекту. Федот считает, что два квадрата похожи, если один из них можно получить из другого несколько раз заменив цвета в какой-то строке или столбце на противоположные. Федот заметил, что клиенты никогда не смотрят на всю работу целиком, обычно поле их зрения ограничивается квадратом k × k. Для оценки эскизов он ввел специальную величину — сложность. Она равна числу пар не похожих друг на друга квадратов k × k, которые встречаются в картине.

Методом проб и ошибок Федот установил, что клиентам нравятся картины определенной сложности. Слишком большая сложность похожа на хаос, а слишком малая навевает скуку, считает Федот.

Прежде чем класть плитку, Федот подготовил несколько эскизов. Помогите Федоту вычислить их сложность.

Входные данные
Первая строка входного файла содержит два целых числа n и k (1 ≤ k ≤ n ≤ 500). Следуюшие n строк содержат описание эскиза. Каждая из них имеет длину n и состоит из символов b и w, которые соответствуют белому и черному цветам плиток.

Выходные данные
В первой строке выходного файла выведите одно целое число q — сложность картины.

Примеры

№	Входные данные	Выходные данные
1	2 1 bw wb	0
2	3 2 bwb wbb bbw	3

Есть озеро, рядом с которым хотят построить дом. Архитектурный проект (форма дома) уже утверждён, можно только выбрать расположение дома так, чтобы он оказался рядом с озером. Желательно выбрать расположение дома рядом с озером так, чтобы у как можно большего числа жителей дома окна выходили на озеро, то есть чтобы длина общей границы дома и озера была максимальной.

План дома и озера задан в виде изображения на клетчатой бумаге, в котором отмечены клетки, принадлежащие дому и озеру. Первая строка входных данных содержит число N – количество строк в плане дома и озера. Вторая строка входных данных содержит число M – количество столбцов в плане дома и озера.

Следующие N строк содержат по M символов – план дома. Символ «.» в этих строках обозначает пустую клетку, символ «H» обозначает» обозначает клетку дома. План дома является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая дому. Следующие N строк по M символов в каждой содержат план озера, в этих строках символ «.» обозначает пустую клетку, символ «W» обозначает клетку, занятую озером. План» обозначает клетку, занятую озером. План озера является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая озеру.

Программа должна вывести одно число – максимальное значение длины общей границы дома и озера, измеряемую в сторонах клетки. При расположении дома рядом с озером его можно передвигать, но нельзя делать повороты и отражения. Вокруг озера есть неограниченное свободное пространство, дом может располагаться с любой стороны от озера.
Числа N и M являются целыми, положительными, не превосходят 15.
 

Ввод	Вывод	Примечание
5 6 ...... .HHHH. .HHHH. .HHHH. ...... ..WWW. ..WWW. ..WWW. ..WWW. ..WWW.	3	. . . . W W W H H H H W W W H H H H W W W H H H H W W W       . . . . W W W
5 7 ...HHH. .H...H. .H.HHH. .H.H... .HHH... ....... ..WWWWW WWW...W W.W...W ..W....	11

Ни для кого не секрет, что Дед Мороз передвигается на особом транспортном средстве, принцип которого известен только самым приближенным зайцам Дедам Мороза. Однако, зайцы немного слабы в составлении маршрутов, и вам придется помочь им.

Принцип работы транспортного средства Деда Мороза(в дальнейшем ПепеЛАЦ(Пепе Летающий агрегат Цвайхандер)) такой:
на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (−1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, −3).
Деду Морозу необходимо добраться из точки (x1, y1) в точку (x2, y2). Помогите зайцам Деда Мороза составить маршрут, чтобы ему меньше пришлось ходить по заснеженному лесу.
Поскольку перемещения мгновенные и абсолютно бесплатные(магия же), то минимизировать количество перемещений не надо.

Формат входного файла
Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по
абсолютной величине.

Формат выходного файла
Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).
Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке. Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.

Примеры

Ввод	Вывод
3 1 3 -3	-A    +B +B
0 0 3 0	-B +B

 (с) Павел Колодкин, 12И