Использование сортировки

Громозека имеет последовательность целых чисел A длины N. Он свободно выбирает целое число b. Здесь ему станет грустно, если Ai и b+i находятся далеко друг от друга. Точнее, печаль Громозеки рассчитывается следующим образом:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\).
Здесь \(abs(x) \)- это функция, которая возвращает абсолютное значение x. Найдите минимально возможную печаль Громозеки.

Входные данные
В первой строке записано целое число N  (\(1<=N<=2 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=10^9\)).

Выходные данные
Выведите на экран минимально возможную печаль Громозеки.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 2 2 3 5 5	2	Если мы выберем b = 0, печаль Громозеки будет \(\)  abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2. Любой другой выбор b не делает печаль Громозеки меньше 2, поэтому ответ - 2.
2	9 1 2 3 4 5 6 7 8 9	0
3	6 6 5 4 3 2 1	18
4	7 1 1 1 1 2 3 4	6

Выведите все исходные точки в порядке возрастания их расстояний от начала координат.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

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

 Примеры

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

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

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

Дано натуральное четырехзначное число. Найдите минимальное натуральное четырехзначное число, состоящее из тех же цифр, что и заданное. Заметим, что четырехзначные числа не могут начинаться с нуля.

Входные данные
Вводится натуральное четырехзначное число.

Выходные данные
Выведите минимальное натуральное  четырехзначное число, состоящее из тех же цифр.

Примеры

№	Входные данные	Выходные данные
1	1513	1135

У ковбоя Влада день рождения! На праздник собрались n детей. Чтобы поздравить ковбоя, дети решили водить вокруг Влада хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, многим из них может быть неудобно, потому что если в хороводе рядом стоят очень высокий и очень низкий ребёнок, им трудно держаться за руки. Поэтому дети решили встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была минимальной.

Более формально, пусть n детей выстроились в хоровод. Пронумеруем их целыми числами от 1 до n так, чтобы справа от ребёнка с номером i стоял ребёнок с номером i+1, а справа от ребёнка с номером n стоял ребёнок с номером 1. Тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. Обратите внимание, что разностью в росте двух детей называется разность между ростом более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна.

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

Входные данные
В первой строке содержится одно целое число n (2 ≤ n≤ 10⁵) — количество детей, которые пришли на день рождения ковбоя Влада.

Во второй строке заданы n целых чисел a_i (1≤a_i≤10⁹) — рост каждого из детей. Рост детей задан в нанометрах и уменьшен на 10⁹, таким образом, рост ребёнка с a_i=1 чуть выше метра, а рост ребёнка с a_i=10⁹ составляет два метра.

Выходные данные
Выведите n целых чисел — значения роста детей в порядке, в котором они должны встать в хоровод. В этом порядке соседними будут дети с номерами i и i+1, а также дети с номерами 1 и n. Если оптимальных хороводов несколько, то выведите любой из них.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 1 1 3 2	1 2 3 2 1	Здесь неудобство хоровода равно 1, так как разность в росте между соседними детьми равна 1, 1, 1, 1 и 0 соответственно. Обратите внимание, что последовательности [23211] , [32112]  задают те же хороводы и отличаются только выбором ребёнка с номером 1.
2	3 30 10 20	10 30 20	Неудобство хоровода равно 20, так как разность в росте детей высотой 10 и 30 равна 20.

У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.

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

Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10⁵ ) — количество банок в наборе Карлсона.

Вторая строка входных данных содержит n целых чисел a_i ( 0 ≤ a_i ≤ 10⁹ ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.

Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.

Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.

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

Примеры

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

Маше на день рождения подарили набор матрёшек!

Теперь Маша сидит и вкладывает их одну в другую. Она заметила, что матрёшки отличаются по размеру, и одна помещается внутри другой, только если ее размеры строго меньше. Так, если есть две матрёшки i и j , а их размеры a_i и a_j соответственно, то матрёшка i вкладывается внутрь матрёшки j тогда и только тогда, когда a_i < a_j . Разумеется, непосредственно внутрь матрёшки можно вложить только одну другую матрёшку, иначе получится неаккуратно, а Маша — очень аккуратная девочка.

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

Входные данные
В первой строке находится число n — количество матрёшек, подаренных Маше ( 1 ≤ n ≤ 1000 ). В следующей строке через пробел находятся n чисел — размеры матрёшек. Число a_i , стоящее на месте i , задает размер матрёшки с номером i ( 1 ≤ a_i ≤ 10 000 ).

Выходные данные
Выведите одно число — максимальное количество матрёшек, которые можно вложить друг в друга.
 

Примеры

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

В числе подсчитали количество единиц, в получившемся опять подсчитали количество единици т.д.
Например: 111211121112111 - 12 - 1 - 1 - 1 - ...

В итоге полученная последовательность стабилизировалась. На каком числе?

Например, последовательность 111211121112111 - 12 - 1 - 1 - 1 - ... стабилизировалась на числе 1.

Входные данные
Вводится одно натуральное число, состоящее из не более чем 100 цифр.

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

Примеры

№	Входные данные	Выходные данные
1	12345	1
2	2007	0

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

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

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

 Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n_i - число стаканов и бутылок напитков в i-ом наборе (1≤n_i≤10⁵).
Во второй строке даны n_i чисел b_i,j - объемы стаканов в i-м наборе (1≤a_i,j,b_i,j≤100).
В третьей строке заданы n_i чисел a_i,j - объемы бутылок в i-м наборе.
Гарантируется, что сумма n_i по всем тестовым наборам не превосходит 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	0 1 6	В первом тестовом наборе второй напиток не помещается ни в один стакан, поэтому ответ будет ноль. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе любой напиток можно налить в любой стакан.

К Коле на день рождения придут 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	В первом тестовом наборе любой напиток помещается в любой стакан. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе ни один напиток не поместится во второй стакан, поэтому ответ будет ноль

Беси учится на PhD в компьютерных науках. Она опубликовала N статей (1≤N≤10⁵) и её i-ую статью цитировали c_i раз (0≤c_i≤10⁵).

Беси слышала что академические успехи измеряются h-индексом. h-индекс - это наибольшее число h такое, что ученый имеет не менее h статей, каждая из которых цитируется не менее h раз. Например, учёный у которого четрые статьи с количествами цитат (1,100,2,3) имеет h-индекс равный 2, а ученый с количествами цитат (1,100,3,3) имеет h-индекс равный 3.

Чтобы повысить свой h-индекс Беси планирует написать обзорную статью, цитирующую некоторые из её прошлых статей. В связи с ограничением на количество страниц, она может включить не более L цитат в свой обзор (0≤L≤10⁵), т конечно она может процитировать каждую из своих статей не более одного раза.

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

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

ФОРМАТ ВВОДА
Первая строка ввода содержит N и L.

Вторая строка ввода содержит N разделённых одиночными пробелами целых чисел c1,…,cN.

ФОРМАТ ВЫВОДА
Максимальный h-индекс, который Беси может получить написанием обзорной статьи.

№	Входные данные	Выходные данные	Пояснение
1	4 0 1 100 2 3	2	Беси не может цитировать свои статьи. Как указано ранее её h-индекс для (1,100,2,3) равен 2.
2	4 1 1 100 2 3	3	Если Беси процитирует третью статью, её количества цитирований станут (1,100,3,3). Как отмечено ранее, h в этом случае равен 3.

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

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

Формат входных данных
Первая строка входных данных содержит число n - количество видов пирожных на фабрике, 1 <= n <= 10⁵.
Следующие n строк содержат по одному числу ai - количество пирожных i-го вида, 1 <= ai <= 10⁵.
Сумма всех значений ai не превосходит 2 x 10⁹.

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

Ввод	Вывод
3 4 10 7	2 7

Пояснение к примеру. Имеется 3 вида пирожных количеством 4, 10 и 7 штук. Наилучший ответ будет, если взять по 7 пирожных второго и третьего вида.

Дано N целых чисел. Найти третий по величине максимальный элемент последовательности (элемент, который бы стоял третьим, если бы входные данные отсортировали по неубыванию).

Входные данные
В первой строке задается число N (\(3<=N<=10^5\)). Далее идут N строк, по одному числу в каждой строке.

Выходные данные
Выведите третий максимальный элемент.
 

 

Примеры

№	Входные данные	Выходные данные
1	7 10 15 35 35 14 35 10	35
2	5 10 5 7 11 9	9

 
 

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

Формат входных данных
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине - неотрицательное число, не превосходит 1000.

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

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

Входные данные
Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что 0 < N ≤ 10000 .

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

Ввод	Вывод
6 9 21 32 55 81 11	55 9 81 32 21 11

Дан текст, состоящий из нескольких строк. Текст заканчивается строкой, содержащей единственное слово "END!". Слово "END!" не является содержимым текста, а служит только признаком окончания.

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

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

Пример

№	Входные данные	Выходные данные
1	Duis aute irure dolor in reprehenderit in voluptate. Velit esse cillum dolore eu fugiat nulla pariatur. END!	in 2 aute 1 cillum 1 dolor 1 dolore 1 duis 1 esse 1 eu 1 fugiat 1 irure 1 nulla 1 pariatur 1 reprehenderit 1 velit 1 voluptate 1