Динамическое программирование

Последовательность чисел монотонно убывающая если для любого i элемента (кроме последнего )выполняется A_i > A_i+1. Последовательность чисел монотонно возрастающая если для любого i элемента (кроме последнего )выполняется A_i < A_i+1. Последовательность монотонная если она или монотонно убывающая или монотонно возрастающая. Дана последовательность A_i из n чисел. Каждый элемент последовательности можно увеличивать или уменьшать. Требуется изменить последовательность так что бы в ней содержалось K монотонных непересекающихся последовательностей. (один элемент тоже последовательность). Т.к. преобразований бесконечно много то нужно найти такое преобразование чтобы сумма разностей по модулю конечного значения A_i и начального значения A_i была минимальна.

Входные данные
В первой строчке n,k n- количество элементов в последовательности, k сколько должно быть монотонных последовательностей. Во второй строчке n чисел через пробел - сама последовательность(каждое число по модулю меньше 20,000,000)

Выходные данные
Одно число, ответ на задачу.

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.

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

В первой строке через пробел заданы два целых числа M и N (1 <= N < M <= 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 <= L, H <= 101). Ступеньки нумеруются снизу вверх.

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

В выходной файл выведите единственное число - ответ на задачу.

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

Формат выходных данных
Выведите одно целое число — минимальное количество пар знакомых людей.

Замечание
Рассмотрим первый пример из условия. Возможны следующие варианты:

1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).

2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).
Возможные примеры расположения моста                                                                   Невозможное расположение моста


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

Формат входных данных
Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 10⁶) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x₁ < x₂ < … < x_N и y₁ = y_N = 0, а также, что точки A и B принадлежат ломаной.

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

Король Полигонии Трианг IV помешан на реформах. Чтобы войти в мировую историю, он решил провести территориальную реформу в своей стране. Страна Полигония имеет форму простого многоугольника, то есть ее граница не имеет самопересечений и самокасаний. В Полигонии большую роль играют внутренние диагонали — отрезки, соединяющие вершины государственной границы и полностью проходящие по территории страны, не касаясь границы. При этом форма Полигонии такова, что никакие две внутренние диагонали не лежат на одной прямой.

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

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

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

В первой строке входных данных задается число N (3 ≤ N ≤ 20) — количество вершин многоугольника, образующего границу Полигонии. В следующих N строках находятся по 2 целых числа, по абсолютной величине не превосходящих 10 000 — координаты вершин в порядке обхода многоугольника против часовой стрелки. Гарантируется, что никакие три последовательные вершины многоугольника не лежат на одной прямой, и он не имеет самопересечений и самокасаний. Также гарантируется, что никакие две диагонали, содержащиеся внутри многоугольника, не лежат на одной прямой.

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

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

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

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

Если искомых разбиений несколько, выведите любое из них.

 

Примеры

№	Входные данные	Выходные данные	Рисунок к тесту
1	4 0 0 1 0 1 1 0 1	2 1 1 1 0 0
2	10 -6 0 0 2 6 0 3 3 6 4 2 4 0 6 -2 4 -6 4 -3 3	4 3 2 4 -2 4 0 2 3 3 -3 3 0 2

Костя и Женя — создатели группы <<Бумага>> — после выпуска легендарного альбома решили создать новое музыкальное объединение <<дневные грузчики>>, для этого им нужно найти двух новых людей.

Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как <<дневные грузчики>> занимаются современным искусством,  музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.

Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!

Формат входных данных
В первой строке вам дано два числа \(n, q\) (\(2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6\)) — количество людей, которые пришли на кастинг, а также количество дней кастинга.

Во второй строке вам даны \(n\) чисел \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \leqslant a_i \leqslant n\)) — рост каждого из кандидатов.

Также гарантируется, что все \(a_i\) различны.

В следующих \(q\) строках даны по \(2\) числа \(l_i, r_i\) (\(1 \leqslant l_i < r_i \leqslant n\)) — отрезок людей для рассмотрения в \(i\)-й день кастинга.

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

Примечание
В первом примере минимальная разность на отрезке \([1, 2]\) составляет \(2\) (\(3 - 1 = 2\)), на отрезке \([2, 3]\) – \(1\), на отрезке \([1, 3]\) также \(1\).

В третьем примере минимальную разность на отрезке \([4, 6]\) составляют числа \(3, 5\) (\(5 - 3 = 2\)). На отрезке \([1, 2]\) минимальную разность имеют числа \(2, 6\) (\(6 - 2 = 0\)). На отрезке \([3, 6]\) минимальную разность имеют числа \(1, 3\) (\(3 - 1 = 2\)). На отрезке \([1, 3]\) минимальную разность образуют числа \(1, 2\) (\(2 - 1 = 1\)).

Знаменитый писатель Велепин очень продуктивен. Совсем недавно он подписал контракт с известным изданием, и теперь за \(i\)-й год ему нужно написать \(k_i\) романов. Для него это вообще не проблема: он может сколько угодно писать о самураях, космосе, пустоте, насекомых и оборотнях.

У него есть \(n\) постоянных читателей, каждый из которых в \(i\)-й год прочитает один из \(k_i\) романов, выпущенных Велепиным. Читатели очень любят обсуждать новинки, поэтому \(j\)-й из них будет доволен в течение года, если такой же роман, как и он, прочитают как минимум \(a_j\) человек, включая его самого.

Издание, с которым подписал контракт Велепин, очень современно: у него есть возможность контролировать, какое произведение прочитает каждый из поклонников. Оно не хочет издавать романы просто так, поэтому хотя бы один экземпляр каждого романа должен попасть в руки читателя. Издание надеется выиграть награду <<Издание \(q\)-летия>>, поэтому отдел маркетинга хочет узнать, какое максимальное количество постоянных читателей можно сделать довольными в течение каждого года, оптимально распределяя романы между ними. Так как в отделе маркетинга нет никого, кто мог бы это сделать, он обратился к вам за помощью.

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

Во второй строке дано \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) \((1 \leqslant a_j \leqslant n)\) — количество людей, которые должны читать тот же роман, что и \(j\)-й, чтобы он был доволен.

В третьей строке дано одно целое число \(q\) (\(1 \leqslant q \leqslant 300\,000\)) — количество лет, которые нужно проанализировать.

В каждой из следующих \(q\) строк дано по одному целому числу \(k_i\) \((2 \leqslant k_i \leqslant n)\) — количество романов, которые Велепин должен написать в \(i\)-й год.

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

В первом примере в первый год оптимальным является разделение \(1, 1, 1, 2, 2\) (первый роман читают первые три человека, а два последних — второй). Во второй год оптимальным решением является \(1, 1, 2, 2, 3\) (первый роман читает первый и второй человек, второй роман читает третий и четвертый человек, третий роман читает пятый человек). В третий год оптимальным будет разбиение \(1, 2, 2, 4, 3\). Соответственно количество довольных людей по годам будет \(5, 5, 3\).

Зимой обитателям Московского зоопарка очень скучно, в частности, это касается горилл. Вы решили развлечь их и принесли в зоопарк перестановку \(p\) длины \(n\).

Напомним, что перестановкой длины \(n\) называется последовательность целых чисел от \(1\) до \(n\), в которой каждое такое число встречается ровно один раз. Например, последовательности \([3, 1, 2]\) и \([1, 4, 2, 3]\) являются перестановками, а последовательности \([3, 4]\) и \([1, 2, 2, 3]\) нет.

У горилл помимо вашей оказалась и своя перестановка \(q\) длины \(n\). Они предложили вам посчитать количество пар целых чисел \(l, r\) (\(1 \le l \le r \le n\)), таких что \(\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])\).

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

\(\operatorname{MEX}\) последовательности — это минимальное целое положительное число, отсутствующее в этой последовательности. Например, \(\operatorname{MEX}([1, 3]) = 2\), \(\operatorname{MEX}([5]) = 1\), \(\operatorname{MEX}([3, 1, 2, 6]) = 4\).

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — длину перестановок.

Вторая строка содержит \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)) — элементы перестановки \(p\).

Третья строка содержит \(n\) целых чисел \(q_1, q_2, \ldots, q_n\) (\(1 \le q_i \le n\)) — элементы перестановки \(q\).

Формат выходных данных
Выведите одно целое число — ответ на задачу.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

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

Все квесты в игре имеют одинаковую структуру. Пусть на карте расположены \(m\) комнат. Тогда каждый квест задаётся парой комнат \(u\) и \(v\) (\(1 \le u \le v \le m\)). Для прохождения этого квеста игроку нужно переместиться из комнаты \(u\) в комнату \(v\). Для усложнения игры в каждой комнате, через которую пройдёт игрок (включая начальную и конечную комнату) необходимо решить загадку. Влад называет сложностью квеста минимальное количество загадок, которые надо решить, чтобы его пройти. В частности, сложность квеста, у которого начальная и конечная комната совпадает, равна \(1\), а сложность квеста, в котором начальная и конечная комнаты соединены коридором равна \(2\). Также Влад называет квест трудным, если не существует квеста с большей сложностью, чем данный.

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

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

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

В следующих \(m - 1\) строках выведите через пробел пары целых чисел \(u\) и \(v\), обозначающие коридор, между комнатами \(u\) и \(v\).

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

Примечание
В первом примере карта выглядит так:

На этой карте есть 10 квестов. Обозначим за (u, v) квест, который начинается в комнате с номером u и заканчивается в комнате с номером v. Сложность квестов (1, 1), (2, 2), (3, 3) и (4, 4) равна 1, сложность квестов (1, 2), (1, 3) и (1, 4) равна 2, а сложность квестов (2, 3), (2, 4) и (3, 4) равна 3. Таким образом, трудными квестами являются квесты (2, 3), (2, 4) и (3, 4). Трудных квестов 3, значит интересность игры на данной карте равна 3.

Во втором тестовом примере карта выглядит так:

На этой карте есть 4 трудных квеста (2, 5), (2, 6), (3, 5) и (3, 6). Их сложность равна 4.

В третьем тестовом примере карта выглядит так:

На этой карте есть 5 трудных квестов (2, 8), (3, 8), (4, 8), (5, 8), (6, 8) со сложностью 4.

В сети магазинов <<Мир>> при оплате карточкой Weeza действует акция. При оплате покупки, состоящей не менее чем из \(10\) товаров, плата за самый дешевый товар не берется. Если товаров не меньше 20, то не оплачиваются уже два самых дешевых товара и т.д.

Например, при одновременной покупке \(17\) товаров, покупатель потратит сумму денег равную стоимости только \(16\) самых дорогих из них, а при покупке \(20\) и \(37\) товаров придется заплатить только за \(18\) и \(34\) самых дорогих товара, соответственно.

Миша хочет купить в магазине <<Мир>> \(n\) дисков с альбомами его любимой музыкальной группы. Подобрав подходящие диски, Миша выложил их на ленту в супермаркете в некотором порядке. Так как Миша не только меломан, но и математик, он понял, что ему, возможно, удастся сэкономить, если платить не за все \(n\) товаров одновременно, а разбить их на несколько покупок и оплатить каждую покупку отдельно. Миша решил привлекать к себе как можно меньше внимания и, в частности, не менять порядок товаров на ленте. Таким образом, Миша может только разбивать товары на ленте на группы подряд идущих и платить за каждую группу в отдельности.

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

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

Следующая строка содержит \(n\) чисел \(a_i\) (\(1 \leq a_i \leq 10^9\)) — стоимости дисков в порядке расположения на ленте.

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

В первом примере Мише в любом случае придется оплатить все диски, так как суммарное количество товаров меньше \(10\).

Во втором тестовом примере оптимально во время первой покупки оплатить первые два диска, а за остальные диски заплатить во время второй покупки. Тогда не придется заплатить за диск стоимостью \(9\).

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

На каждом уровне игры генерируется новый проспект из небоскребов, где каждая высотка задается уникальной положительной координатой относительно начала проспекта. После этого Похпид выбирает здание, с которого он начинает свой путь, при этом он может прыгать только на здание, координата которого больше текущей. Трудность этой игры заключается в том, что после каждого прыжка Похпид устает и уже не может прыгать также далеко как раньше. Формально говоря, на каждом уровне генерируется \(n\) зданий, координаты которых равны \(a_1, a_2, \ldots, a_n\). Игрок выбирает стартовый небоскреб и с него может прыгнуть на любое здание, которое находится правее, при этом длина первого прыжка может быть любой. Для всех последующих прыжков должно быть выполнено условие: если сейчас игрок находится на здании с координатой \(a_i\), а до этого был на позиции \(a_j\), то он может перепрыгнуть на здание с координатой \(a_k\), если \(a_i - a_j > a_k - a_i\).

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

Формат входных данных
В первой строке входных данных дается число уровней \(t\) \((1 \leq t \leq 1000)\).

В следующих строках каждый уровень задается числом зданий \(n\) \((1 \leq n \leq 5\,000)\) в одной строке и позициями этих зданий \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 10 ^ {18}, \, a_i \neq a_j\) если \(i \neq j)\) в следующей строке. Гарантируется, что сумма \(n\) по всем уровням не превосходит \(30\,000\).

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

Решения, работающие при \(n \leq 10\) и \(t = 1\) будут получать не меньше 25% баллов.

Решения, работающие при \(n \leq 100\) и \(t \leq 10\) будут получать не меньше 50% баллов.

Решения, работающие при \(n \leq 2500\) и \(t \leq 10\) будут получать не меньше 75% баллов.

В первом примере оптимальный выбор небоскребов \(3, 5, 4, 1\) их координаты соответственно будут равны \(3, 6, 8, 9\).

Во втором примере ответы для уровней получаются выбором следующих 3 наборов индексов соответственно:
1) \(2, 1, 3\)
2) \(3, 2, 8, 7, 5\)
3) \(5, 1, 4, 2\)

Всего во Флатландии \(n\) городов, пронумерованных от \(1\) до \(n\), столица Флатландии имеет номер \(1\). Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города \(i\), где \(i > 1\), обозначим первый город на маршруте от города \(i\) до столицы как \(p_i\).

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город \(i\) с городом \(p_i\), равна \(w_i\). Из-за ограничений технологии любой центр подключения может быть подключен оптическими каналами не более чем к \(k\) другим центрам.

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

Помогите специалистам министерства выбрать каналы для модернизации.

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

На следующих \(n - 1\) строках заданы описания каналов, \((i-1)\)-я из этих строк содержит два целых числа: \(p_i\) и \(w_i\) (\(1 \le p_i \le i\), \(0 \le w_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(cnt\) и \(cost\): максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Замечание
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(4\). Стоимость модернизации любого канала равна \(0\) и не показана.

Есть и другие подходящие решения, в которых модернизируется \(4\) канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно \(6\). Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна \(27\).

Даны два целых числа \(x\) и \(y\). Назовем последовательность \(a\) длины \(n\) модообразной, если \(a_1=x\), и для всех \(1 < i \le n\) значение \(a_{i}\) равно либо \(a_{i-1} + y\), либо \(a_{i-1} \bmod y\). Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).

Определите, существует ли модообразная последовательность длины \(n\), сумма элементов которой равна \(S\), и если существует, то найдите любую такую последовательность.

Формат входных данных
Первая и единственная строка содержит четыре целых числа \(n\), \(x\), \(y\) и \(S\) (\(1 \le n \le 200\,000\), \(0 \le x \le 200\,000\), \(1 \le y \le 200\,000\), \(0 \le S \le 200\,000\)) — длина последовательности, параметры \(x\) и \(y\), и необходимая сумма элементов последовательности.

Формат выходных данных
Если искомая последовательность существует, выведите в первой строке <<Yes>> (без кавычек). Далее, во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — элементы последовательности \(a\). Если подходящих последовательностей несколько, выведите любую из них.

Если же последовательность не существует, выведите в единственной строке <<No>>.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки <<yEs>>, <<yes>>, <<Yes>> и <<YES>> будут приняты как положительный ответ.

Замечание
В первом примере условиям удовлетворяет последовательность \([8, 11, 2, 5, 2]\). Таким образом, \(a_1 = 8 = x\), \(a_2 = 11 = a_1 + 3\), \(a_3 = 2 = a_2 \bmod 3\), \(a_4 = 5 = a_3 + 3\), \(a_5 = 2 = a_4 \bmod 3\).

Во втором примере первый элемент последовательности должен равняться \(5\), поэтому последовательность \([2, 2, 2]\) не подходит.

В ходе работы над оптимизацией компилятора для процессора из предыдущей задачи в фирме Хардсофт задумались об автоматическом выборе подпрограмм, которые станут инлайнподпрограммами. Инлайн-подпрограммы - это такой способ сборки машинного кода, при котором тело подпрограммы во время компиляции подставляется непосредственно в место её вызова, и оно становится частью вызывающего кода. Таким образом, исключаются накладные расходы на вызов и завершение подпрограмм во время работы. 
Инженеры фирмы Хардсофт считают, что инлайн-подпрограммами надо делать те, которые вызываются чаще всего. Однако вставка кода больших подпрограмм в места их вызова приведёт к резкому увеличению памяти, потребляемой программами, а для фирмы важна возможность лёгкой адаптации своего решения к промышленным устройствам, в которых значительную роль играет экономическая составляющая: в частности, необходимый для работы объём памяти должен быть минимальным.
Разработчики создали специальный анализатор, который определяет среднее количество запуска подпрограмм и размер каждой из них.
Требуется определить, какие из подпрограмм можно встроить в инлайн-режиме, для увеличения быстродействия и в пределах доступной памяти.

Формат входных данных
в первой строке через пробел указаны натуральные числа N, M и X. N и M не превышают 100 и являются количеством подпрограмм и количеством цепочек вызова, а X не превышает 10⁶ и является количеством памяти (в килобайтах), доступным для размещения инлайнподпрограмм. Далее идёт N строк, где через пробел перечислены имена подпрограмм (из латинских слов длиной до 20 символов) и их размер в килобайтах (натуральное число от 1 до 1000). Далее - M строк с описанием выявленных цепочек вызова: в них записаны имена подпрограмм через пробел, после которых также через пробел указано ожидаемое количество срабатываний этой цепочки за время работы программы (целое число от 1 до 1000).
Формат выходных данных
в первой строке - количество подпрограмм, которые можно пометить инлайновыми, в последующих строках - имена этих подпрограмм в том порядке, в котором они были указаны во входных данных. Требуется выбрать подпрограммы так, чтобы количество вызовов инлайн-подпрограмм за время работы программы было максимальным. 

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

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

Например, число 6 можно представить следующими способами: \(1+1+1+1+1+1\), \(1+1+1+3\), \(3+3\), \(1+5\).

Формат входных данных
На вход подается число \(n\) (\(1 \le n \le 1000\)).

Формат выходных данных
Выведите число способов представить \(n\) в виде суммы нечетных слагаемых.

У Саши есть блокнот, состоящий из \(n\) листочков, пронумерованных от 1 до \(n\). На \(i\)-м листочке написано целое число \(a_i\).

Аня собирается разорвать блокнот на \(k\) частей, для этого она выбирает \(k-1\) число \(1 \le r_1 < r_2 < \ldots < r_{k-1} < n\) и разрывает блокнот так, что листки с 1 по \(r_1\)-й оказываются в первой части, листки с \((r_1+1)\)-го по \(r_2\)-й оказываются во второй части, и т.д., последняя \(k\)-я часть содержит листки с \((r_{k-1}+1)\)-го по \(n\)-й.

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

Формат входных данных
Первая строка ввода содержит два числа: \(n\) и \(k\) (\(2 \le k \le n \le 300\)). Вторая строка содержит \(n\) целых чисел: \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Формат выходных данных
На первой строке выведите максимальное значение суммы, которое удастся достичь Ане. На второй строке выведите значения \(r_1, r_2, \ldots, r_{k-1}\), которые ей необходимо выбрать. Если вариантов разорвать блокнот, чтобы максимизировать искомую сумму несколько, выведите любой из них.

Примечание
В приведенном примере Аня разорвала блокнот на части \([1, 10, 2]\), \([8]\), \([9]\), \([3, 5, 4]\) и \([7, 6]\). Искомая сумма равна \(1 + 8 + 9 + 3 + 6 = 27\).

Вася идет из школы домой вдоль проспекта, по которому ходят трамваи. Мама считает, что ему после школы полезно дышать свежим воздухом, поэтому настаивает, чтобы не менее \(K\) метров он прошел пешком. Вася при этом хочет попасть домой как можно быстрее (обязательно выполнив требование мамы).

Вдоль проспекта расположено \(N\) трамвайных остановок, которые находятся в точках \(a_1, a_2, \ldots, a_N\) (все координаты задаются в метрах). Школа находится около 1-й остановки, а дом — около остановки номер \(N\). Мальчик идет пешком со скоростью \(v\) метров в минуту. Трамвай едет со скоростью \(w\) метров в минуту (временем стоянки трамвая на остановках пренебрежем). В нулевой момент времени и далее с интервалом \(T\) минут от первой остановки в сторону Васиного дома отправляются трамваи. Вася выходит из школы также в момент времени 0. Сесть в трамвай и выйти из него можно только на остановке. При этом, если Вася приходит на остановку раньше трамвая, на который хочет сесть, то ему придется подождать, пока тот не подъедет. Вася идет пешком и едет на трамвае только в направлении от школы к дому.

Напишите программу, которая определит, когда Вася сможет оказаться дома.

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

Сначала вводится число \(N\) — количество остановок (\(1 \leqslant N \leqslant 2000\)). Далее заданы координаты остановок \(a_1, a_2, \dots, a_N\) (\(0 \leqslant a_1 < a_2 < \ldots < a_N \leqslant 10^9\)). Далее вводится интервал движения трамваев \(T\) (\(1 \leqslant T \leqslant 2000\)). Затем расстояние, не меньше которого Вася должен пройти пешком \(K\) (\(0 \leqslant K \leqslant 2000\)). Затем заданы скорости Васи \(v\) и трамвая \(w\) (\(1 \leqslant v \leqslant w \leqslant 10\,000\)). Все вводимые числа целые. \(K\) не превышает длины пути от школы до дома.

Формат выходных данных
В первую строку выведите не менее чем с пятью знаками после десятичной точки одно число — минимальное время, когда Вася сможет оказаться дома, пройдя пешком не менее \(K\) метров. Далее нужно вывести информацию о пути Васи. Занумеруем промежутки между соседними остановками числами от 1 до \(N-1\) (то есть промежуток между первой и второй остановками имеет номер 1, между второй и третьей — 2 и так далее). Следующая строка должна содержать количество промежутков, пройденных Васей пешком. Далее выведите номера этих промежутков в возрастающем порядке.

В одном королевстве есть \(n\) городов, расположенных вдоль длинной прямой дороги, \(i\)-й город расположен на расстоянии \(x_i\) километров от начала дороги (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

В ближайшее время король планирует провести реформу управления королевством и разделить его на \(k\) провинций. Каждый город должен войти ровно в одну провинцию.

В каждую провинцию войдет от \(a\) до \(b\) городов, причем эти города должны иметь следующие подряд номера. Таким образом, каждая провинция характеризуется числами \(i\) и \(l\), для которых \(1 \le i\), \(i + l - 1 \le n\), \(a \le l \le b\) и в провинцию входят города с номерами \(i, i + 1, \ldots, i + l - 1\).

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

Формат входных данных
Первая строка ввода содержит четыре целых числа: \(n\), \(k\), \(a\) и \(b\) (\(1 \le n \le 200\), \(1 \le k \le n\), \(1 \le a \le b \le n\), \(ak \le n \le bk\)). Вторая строка ввода содержит \(n\) целых чисел: \(x_1, x_2, \ldots, x_n\) (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

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

Примечание
В примере оптимально первые 4 города объединить в первую провинцию, а пятый и шестой — во вторую. Максимальное расстояние между двумя городами в одной провинции: \(13 - 6 = 7\).