Algorithmic tasks

1. nails
 https://coderun.yandex.ru/problem/pin?currentPage=1&pageSize=10&rowNumber=1

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

Формат ввода
В первой строке входных данных записано целое число N(2<=N<=100)  — количество гвоздиков.
В следующей строке задано N попарно различных целых чисел ai (0<=ai<=10000)

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

Пример 1
Ввод                Вывод
6
3 13 12 4 14 6      5


2. cheapest_way
https://coderun.yandex.ru/problem/cheapest-way?currentPage=1&pageSize=10&rowNumber=2

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

Формат ввода
Вводятся два числа N и M — размеры таблицы (1<=N <=20, 1<=M<=20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

Формат вывода
Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Пример 1
Ввод                Вывод
5 5                 11
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1


3. most_expensive_way
https://coderun.yandex.ru/problem/print-the-route-of-the-maximum-cost?currentPage=1&pageSize=10&rowNumber=3

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

Формат ввода
В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Формат вывода
Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Пример 1
Ввод               Вывод
5 5                74
9 9 9 9 9          D D R R R R D D
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9


4. Breadth_first_search
«Интересное путешествие»

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

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

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

Примеры
Ввод            Вывод
7               2
0 0
0 2
2 2
0 -2
2 -2
2 -1
2 1
2
1 3


5. knight_move
https://coderun.yandex.ru/problem/knight-move?currentPage=1&pageSize=10&rowNumber=4
Ход конём
Дана прямоугольная доска N×M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. В данной задаче конь может перемещаться на две клетки вниз и одну клетку вправо или на одну клетку вниз и две клетки вправо.
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.

Формат ввода
Входной файл содержит два натуральных числа NxM (1 <= N,M <= 50)

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

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

Ввод      Вывод
31 34     293930


6. bubble_sort
сортировка пузырьком

7. binary_search
Бинарный поиск

8.quick_sort
Быстрая сотировка

9. kafe
https://coderun.yandex.ru/problem/cafe?currentPage=1&pageSize=10&rowNumber=5
 Кафе
Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед (при покупке на сумму 100 рублей и меньше такой купон покупатель не получает).
Однажды Пете на глаза попался прейскурант на ближайшие N дней. Внимательно его изучив, он решил, что будет обедать в этом кафе все N дней, причем каждый день он будет покупать в кафе ровно один обед. Однако стипендия у Пети небольшая, и поэтому он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны. Требуется найти минимально возможную суммарную стоимость обедов и номера дней, в которые Пете следует воспользоваться купонами.

Формат ввода
В первой строке входного файла записано целое число N (0 <=N<=100). В каждой из последующих N строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.

Формат вывода
В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа K1 и К2 — количество купонов, которые останутся неиспользованными у Пети после этих N дней и количество использованных им купонов соответственно.
В последующих К2 строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение K1 максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.

Ввод         Вывод

5            235
35           0 1
40           5
101
59
63


10. needleman_wunsch
НОП с восстановлением ответа
https://coderun.yandex.ru/problem/nop-with-response-recovery?currentPage=1&pageSize=10&rowNumber=6
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

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

Формат вывода
Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.


Пример 1

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


11. linked_components
https://coderun.yandex.ru/problem/connectivity-components/description?currentPage=1&pageSize=10&rowNumber=8

 Компоненты связности
    • легкая
    • dfs
Дан неориентированный невзвешенный граф, состоящий из N вершин и M ребер. Необходимо посчитать количество его компонент связности и вывести их.
Формат ввода
Во входном файле записано два числа N и M (0<N<=100000, 0≤M≤100000). В следующих M строках записаны по два числа i и j (1≤i, j≤N), которые означают, что вершины i и j соединены ребром.
Формат вывода
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в произвольном порядке.

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


12. cheating
https://coderun.yandex.ru/problem/cheating?currentPage=1&pageSize=10&rowNumber=9
Списывание
    • легкая
    • dfs
Во время контрольной работы профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому решил разделить студентов на две группы: списывающих и дающих списывать, и поставить двойки только первым.
У профессора записаны все пары студентов, обменявшихся записками. Требуется определить, сможет ли он разделить студентов на две группы так, чтобы любой обмен записками осуществлялся от студента одной группы студенту другой группы.
Формат ввода
В первой строке находятся два числаN иM— количество студентов и количество пар студентов, обменивающихся записками (1≤N≤102, 0 ≤M≤N(N−1)/2).
Далее в Mстроках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.
Формат вывода
Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Ввод  Вывод
3 2   YES
1 2
2 3

Ввод   Вывод
3 3    NO
1 2
2 3
1 3


13. topsort
Топологическая сортировка
    • легкая
    • topsort
Дан ориентированный граф. Необходимо построить топологическую сортировку.
Формат ввода
В первой строке входного файла два натуральных числаN и M (1≤N,M≤100000) — количество вершин и рёбер в графе соответственно. Далее в M строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.
Формат вывода
Выведите любую топологическую сортировку графа в виде последовательности номеров вершин (перестановка чисел от 1 до N). Если топологическую сортировку графа построить невозможно, выведите -1.

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


14. looking_for_cycle
Поиск цикла.
https://coderun.yandex.ru/problem/cycle-search?currentPage=2&pageSize=10&rowNumber=11

Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его.
Формат ввода
В первой строке дано одно число n — количество вершин в графе ( 1 ≤ n ≤ 500 ). Далее в n строках задан сам граф матрицей смежности.
Формат вывода
Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — номера вершин, которые принадлежат циклу в порядке обхода (обход можно начинать с любой вершины цикла). Если циклов несколько, то выведите любой.

Ввод    Вывод
3       YES
0 1 1   3
1 0 1   3 2 1
1 1 0


15. shortest_way
https://coderun.yandex.ru/problem/shortest-path-length?currentPage=2&pageSize=10&rowNumber=12
Длина кратчайшего пути.

В неориентированном графе требуется найти длину минимального пути между двумя вершинами.
Формат ввода
Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Формат вывода
Выведите L – длину кратчайшего пути (количество ребер, которые нужно пройти).
Если пути нет, нужно вывести -1.

Ввод                     Вывод
10                       2
0 1 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0
5 4


16. path_in_graph
https://coderun.yandex.ru/problem/the-path-in-the-graph?currentPage=2&pageSize=10&rowNumber=13
Путь в графе

легкая
• bfs
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Формат ввода
Первым на вход поступает число N – количество вершин в графе (1 ≤ N ≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Формат вывода
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.
Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

Пример 1
Ввод                         Вывод
10                           2
0 1 0 0 0 0 0 0 0 0          5 2 4
1 0 0 1 1 0 1 0 0 0
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0
5 4


17. fleas
https://coderun.yandex.ru/problem/fleas?currentPage=2&pageSize=10&rowNumber=14
Блохи
• легкая
• bfs
На клеточном поле, размером NxM (2 ≤ N, M ≤ 250) сидит Q (0≤Q≤10000) блох в различных клетках. «Прием пищи» блохами возможен только в кормушке - одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.
Формат ввода
В первой строке входного файла находится 5 чисел, разделенных пробелом: N, M, S, T, Q. N, M - размеры доски (отсчет начинается с 1); S, T - координаты клетки - кормушки (номер строки и столбца соответственно), Q - количество блох на доске. И далее Q строк по два числа - координаты каждой блохи.
Формат вывода
Содержит одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.

Ввод          Вывод
2 2 1 1 1    -1
2 2

Ввод          Вывод
4 4 1 1 16    42
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4