Алгоритмы

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1    2    3
4    5    6
7    8    9
а во втором – так:
1    4    7
2    5    8
3    6    9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

Входные данные
Вводятся два целых числа n и m (1 ≤ n, m ≤ 10⁹ ).

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

Примеры

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

Значение выражения \( 27^7 - 3^{11} + 36 - x\) записали в троичной системе счисления, при этом сумма цифр в записи оказалась равной b (вводится с клавиатуры, 0 < b < 100).  Напишите программу, которая выводит на экран минимальное натуральное значение x. Гарантируется, что ответ существует.

Результат арифметического выражения \(9^9 – 3^9 + 9^{19} – 19 \) записали в троичной системе счисления. Напишите программу, которая определит количество цифр "2", "1" и "0"в результирующем числе. Выведите ответ в одной строке, через пробел, в указанном порядке.

Дана функция \(z(x) = ax^3 + bx^2 + cx + d\). Для заданных чисел a, b, c и d, выведите все целые значения x из диапазона от 0 до 1000, при которых функция z(x) принимает нулевое значение.

Входные данные
Программа получает на вход 4 числа: a, b, c и d. Каждое число записано в отдельной строке.

Выходные данные
Выведите все значение x, которые удовлетворяют условию задачи в порядке возрастания. 
 

Примеры

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

 

Примеры

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

У всех жителей Цветочного города спросили его любимый фрукт.  Определите самый любимый фрукт среди всех жителей Цветочного города.

Входные данные
Программа получает на вход текст (количество строк может быть много). Текст заканчивается строкой END!. 

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

Пример

№	Входные данные	Выходные данные
1	apple orange banana banana orange END!	banana

Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы.
Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели построить N порталов. Портал с номером i расположен в точке с координатой x_i . Если в текущий момент времени вы находитесь в одной точке с каким-нибудь порталом, то можете всего за одну секунду телепортироваться в любой другой портал вне зависимости от расстояния между ними. А время, требуемое для преодоления расстояния между точками с координатами p и q без использования порталов равно |p − q| секунд. Андрей является влиятельным гражданином, поэтому он может использовать систему порталов любое количество раз.
Изначально Андрей находится в точке s, а точка проведения олимпиады имеет координату e.
Помогите Андрею понять, как быстро он может попасть на олимпиаду, ведь каждая секунда на счету.

Входные данные
В первой строке входных данных записано одно целое число s — начальное положение Андрея.
Во второй строке записано одно целое число e — место проведения олимпиады. 
В третьей строке записано количество порталов N (2 ≤ N ≤ 2 · 10⁵).
В каждой из N следующих строк записано целое число x_i — координата портала с номером i.
Все числа s, e, x_i по модулю не превосходят 10⁸.

Выходные данные
Выведите одно число — минимальное количество секунд, которое потребуется Андрею для того, чтобы добраться до места проведения олимпиады.
 
Примеры

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

Замечание
Рассмотрим пример из условия. Если бы Андрей не мог пользоваться порталами, он бы смог добраться до точки проведения олимпиады за |0 − 4| = 4 секунды. Однако, можно действовать так:
1. Дойти до портала с номером 1 за |0 − 1| = 1 секунду.
2. Телепортироваться в портал с номером 2 за одну секунду.
3. Дойти от портала с номером 2 до точки проведения олимпиады за |3 − 4| = 1 секунду.
Суммарно получаем 1 + 1 + 1 = 3 секунды.

Подсчитайте количество натуральных делителей числа x (включая 1 и само число x).

Входные данные
Вводится натуральное число x (x < 30000).

Выходные данные
Выведите единственное число - количество делителей числа x.
 

Примеры

№	Входные данные	Выходные данные
1	32	6

Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).

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

Выходные данные
Выведите все делители числа x

 

Примеры

№	Входные данные	Выходные данные
1	32	1 2 4 8 16 32

Найдите самый маленький натуральный делитель числа x, отличный от 1 (2 <= x <= 30000).

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

Выходные данные
Выведите наименьший делитель числа x, отличный от 1.

Примеры

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

Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: \(C^k_n=C^{k-1}_{n-1}+C^{k}_{n-1}\), \(C^0_n = C^n_n=1\).
Входные данные
Вводится 2 числа - n и k.

Выходные данные
Необходимо вывести  значение  \(С^k_n\) .
 

Примеры

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

Входные данные
В первой строке вводится одно число N (3≤N≤100000). Далее в N строках задается по паре чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные
Выведите одну строку: “YES”, если приведённый многоугольник является выпуклым, и “NO” в противном случае.

Примеры

№	Входные данные	Выходные данные
1	3 0 0 0 1 1 0	YES
2	6 0 0 0 2 1 2 1 1 2 1 2 0	NO

Увлекшись машинным обучением, Вася совсем забыл про свои экзамены в университете, завалил их и пошел служить в армию. Однако, и тут ему пригодились его навыки программиста — у работников столовой возникла проблема с тем, что блюда постоянно повторяются, и солдаты начали слишком этому возмущаться. Узнав, что Вася разбирается в программировании, работники попросили его написать программу, которая сделает распределение блюд.
Работники столовой считают, что единственное, что характеризует распределение блюд — их «степень немонотонности» — число разных блюд, которые даются в последовательные приемы пищи. То есть, если представить расписание блюд как массив a, то «степень немонотонности» будет равна количеству индексов i, таких что \(a_i \neq a_{i-1}\) . Для начала вас просят найти не само распределение блюд, а хотя бы максимальную возможную «степень немонотонности», которую можно было бы получить некоторой перестановкой заданного набора блюд. Помогите армейской столовой!
Входные данные
В первой строке содержится число n — количество блюд, которые должны войти в расписание (1 ≤ n ≤ 100).
В следующей строке содержится n чисел a_i — блюда (1 ≤ a_i  ≤ 100). Одинаковые блюда обозначены одинаковыми числами, разные — разными.
Выходные данные
В единственной строке выведите одно число — максимальное возможное значение «степени немонотонности».
 

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

Входные данные
Шесть чисел – коэффициенты A, B и C нормального уравнения двух различных непараллельных прямых (сначала для одной прямой, затем для другой).

Выходные данные
Два числа – координаты точки их пересечения.

Примеры

№	Входные данные	Выходные данные
1	4 -4 0 0 -3 6	2.00000 2.00000

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

Выходные данные
Одна строка “YES”, если отрезки имеют общие точки, и “NO” в противном случае.
 

Примеры

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

Входные данные
Шесть чисел – координаты точки и координаты концов отрезка.

Выходные данные
Одно число – расстояние от точки до отрезка.
 

Примеры

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

Входные данные
Шесть чисел – координаты точки и координаты начала и конца вектора.

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

Примеры

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

Входные данные
Пять чисел – координаты точки и коэффициенты A, B и C уравнения прямой.

Выходные данные
Одно число – расстояние от точки до прямой.
 

Примеры

№	Входные данные	Выходные данные
1	1 5 0 -4 8	3.00000

Входные данные
Пять чисел – координаты точки и коэффициенты A, B и C уравнения прямой.

Выходные данные
Одна строка “YES”, если точка принадлежит прямой, и “NO” в противном случае.

Примеры

№	Входные данные	Выходные данные
1	8 7 2 -3 5	YES

Входные данные
Четыре числа – координаты точки на прямой и координаты вектора нормали к этой прямой.

Выходные данные
Три числа – коэффициенты A, B и C уравнения этой прямой.
 

Примеры

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