Алгоритмы

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

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

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

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Формат входных данных
В первой строке вводится число n  (1 ≤ n ≤ 100) – количество вершин в графе. Далее идет n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных
Выведите n чисел – степени вершин графа (по одному числу в строке). 

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

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

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

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

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

Входные данные: В первой строке входных данных содержатся два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N – количество вершин графа, а S – заданная вершина. В следующих N строках записано по N чисел – матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные: Выведите одно целое число – искомое количество вершин.

Примеры

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

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

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

В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.

Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.

Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.
 

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

Выведите на стандартный выход (экран) NUM строк, в каждой из которых по N_i чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
 

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [102438; 124698] числа, у которых ровно 7 различных натуральных делителей, не считая 1 и самого числа. Для каждого найденного числа выведите эти 7 делителей с новой строки в порядке возрастания произведения этих 7 делителей. Делители должны следовать в порядке возрастания.

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [108933; 132757] числа, у которых ровно 2 различных натуральных делителя, не считая 1 и самого числа. Для каждого найденного числа выведите эти 2 делителя с новой строки в порядке возрастания произведения этих 2 делителей. Делители должны следовать в порядке возрастания.

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [289039; 311993] числа,  у которых ровно 8 различных натуральных делителей, не считая 1 и самого числа. Для каждого найденного числа выведите эти 8 делителей с новой строки в порядке возрастания суммы этих 8 делителей. Делители должны следовать в порядке возрастания.

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

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

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

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

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

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

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

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

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

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