Жадный алгоритм

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф – темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо b_j < a_i < b_k, либо b_k < a_i < b_j.

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

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел a_i – строптивость оленей ( 0 ≤ a_i ≤ 10⁹). В третьей строке записаны n целых чисел b_i – темперамент эльфов ( 0 ≤ b_i ≤ 10⁹).

Выходные данные
В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: d_i, e_i, 1, e_i, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.

Примеры

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

По приезде Василий с Петром обнаружили в своем номере в гостинице странный прибор. Он был оснащен дисплеем, на котором показывалось число 0, и двумя кнопками. Василий сразу понял, что первая кнопка увеличивает число на дисплее на 1, а вторая умножает его на K. В этот момент Петр обнаружил на своей кровати листок бумаги, на котором было написано единственное число N.
Теперь друзья хотят воспроизвести число N на дисплее найденного ими устройства, и, поскольку их ждет еще множество дел, им интересно минимальное число нажатий на кнопки устройства для получения числа N.

Входные данные
В первой строке входных данных записано целое неотрицательное число N (1 ≤ N ≤ 10⁹ ).
Во второй строке входных данных записано целое положительное число K (2 ≤ K ≤ 10⁹ ).

Выходные данные
Выведите единственное число — минимальное количество нажатий на кнопки устройства для получения на его дисплее числа N.
 

Примеры

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

Замечание
В примере из условия Василий и Петр хотят воспроизвести число 4. Кнопка умножает на 2 число, которое показывается на дисплее. Первой операцией друзья увеличивают текущее число на 1, нажимая первую кнопку, после чего оно становится равно 1. Затем они умножают его на 2, нажимая вторую кнопку. Текущее число становится равно 2. После чего, для получения на дисплее числа 4 достаточно один раз нажать вторую кнопку и умножить текущее число (то есть 2) на 2. Несложно показать, что меньше, чем за три операции, получить число 4 невозможно. Таким образом, минимальное число действий равняется трем.
 

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

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

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе F_i в момент времени X_i и заканчивается в некотором другом городе G_i в момент времени Y_i. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени X_i в городе Fi.

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

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

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления F_i, время отправления X_i, номер города назначения G_i (Fi ≠ Gi), время прибытия Y_i, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

Выходные данные
Выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1.

Примеры

№	Входные данные	Выходные данные
1	4 6 1 10:00 2 12:00 1 10:00 3 09:00 3 12:00 4 23:00 2 11:00 4 13:00 4 12:00 1 11:00 4 12:00 1 10:30	8

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

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

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), разделенные пробелами.

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

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

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 13 2	8
2	3 4 8 3	2
3	3 4 7 1	9

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

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

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

Входные данные
Первая строка содержит целое число N (1  N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк -  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 2 1 4 2 5 1	< > > ? >

В новой математической игре для одного игрока «Таблица чисел» используется таблица размером n строк на m столбцов, заполненная целыми числами. За один ход игрок выбирает одну из строк или один из столбцов и меняет знак на противоположный у всех чисел этой строки или столбца.

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

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

Входные данные
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n, m ≤ 100). Каждая из последующих n строк содержит по m целых чисел a_i,j (|a_i,j| ≤ 100).

Выходные данные
В первой строке выходного файла выведите k — число ходов, которые необходимо выполнить, или «-1», если цели игры добиться невозможно. В первом случае в последующих k строках выведите описание этих ходов.

Описание каждого хода должно быть выведено в отдельной строке, которые должны содержать: тип хода («R» — на этом ходе выбирается строка или «C» — на этом ходе выбирается столбец) и номер соответствующей строки или столбца. Строки и столбцы нумеруются натуральными числами начиная с единицы, строки нумеруются сверху вниз, а столбцы — слева направо.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 -1 -3 1 -2	1 C 2
2	3 2 -1 -1 -1 -1 -1 -1	3 R 1 R 2 R 3

Дано верное равенство вида a₁+a₂+…+a_N=b₁+b₂+…b_M, где a₁,a₂,…,a_N, b₁,b₂,…,b_M – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c₁+c₂+…+c_N=d₁+d₂+…+d_M, где c₁,c₂,…,c_N,d₁,d₂,…,d_M — целые числа, и при этом c₁ получено округлением числа a₁ до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c₂ получено округлением a₂, …, c_N – округлением a_N, d₁ – округлением b₁, …, d_M – округлением b_M. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.

Входные данные
Во входном файле задано сначала число N, затем N чисел a₁, a₂, …, a_N, затем число M, затем числа b₁, b₂, …, b_M. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a₁+a₂+…+a_N=b₁+b₂+…b_M.

Выходные данные
Если «округлить» равенство можно, то в выходной файл выведите сначала числа c₁,c₂,…,c_N, а затем числа d₁,d₂,…,d_M. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.

Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 0.15 -3.000 2.7 1 -0.15	1 -3 2 0	Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0
2	2 1.7 2.5 3 1 2.000 1.20	2 2 1 2 1	Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.
3	1 0.5 1 0.5	0 0	Здесь верными являются как ответ 1=1, так и 0=0.

В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

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

Входные данные
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	50 3 100	75	Через 50 секунд после начала игры у игрока будет 50 печенек, и он сможет купить фабрику. После этого он будет получать 4 печеньки в секунду, и на производство 100 печенек понадобится еще 25 секунд.
2	99 10 100	100	Игрок сможет набрать 100 печенек за 100 секунд, при этом фабрику покупать нет смысла.

Начались каникулы, и дядя Фёдор, изрядно соскучившись по своим школьным друзьям, пригласил их всех в гости к себе в Простоквашино. После некоторых раздумий n из них согласились приехать. Взяв с собой все необходимые для отдыха на природе вещи, они приехали на вокзал покупать билеты. Выяснилось, что в поездах, идущих до Простоквашино, есть только купейные вагоны. В каждом вагоне всего k₄ четырехместных купе и k₂ — новых двухместных купе. Кроме друзей дяди Фёдора, никто не хочет ехать в Простоквашино, поэтому все места в поезде пока свободны. Друзья решили, что они хотят поехать все в одном вагоне: вместе ведь веселее. Чтобы поездка запомнилась надолго, один из друзей дяди Фёдора, Женя, решил одолжить у папы фотоаппарат «Зенит» и сфотографировать всех участников поездки, сидящих каждый на своем месте в поезде, по одному снимку на купе. Но пленка дорогая, а проявка — это долго и нудно, поэтому Женя попросил купить билеты так, чтобы вся дружная компания занимала как можно меньше купе. Помогите Жене посчитать, сколько в лучшем случае ему понадобится кадров, чтобы сфотографировать всю компанию, то есть посчитайте, сколько минимально купе они должны занять.

Входные данные
В первой и единственной строке вводятся числа n, k₄ и k₂ — количество друзей дяди Фёдора, едущих в Простоквашино, количество четырехместных купе в вагоне и количество двухместных купе в вагоне соответственно (1≤n≤10¹⁸, 0≤k₄≤10¹⁸, 0≤k₂≤10¹⁸).

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

Примеры

№	Входные данные	Выходные данные
1	10 5 3	3

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

Входные данные
Вводится сначала стоимость билета, который хочет приобрести пассажир, затем общее количество купюр и монет, которые он опустил в автомат, а затем достоинства каждой из этих купюр и монет. Входные данные записаны в одной строке и разделены пробелами. Известно, что сумма всех купюр больше, чем стоимость билета. Во всех тестовых примерах стоимость билета – натуральное число, не превосходящее 1 000 рублей, количество купюр и монет не более 50, достоинство каждой не превосходит 500 рублей. Общая сумма денег, опущенных в автомат покупателем, превосходит стоимость билета.

Выходные данные
Программа должна вычислить, какими купюрами и монетами можно выдать сдачу, и вывести достоинство каждой из этих купюр или монет в произвольном порядке. Автомат может выдавать сдачу купюрами в 10, 50, 100 и 500 рублей, а также монетами в 1, 2 и 5 рублей. Если решений несколько, требуется выдать одно любое из них. Если решений нет, требуется выдать текст:

Sorry! Our monetary system is not perfect!
Please, choose another way to pay!
Thank you!

Примеры

№	Входные данные	Выходные данные
1	100 1 500	50 100 100 100 50

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

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

Коля хочет своеобразно оценить сколько способов есть разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы. Так как число способов может быть довольно большим, Коля хочет знать его по модулю 1 000 000 007. Помогите Коле посчитать это число.
Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n_i - число бутылок напитков и стаканов в i-ом наборе (1≤n_i≤10⁵).
Во второй строке заданы n_i чисел a_i,j - объемы бутылок в i-м наборе.
В третьей строке даны n_i чисел b_i,j - объемы стаканов в i-м наборе (1≤a_i,j,b_i,j≤100).
Гарантируется, что сумма ni по всем тестовым наборам не превосходит 3⋅10⁵.

Выходные данные
Для каждого тестового набора выведите одно число - число способов разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы, взятое по модулю 1 000 000 007.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 1 1 1 2 1 5 1 2 3 4 5 1 2 3 4 5 3 2 2 2 2 1 2	6 1 0	В первом тестовом наборе любой напиток помещается в любой стакан. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе ни один напиток не поместится во второй стакан, поэтому ответ будет ноль

Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.

Корова Беси хочет посетить N своих предшественников, которые жили много раньше (\(1<=N<=0x10000\)). 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной.

К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более K прыжков во времени (\(1<=K<=N\)). Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более K прыжков во времени по пути.

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

Входные данные
Первая строка ввода содержит N и K. Следующие N строк содержат N различных целых чисел в интервале \(1…10^9\), указывающих сколько лет назад жил каждый из предшественников Беси.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 3 101 85 100 46 95	36	Один из способов для Беси посетить всех своих предшественников за 36 лет таков: Войти в портал в текущем году и вернуться на 48 лет в прошлое. Подождать 12 лет затем войтив портал в 36 лет в прошлом и пропутешествовать 108 лет в прошлое. Подождать 24 года, затем зайти в портал в 84 года в прошлом и пропутешествовать обратно в текущий год.

Фермер Джон открыл пастбище с целью помочь Беси и её друзьям.
Пастбище ФД можно рассматривать как большую 2D-решётку квадратных ячеек. Каждая ячейка помечена таким образом:

• C если в ячейке корова
• G если в ячейке трава
• . если в ячейке нет ни коровы, ни травы

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

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

ФОРМАТ ВВОДА:
Первая строка содержит N и M (2 ≤ N,M ≤ 1000).
Каждая из следующих N строк содержит M символов, описывая пастбище.

ФОРМАТ ВЫВОДА:
Определите максимальное количество пар коров, которые могут стать друзьями.
 

№	Входные данные	Выходные данные
1	4 5 .CGGC .CGCG CGCG. .CC.C	4

Если мы пометим корову в строке i и столбце j координатами (i,j), тогда в этом примере есть коровы в (1,2), (1,5), (2,2), (2,4), (3,1), (3,3), (4,2), (4,3), and (4,5). Один из способов, чтобы 4 коровы стали друзьями таков:

Коровы из (2,2) и (3,3) едят траву в (3,2).
Коровы из (2,2) и (2,4) едят траву в (2,3).
Коровы из (2,4) и (3,3) едят траву в (3,4).
Коровы из (2,4) и (1,5) едят траву в (2,5).

Недавно Вася решил, что все существующие алгоритмы сортировки слишком сложны, и обязательно должен существовать более простой и эффективный алгоритм.
Для начала Вася решил рассмотреть следующий алгоритм: по данному массиву целых чисел a размером n, он создает пустой массив b, а дальше на каждой из n последующих итераций будет брать k-й элемент массива a (или последний, если такого нет), удалять его из a, а затем записывать в конец b. Таким образом, после n итераций Вася планирует в качестве массива b получить отсортированный по возрастанию массив a.
Однако, протестировав на нескольких примерах, Вася понял, что этот алгоритм работает не всегда. Так, например, если исходный массив a=[1,2,3,4] и k=2, то после 4 итераций массив b вовсе не будет отсортированным:
После первой итерации в b добавляется число 2, а массив a равен [1,3,4];
После второй итерации в конец b добавляется число 3, а массив a равен [1,4];
После третьей итерации в конец b добавляется число 4, а массив a равен [1];
На последней, четвертой итерации, в конец b добавляется число 1, а массив a становится пустым;
Таким образом, итоговый массив b будет выглядеть так: [2,3,4,1]. Нетрудно заметить, что он не является отсортированным по возрастанию. Однако, Вася решил так легко не сдаваться и по данному числу k научиться находить такой массив a, содержащий перестановку последовательности натуральных чисел от 1 до n, который будет сортироваться по возрастанию методом, описанным выше. Помогите ему - по данным числам n и k найдите хотя бы один подходящий массив a.

Формат входных данных
В единственной строке содержится два числа n и k - размер массива и номер элемента, берущегося на каждой итерации, соответственно (1≤k≤n≤1000).

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

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

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами A, B и C (A < B < C) сидят три кузнечика, которые играют в чехарду по следующим правилам:
1. На одной плитке может находиться только один кузнечик.
2. За один ход один из двух крайних кузнечиков (то есть с плитки A или с плитки C) может перепрыгнуть через среднего кузнечика (плитка B) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между B и C или A и B соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.
Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).
Даны три числа: A, B, C. Определите, какое наибольшее число ходов может продолжаться игра.

Формат входных данных
Программа получает на вход три целых числа A, B и C (1 <= A < B < C <= 1000), записанных в отдельных строках.
Формат выходных данных
Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.
 

Ввод	Вывод	Примечание
1 4 6	2	В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.

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

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

Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.
Первая строка входных данных содержит целое число L (L > 0) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N (N > 0) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.
Программа должна вывести одно целое число — минимальное количество компанийподрядчиков, которое необходимо привлечь для ремонта дороги.
 

Ввод	Вывод	Примечание
3 8 0 0 1 0 1 0 1 0	2	Первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.

В Москве начал работать новый оператор сотовой связи, предоставляющий доступ в интернет посредством технологии 3G. Новый оператор предлагает простые и невысокие
тарифы, в частности, один мегабайт интернет-трафика стоит 1 рубль. 

Кроме того, оператор предлагает покупать оптовые пакеты трафика – есть два предложения: купить пакет трафика на A мегабайт за B рублей и купить пакет трафика на C мегабайт за D рублей.

Таня планирует использовать в течение месяца N мегабайт интернет-трафика. Определите минимальную сумму, которую придётся ей заплатить. Таня может приобретать
любое количество каждых из двух предлагаемых пакетов, а также оплачивать трафик по тарифу «1 рубль за мегабайт». Таня может приобретать пакеты интернет-трафика и в том
случае, если суммарный оплаченный трафик будет более N мегабайт, если это выйдет дешевле.

Программа получает на вход пять натуральных чисел N, A, B, C, D, записанных в отдельных строках, не превосходящих 500 000 каждое. Гарантируется, что A > B и C > D.
Программа должна вывести одно целое число – минимальную сумму, которую нужно заплатить для приобретения N мегабайт трафика.
 

Ввод	Вывод	Примечание
35 10 9 20 17	31	Пакет на 10 мегабайт стоит 9 рублей, пакет на 20 мегабайт стоит 17 рублей. Для оплаты 35 мегабайт нужно купить пакет на 10 мегабайт и пакет на 20 мегабайт, а за оставшиеся 5 мегабайт заплатить 5 рублей.
55 30 20 20 16	40	Пакет на 30 мегабайт стоит 20 рублей, пакет на 20 мегабайт стоит 16 рублей. Для оплаты 55 мегабайт нужно купить два пакета на 30 мегабайт, что суммарно будет стоить 40 рублей.

 

Тем временем Ёж решил покатать шары из снега. В итоге у него получилось N шариков с диаметрами a₁, a₂, … a_n, все они различны. Из них он хочет собрать как можно больше НОРМАЛЬНЫХ снеговиков. Нормальный снеговик состоит из трёх шаров, диаметр которых снизу вверх строго уменьшается. Сколько максимум снеговиком он сможет собрать?

Ввод	Вывод
6 2 3 4 5 6 7	2

(с) Манаев И., Кашукова М., 2018 г.