Алгоритмы

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить число безопасных стопок.

Входные данные
Одно число 1≤N≤20.

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

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, AC, BA, BB, BC, CA, CB и CC. Стопки типа AA являются взрывоопасными.

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить количество возможных типов безопасных стопок.

Входные данные
Одно число 1 ≤ N ≤ 20.

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

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.

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

Входные данные
Вводится натуральное число N, не превосходящее 40.

Выходные данные
Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹ − 1.

Дано два массива. Для каждого элемента второго массива определите, сколько раз он встречается в первом массиве.

Входные данные
Первая строка входных данных содержит одно число N (1 ≤ N ≤ 10⁵) – количество элементов в первом массиве. Далее идет N целых чисел, не превосходящих по модулю 10⁹ – элементы первого массива, Далее идет количество элементов M во втором массиве и M элементов второго массива с такими же ограничениями.

Выходные данные
Выведите M чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.

Вывести представление целого числа N в виде произведения простых чисел.

Входные данные
В первой строке находится единственное число N. 2 <= N <= 2³¹ - 1.

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

Вывести все простые числа от M до N включительно.

Входные данные
В первой строке находятся разделённые пробелом M и N. 2 <= M <= N <= 300 000.

Выходные данные
Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

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

Рассмотрим дорогу, подходящую к перекрестку, на котором сходится \(m\) дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в \(m\) различных направлениях — обратно по дороге, по которой он приехал, а также по одной из оставшихся \(m - 1\) дорог. Пронумеруем возможные направления числами от 1 до \(m\) слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 — поворот на самую левую из дорог, и т. д.

Пусть дорога содержит \(n\) полос для движения. Пронумеруем полосы от 1 до \(n\) слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак <<движение по полосам>> разрешает каждой из полос движение по некоторым из \(m\) возможных направлений. При этом должны выполняться следующие условия:

1. если с \(i\)-й полосы разрешено движение в \(a\)-м направлении, а с \(j\)-й полосы — в \(b\)-м направлении, причем \(i < j\), то \(a \le b\);

2. с каждой полосы разрешено движение хотя бы в одном направлении;

3. в каждом направлении разрешено движение хотя бы с одной полосы.

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

Формат входных данных
Строка содержит два целых числа: \(m\) и \(n\) (\(2 \le m \le 50\), \(1 \le n \le 15\)).

Формат выходных данных
Выведите одно число — количество возможных знаков <<движение по полосам>>, которые можно установить перед перекрестком.

В примере возможны следующие варианты знаков <<движение по полосам>>:

На странице сайта размещена карусель с фотографиями. Фотографии в каруселе пронумерованы от 1 до n. Карусель содержит кнопки вперед и назад. При нажатии кнопки вперед, в карусель загружается следующая фотография (фотография с номером на 1 больше). Если в каруселе отображается последняя фотография (с номером n), то при нажатии кнопки вперед загружается первая фотография (фотография с номером 1).
Всего карусель содержит n фотографий. Посетитель сайта сейчас просматривает фотографию с номером m. Фотография под каким номером загрузится в карусель, если посетитель нажмет один раз кнопку вперед?

Формат входных данных
Программа получает на вход две строки. В первой строке записано натуральное число n (n < 10⁹). Во второй - натуральное число m (1≤ m ≤ n). 

Формат выходных данных
Выведите одно число - номер следующей фотографии.

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

Формат входных данных
В первой строке входных данных записано натуральное число N - количество пачек, которые были заказаны. Во второй строке - натуральное число M - максимальное число пачек, которое помещается в одну коробку.

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

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m ( 1 \leq m \leq n (n-1))\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф является турниром, и «NO» в противном случае.

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n-1))\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф является полуполным, и «NO» в противном случае.

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m ( 1 \leq m \leq n (n-1)/2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф является полным, и «NO» в противном случае.

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100) – количество вершин в графе и \(m (0 \leq m \leq n (n - 1)/2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  «YES», если граф является регулярным, и «NO» в противном случае.

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

Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.

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

Выходные данные
Вначале выведите k – число истоков в графе и затем k чисел – номера вершин, которые являются истоками, в возрастающем порядке. Затем выведите информацию о стоках в том же порядке.

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) –  количество вершин в графе и \(m (1 \leq m \leq n (n-1))\) – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите  n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

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

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

Выходные данные
Выведите  n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n - 1) / 2)\)  – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите n чисел – степени вершин графа.

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

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

Выходные данные
Выведите одно число – количество ребер заданного графа.

Простой неориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

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

Выходные данные
Выведите одно число – количество ребер заданного графа.

Входные данные
Пять чисел - коэффициенты A, B и C уравнения прямой и координаты некоторой точки X, Y (точка может быть как на прямой, так и вне ее). Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите три числа - коэффициенты A, B и C уравнения прямой, перпендикулярной заданной и проходящей через заданную точку. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.