Алгоритмы

Дан массив чисел. Необходимо записать в другой массив, все числа Фибоначчи исходного массива. Если в исходном массиве нет чисел Фибоначчи, программа должна вывести число 0.

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

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

Примеры

№	Входные данные	Выходные данные
1	6 4 14 5 8 12 13	5 8 13

Дан массив чисел. Необходимо записать в другой массив все простые числа исходного массива. Если в исходном массиве нет простых чисел, программа должна вывести число 0.

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

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

Примеры

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2 3 5

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты xi и yi. Все числа по модулю не превосходят 104.

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

Ввод	Вывод
4 0 0 3 4 3 1 6 0	16.0000000000 12.0000000000

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

Входные данные
В первой строке задается число N (\(3<=N<=10^5\)). Далее идут N строк, по одному числу в каждой строке.

Выходные данные
Выведите третий максимальный элемент.
 

 

Примеры

№	Входные данные	Выходные данные
1	7 10 15 35 35 14 35 10	35
2	5 10 5 7 11 9	9

 
 

Дано натуральное число \(n  <= 10^9,\) определите количество натуральных чисел, меньших \(n\) и взаимно простых с \(n\). Это число обозначается \( f(n) \)и называется фи-функцией Эйлера. Сложность алгоритма должна быть \( O(\sqrt{n})\) .

Входные данные
На вход подается натуральное число n.

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

 

Примеры

№	Входные данные	Выходные данные
1	2	1

Примеры

№	Входные данные	Выходные данные
1	4 2	6

Даны натуральные числа a, b, c. Если уравнение \(ax+by=c\) имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.

Входные данные 
Вводятся три натуральных числа.

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

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
 

Примеры

№	Входные данные	Выходные данные
1	1 2 3	1 1
2	10 6 8	2 -2

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

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

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

Ввод	Вывод
1 2 1000	1000
2 1 1000	1000
3 6 1000	333 1

Дано два целых числа x и y - координаты точки.
Необходимо определить цвет этой точки на рисунке. 
Для вывода цветов используйте следующие обозначения:
W - белый (все точки, находящиеся за границей рисунка, считаются белыми)
G - зеленый
Y - желтый
R - красный
B - черный (если точка попала на границу областей рисунка)

Одна клеточка рисунка равна 1.

Картинку можно увеличить, щелкнув по ней (откроется в новом окне).

 

Примеры

№	Входные данные	Выходные данные
1	-6 2	W
2	0 1	R

n школьников делят k яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не более, чем на 1.
Запрещено использовать какие-либо алгоритмические конструкции (if, while, for и т.п.), кроме арифметических операций 

Входные данные: Программа получает на вход числа n и k (по одному в строке).
Выходные данные: Программа должна вывести количество школьников, которым достанется яблок меньше, чем некоторым из их товарищей.
Примеры

№	Входные данные	Выходные данные
1	7 30	5

Требуется определить в заданном массиве количество элементов, равных искомому числу.

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

В первой строке вводится одно натуральное число N, не превосходящее 10⁵: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 10⁹, каждое следующее не меньше предыдущего.

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

В четвертой строке вводится M натуральных чисел, не превосходящих 10⁹.

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

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

Если в массиве нет такого числа, выведите 0.

Примеры

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

Дано натуральное число N (вводится с клавиатуры). Вычислите \(2^N\). Выведите на экран вычисленное значение (\(1<=N<=15\)).


Входные данные
На вход подается одно число N.

Выходные данные
Выведите на экран результат выражения \(2^N\).
 
 

Примеры

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

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

Входные данные 
Программа получает на вход одно натуральное четное число n (\(3<n<2 \cdot 10^5\)).

Выходные данные 
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.
 

Примеры

№	Входные данные	Выходные данные
1	4	2 2
2	6	3 3

Проверьте, является ли число простым.

Входные данные 
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.

Выходные данные 
Необходимо вывести  строку prime, если число простое, или composite, если число составное.
 

Примеры

№	Входные данные	Выходные данные
1	5	prime

Дано целое число N. Рассмотрим последовательность S₁S₂S₃...S_k..., где каждая группа цифр S_k состоит из записанных одно за другим чисел от 1 до k. Например, первые 75 цифр последовательности выглядят так:

112123123412345123456123456712345678123456789123456789101234567891011123456.

Требуется написать программу, которая определит: какая цифра находится на N-ой позиции в построенной последовательности.

Входные данные
Ввод содержит одно число N (0 < N < 32768).

Выходные данные
Выведите цифру, которая стоит на N-ой позиции в последовательности.
 

Ввод	Вывод
3	2
20	5

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

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

Выходные данные
Выведите слово "double", если слон угрожает двум другим фигурам, в противном случае выведите слово "no".

 

Пример

№	Входные данные	Выходные данные
1	4 4 5 5 6 6	double

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ N, M ≤ 200.

Выходные данные
Вывести одно число - количество грядок на садовом участке.


Примеры

№	Входные данные	Выходные данные
1	5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####	5

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

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

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

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

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

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