сортировки

Алгоритм гравитационной сортировки позволяет упорядочить массив целых неотрицательных чисел. Для сортировки чисел используется набор стержней и бусинок. Рассмотрим алгоритм сортировки массива целых неотрицательных чисел \([a_1, a_2, ..., a_n]\). Если данные числа могут достигать значения \(n\), нужно использовать \(n\) стержней и \(a_1+a_2+...+a_n\) бусинок. Наденем по одной бусинке на самые левые \(a_1\) стержней, они представляют значение \(a_1\). Затем наденем по одной бусинке на самые левые \(a_2\) стержней, разместив их во втором ряду, над первым рядом бусинок. При этом, если \(a_2>a_1\), то некоторые бусинки второго ряда окажутся как бы висящими в воздухе, они не будут опираться на бусинки нижнего ряда. Затем на самых левых \(a_3\) стержнях в третьем ряду разместим \(a_3\) бусинок, часть из них также может не опираться ни на какие предыдущие бусинки и т.д. После того, как все бусинки будут размещены, они начинают двигаться по стержням вниз. Когда движение завершится, количество бусинок в каждом ряду будет равно значениям упорядоченного массива.

Будем считать, что все бусинки двигаются одновременно. За секунду одна бусинка сползает на один ряд вниз, если в ряду ниже пусто или находится бусинка, которая также спускается вниз. На рисунках показано начальное расположение бусинок для массива \([2, 4, 1, 5, 3]\) и состояние через 1, 2 и 3 секунды.

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

Первая строка входных данных содержит число \(n\) (\(1\le n\le 10^5\)) — количество сортируемых чисел и количество стержней (то есть максимальное значение одного числа). Следующие \(n\) строк содержат по одному числу \(a_i\) (\(0\le a_i\le n\)) — значения упорядочиваемых чисел (начальные значения числа бусинок в каждом ряду).

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

Решения, правильно работающие при \(n\le 10\), будут оцениваться в 30 баллов.

Решения, правильно работающие при \(n\le 2000\), будут оцениваться в 60 баллов.

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

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

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

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

 

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

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

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

 

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

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

Космическая станция «Орион» принимает сигналы от спутников-разведчиков. Приёмная матрица станции имеет размер 640 строк на 480 позиций. При получении каждого сигнала в журнал записываются координаты активированного элемента матрицы: номер строки и номер позиции в строке.

Элемент матрицы, который принял хотя бы один сигнал, считается активным. Элемент, который не принял ни одного сигнала, считается неактивным.

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

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


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

В первой строке записано целое число N — количество принятых сигналов (1 ≤ N ≤ 10000).

В каждой из следующих N строк записаны по два числа через пробел:
- номер строки (целое число от 1 до 640)
- номер позиции в строке (целое число от 1 до 480)

Один и тот же элемент матрицы может получить несколько сигналов (координаты могут повторяться).

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

Два целых числа через пробел: наибольшая длина цепочки активных элементов и номер строки, в которой она находится.
 

Напишите программу, которая переставляет строки матрицы так, чтобы при их просмотре сверху вниз максимальные значения в каждой строке образовали невозрастающую последовательность. В случае равенства максимальных значений в двух строках, строки должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.
 

Напишите программу, которая переставляет строки матрицы так, чтобы при их просмотре сверху вниз суммы всех значений в каждой строке образовали невозрастающую последовательность. В случае равенства суммы всех значений в двух строках, строки должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.