Квадратичные сортировки


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 29474. Пузырьковая сортировка
Темы: Квадратичные сортировки   

Требуется отсортировать массив по неубыванию методом "пузырька".
 
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
 
Выходные данные
Вывести получившийся массив.
 
Примеры
Входные данные Выходные данные
1
5
5 4 3 2 1
1 2 3 4 5

ID 23590. Использование сортировки
Темы: Квадратичные сортировки   

Известны значения роста всех учащихся класса. Определите рост учащегося, который при построении учащихся по росту, в порядке возрастания, занимал бы 10-е место при счете от самого высокого ученика.

Нельзя использовать встроенную сортировку.
 

Входные данные
В первой строке вводится натуральное число N - количество учащихся класса (11 <= N <= 35).
Во второй строке вводятся N целых чисел - рост учащихся.

Выходные данные
Необходимо вывести на экран значение роста учащегося, который бы занимал 10-е место по росту в порядке убывания, при счете от самого высого ученика.
 
Пример
Входные данные Выходные данные
1 12
148 144 154 145 155 130 157 136 152 130 177 166
136

ID 22009. Результаты олимпиады
Темы: Квадратичные сортировки   

N участников олимпиады получили уникальные номера от 1 до N. В результате решения задач на олимпиаде, каждый участник получил некоторое количество баллов (целое число от 0 до 600).  Известно, кто сколько баллов набрал. Требуется перечислить участников олимпиады в порядке невозрастания набранных ими баллов.
 
Входные данные
Вводится сначала число N (\(1<=N<=100\)) - количество участников олимпиады. Далее вводится N чисел - количества набранных участниками баллов (1-е число - это баллы, набранные участником номер 1, 2-е - участником номер 2 и т.д.).
 
Выходные данные
Выведите N чисел - номера участников в порядке невозрастания набранных ими баллов (участники, набравшие одинаковое количество баллов, могут быть выведены в любом порядке).
 
Пример
Входные данные Выходные данные
1
5
100 312 0 312 500
5 2 4 1 3

ID 29476. Миссия Серенити
Темы: Квадратичные сортировки   

Экипаж Серенити межпланетного корабля класса Светлячок занимается доставкой грузов на различные планеты звездной системы. На корабле имеется секретный грузовой отсек, состоящий из N × M ячеек. Каждая ячейка грузового отсека имеет предельный объем, который она может вместить. Невозможно в ячейку вместить груз объемом больше, чем предельный объем ячейки. В одну ячейку можно поместить только ровно один груз. 
 
 Капитан Серенити Малькольм Рейнольдс продумывает размещение грузов по ячейкам. Помогите ему определить, какое максимальное количество грузов удастся доставить капитану.
 
Входные данные
В первой строке даны числа N и M (\(1 \leq N, M \leq 40\)). В каждой из последующих N строк содержится по M чисел, обозначающих предельный объем соответствующей ячейки. В (N+2)-ой строке находится число K (\(1 \leq K \leq 2000\)) – количество грузов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – объем i-ого груза. Все объемы – натуральные числа, не превышающие 109.

Выходные данные
Требуется вывести одно число – максимально возможное количество грузов, которое удастся доставить.
 
Пример
Входные данные Выходные данные
1
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
4

ID 38115. Доставка контейнеров
Темы: Квадратичные сортировки   

Малькольма Рейнольдса попросили доставить пустые контейнеры на самую отдаленную планету звездной системы. На корабле осталась только одна свободная ячейка объемом Х, в которую можно положить контейнеры. Капитан решил сложить несколько контейнеров друг в друга. Все контейнеры имеют подобные размеры. Контейнер с меньшим объемом свободно помещается в контейнер с объемом на 3 условных единицы больше. Определите, какое наибольшее количество контейнеров может доставить капитан Рейнольдс?

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

Выходные данные
Выведите одно число — максимальное количество контейнеров, которое сможет доставить Малькольм Рейнольдс.
 

Примеры
Входные данные Выходные данные
1 60
2
60 63
1
2 26 
5
26 24 22 21 18
3

ID 45240. Сортировка по квадратам чисел
Темы: Квадратичные сортировки   

Дан массив целых чисел. Верните отсортированный по неубыванию массив квадратов исходных чисел.

Входные данные
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел a- элементы массива (1 <= n <= 103-104 <= ai <= 104).

Выходные данные
Выведите результирующий массив.
 
 

Примеры
Входные данные Выходные данные
1 5
-1 -4 3 0 10
0 1 9 16 100
2 3
3 -1 1
1 1 9

ID 45241. Сортировка массива (сложная) - 1
Темы: Квадратичные сортировки    Двумерные массивы   

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

Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел a- элементы массива (1 <= n <= 1031 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.
 
 

Примеры
Входные данные Выходные данные
1 4
1 43 12 10
43 12 10 1

ID 45242. Наибольшее произведение трех чисел - поиск сортировкой
Темы: Квадратичные сортировки   

Дано целое число  N<=103 и N целых чисел. необходимо найти три числа, произведение которых максимально.

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

Входные данные
В первой строке задано целое число 3 <= N <= 103 - количество элементов в списке.
Во второй строке заданы N целых  элементов списка, не превосходящих по модулю 30000.

Выходные данные
Выведите ответ на задачу.
 

Примеры
Входные данные Выходные данные
1 9
3 5 1 7 9 0 9 -3 10
10 9 9
2 3
-5 -30000 -12
-5 -12 -30000

ID 33207. Сортировка по цифрам числа 2
Темы: Одномерные массивы    Квадратичные сортировки   

Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные

9
639 265 915 993 436 202 573 906 490 

Выходные данные
202 265 436 490 573 639 906 915 993

ID 33205. Пятый самый легкий
Темы: Одномерные массивы    Квадратичные сортировки   

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел mi - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

Формат выходных данных
Напечатайте массу предмета, являющегося "пятым самым легким предметом".

ID 33203. Средние в шеренге
Темы: Одномерные массивы    Квадратичные сортировки   

Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел mi - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

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

ID 33202. Использование сортировки 2
Темы: Одномерные массивы    Квадратичные сортировки   

В каждом из двух классов учатся по n человек (10 <= n <= 30). Известны средний балл каждого ученика каждого класса, подсчитанные по ряду предметов (все значения целые). Определить, в каком классе у "третьего из самых успевающих учеников" средняя оценка больше. Вывести цифру "1" - для первого класса, "2" - для второго. Если оценки равны, вывести эту оценку.


Формат входных данных
В первой строке записано натуральное число n (n < 100) - количество учеников в каждом классе . Вторая строка содержит n положительных целых чисел class1i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class1i ≤ 105). Третья строка содержит n положительных целых чисел class2i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class2i ≤ 105).

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

ID 33206. Сортировка по цифрам числа 1
Темы: Одномерные массивы    Квадратичные сортировки   

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

Формат входных данных
В первой строке записано натуральное число N (1<=N<=1000). Вторая строка содержит n двузначных положительных чисел numsi (1 ≤ i ≤ n, 10 ≤ numsi ≤ 99).

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

ID 45717. Сортировка побочной диагонали
Темы: Двумерные массивы    Квадратичные сортировки   

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

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

В первой строке записано одно число N размер квадратной матрицы ( 1 <= N <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по N натуральных чисел, разделённых пробелами. 
 

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

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

Примеры
Входные данные Выходные данные
1
5
12 4 8 13 13 
1 12 1 4 15 
2 3 5 2 3 
6 5 13 12 14 
14 9 15 4 12 
12 4 8 13 14 
1 12 1 13 15 
2 3 5 2 3 
6 5 13 12 14 
4 9 15 4 12
 

ID 45719. Сортировка двумерного массива
Темы: Двумерные массивы    Квадратичные сортировки   

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


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

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

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

Программа должна вывести отсортированный двумерный массив.
 

Примеры
Входные данные Выходные данные
1
5 7
13 5 1 8 4 14 5 
5 13 10 9 3 7 7 
3 3 9 6 3 7 5 
10 8 11 2 1 1 13 
1 12 13 15 9 11 4 
1 1 1 1 2 3 3 
3 3 4 4 5 5 5 
5 6 7 7 7 8 8 
9 9 9 10 10 11 11 
12 13 13 13 13 14 15 

ID 48947. Обувной магазин
Темы: Квадратичные сортировки   

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

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

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

ID 49035. K-й по счету
Темы: Квадратичные сортировки   

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел vi - значения максимальной скорости i-го автомобиля (1 i n, 1 ≤ ai ≤ 105). В третьей строке записано натуральное число k (k ≤ n). 

Формат выходных данных
Напечатайте максимальную скорость автомобиля, являющегося "k-м самым быстрым автомобилем".

ID 49037. Самый легкий
Темы: Квадратичные сортировки   

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел mi - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). В третьей строке записано натуральное число k (k ≤ n). 

Формат выходных данных
Напечатайте массу предмета, являющегося "k-м самым легким предметом".

ID 49039. Средние по росту
Темы: Квадратичные сортировки   

Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел mi - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

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

ID 49368. Сортировка по сумме строк
Темы: Квадратичные сортировки   

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

ID 49369. Сортировка по сумме строк - 2
Темы: Квадратичные сортировки   

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

ID 49370. Сортировка по максимальному элементу в строке - 2
Темы: Квадратичные сортировки   

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

ID 49371. Сортировка по максимальному элементу в строке - 1
Темы: Квадратичные сортировки   

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

ID 49372. Сортировка по минимальному элементу в строке - 1
Темы: Квадратичные сортировки   

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

ID 49373. Сортировка по минимальному элементу в строке - 2
Темы: Квадратичные сортировки   

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

ID 49380. Сортировка по сумме элементов в столбце - 1
Темы: Квадратичные сортировки   

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

ID 49381. Сортировка по сумме элементов в столбце - 2
Темы: Квадратичные сортировки   

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

ID 49382. Сортировка по максимальному в столбце - 1
Темы: Квадратичные сортировки   

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

ID 49405. Сортировка по максимальному в столбце - 2
Темы: Квадратичные сортировки   

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

ID 49406. Сортировка по минимальному в столбце - 2
Темы: Квадратичные сортировки   

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

ID 49407. Сортировка столбцов матрицы (сложная) - 1
Темы: Квадратичные сортировки   

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

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

ID 49408. Сортировка по минимальному в столбце - 1
Темы: Квадратичные сортировки   

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

ID 49409. Сортировка столбцов матрицы (сложная) - 2
Темы: Квадратичные сортировки   

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

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

ID 49410. Сортировка массива (сложная) - 2
Темы: Квадратичные сортировки    Двумерные массивы   

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


Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел a- элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.

ID 49413. Сортировка массива (сложная) - 3
Темы: Квадратичные сортировки    Двумерные массивы   

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


Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел a- элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.

ID 49414. Сортировка массива (сложная) - 4
Темы: Квадратичные сортировки    Двумерные массивы   

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


Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел a- элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.

ID 49417. Наибольший отрезок, не содержащий точек
Темы: Квадратичные сортировки    Использование сортировки   

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

Формат входных данных
В первой строке записано натуральное число N - количество отмеченных точек (2 <= N <= 103). Во второй строке записано N целых чисел - координаты точек (каждое число по модулю не больше 109).

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