Информатика

Любитель математики Гоша придумал свою собственную последовательность. Правила в его последовательности следующие:
1) все числа в последовательности имеют свой номер;
2) первый элемент последовательности имеет номер 1;
3) каждое число в последовательности должно делится на свой номер;
4) число с большим номером, должно быть больше, чем число с меньшим номером.

Пример Гошиной последовательности: 1 4 6 8 10 18 21.

По заданному набору чисел определите какое максимальное количество чисел можно выбрать, чтобы составить Гошину последовательность, а также какое максимальное число в ней может быть.


Входные данные
В первой строке записано число N - количество чисел в файле (N <= 10⁵). Далее идет N натуральных чисел (не больше 10⁶), каждое - в отдельной строке.

Входные данные
Выведите два числа через пробел: сначала максимальное количество чисел, которые можно выбрать, чтобы составить Гошину последовательность, затем - максимальное число, которое может быть в этой последовательности.

 

Примеры

№	Входные данные	Выходные данные
1	12 25 17 20 15 6 9 10 12 5 3 4 1	5 25

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

Входные данные 
На вход подается одно число N (10 <= N <= 10⁹).

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

 

Примеры

№	Входные данные	Выходные данные
1	45545	5 5
2	1113	3 1
3	444	4 4

Многие банки при оплате покупок их банковскими картами предлагают систему возврата части потраченных средств, называемую cashback .

Мама Алёны имеет три подобные карты с разными условиями возврата части потраченной суммы. На карту банка RR возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, 5 рублей возвращается и за покупку стоимостью 100 рублей, и 199 рублей. Банк BB возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк ММ возвращает 3% с полной стоимости любой покупки (заметим, что при цене в целом числе рублей, 3% всегда будут составлять целое число копеек), поэтому за покупку в 199 рублей вернется 5 руб. 97 коп.

Алёна любит ходить вместе с мамой за покупками. Мама предложила Алёне определять, какую покупку какой картой оплачивать, чтобы сумма возврата была максимально возможной. Считайте, что оплата любой покупки возможна любой картой. Если какие-то две или все три карты дают лучшую сумму возврата с точностью до копеек, то Алёна выбирает ту из карт, которая ей больше нравится по оформлению. Больше всего Алёна любит карту банка MM, затем идёт карта банка BB, а меньше всего Алёне нравится карта банка RR.

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

Вводится одно целое число S ( 1 <= S <= 10 000 ) — стоимость покупки в рублях.

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

Выведите название банка RR , BB или MM в зависимости от того, картой какого банка выгоднее оплатить эту покупку. А при равенстве суммы возврата - название банка, определённого в условии задачи.

 

Примечание

В первом примере только банк MM вернёт часть суммы покупки. Второй пример разобран в условии задачи.

 

Примеры

№	Входные данные	Выходные данные
1	10	MM
2	199	BB
3	101	RR

На пути к спасению городка Энджел Гроув черный рейнджер Зак Тейлор столкнулся с очередным препятствием. Рейнджер оказался на инопланетном космическом корабле в окружении врагов, и теперь, чтобы освободиться, ему необходимо уничтожить всех врагов в определенном порядке.
Каждый из n врагов обладает силой f_i. Однако среди них имеется главный враг — босс, чья сила равняется сумме сил всех остальных врагов. Так как уничтожение босса требует полной концентрации и сосредоточенности, Зак сможет справиться с ним только после того, как уничтожит всех остальных врагов.
В запасе у рейнджера мало времени, так что он не успевает понять, кто босс. Ему необходима ваша помощь. Восстановите порядок, в котором Заку Тейлору необходимо уничтожать врагов, чтобы выбраться на свободу.

Входные данные
В первой строке находится натуральное число n — количество врагов (3 ≤ n ≤ 10⁵).
Во второй строке находятся n целых чисел f_i, задающих силу каждого врага (-10⁹ ≤ f_i ≤ 10⁹).
Силы врагов заданы в случайном порядке.

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

Примеры

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

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

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

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

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

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

Пример

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

Два друга-биолога Василий и Петр едут в Африку на поезде. Билеты они покупали в разное время и не смогли получить места в одном вагоне. Василий купил билет на место с номером X, а Петр — на место с номером Y .
Все поезда в структуре РЖД комплектуются вагонами с одинаковым числом посадочных мест, равным K. Нумерация мест сквозная: в первом вагоне расположены места с номерами от 1 до K, во втором вагоне — места с номерами от K + 1 до 2K, и так далее. Помогите Василию посчитать,сколько раз он должен перейти из одного вагона в соседний для встречи с Петром.

Входные данные
В первой строке входных данных записано целое число K (1 ≤ K ≤ 10⁹) — число посадочных мест в каждом вагоне.
Во второй строке записано целое число X — номер места Василия.
В третьей строке записано целое число Y (1 ≤ X < Y ≤ 10⁹) — номер места Петра.

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

Примеры

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

Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы.
Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели построить 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 секунды.

Персонаж известной компьютерной игры Марио постарел и почти перестал прыгать. Но совсем недавно он увидел спуск из N ступенек, и его накрыло ностальгией. Марио встал на самую верхнюю ступеньку и решил преодолеть этот спуск при помощи прыжков.
Когда-то Марио знал тысячи различных видов прыжков, но теперь он смог вспомнить только два: короткие и длинные. Короткий прыжок позволяет спуститься на произвольное число ступенек, не большее X, а длинный — на произвольное число, не большее Y (X < Y ). Но в силу возраста Марио не может делать два длинных прыжка подряд и вынужден между ними совершать хотя бы один короткий. При этом Марио не хочет слишком уж сильно ухудшить свои прошлые результаты и поэтому постарается обойтись как можно меньшим числом прыжков.
Помогите Марио посчитать минимальное количество прыжков, требующееся для преодоления всех N ступенек.

Входные данные
В первой строке входных данных записано целое число X — максимальная длина короткого прыжка.
Во второй строке записано целое число Y (1 ≤ X < Y ≤ 10¹⁸) — максимальная длина длинного прыжка.
В третьей строке записано целое число N (1 ≤ N ≤ 10¹⁸) — количество ступенек в спуске.

Выходные данные
В единственной строке выведите целое число — минимальное число прыжков, необходимое Марио для спуска.

Примеры

№	Входные данные	Выходные данные
1	2 3 5	2
2	1 2 4	3
3	1 100 1000000000000000000	19801980198019801

Замечание
На изображениях ниже приведены возможные способы решения первых двух тестов из условия:

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

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

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

Примеры

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

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

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

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

Примеры

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

У вас есть N мешков с конфетами. В каждом мешке некоторое количество конфет. Определите максимальную разность количества конфет двух любых мешков.

Входные данные
В первой строке записано целое число N (1<=N<=100). Во второй строке записаны N чисел ai (1<=a_i<=10⁹) - количество конфет в  i-м мешке.

Выходные данные
Выведите максимальную разность количества конфет двух любых мешков.
 

Примеры

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

Мистер Дункан, директор магазина "Игрушечный сундук Дункана", ежегодно под Рождество жертвует детским фондам определенную сумму денег.  Сумма, которая уходит на благотворительность всегда равна минимальному числу, которое делится на 2 и на число игрушек, проданных за год. По заданному числу проданных игрушек за год (N), определите сумму, которую пожертвует мистер Дункан. 

Входные данные
На вход подается положительное целое число N (1<=N<=10⁹).

Выходные данные
Выведите одно число - сумму, которую пожертвует мистер Дункан.
 

Примеры

№	Входные данные	Выходные данные
1	3	6
2	10	10
3	999999999	1999999998

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

Формат входных данных
В первой строке записаны целое число N (1 ≤ N ≤ 100000) - количество друзей Васи. В следующих N строках записано по два целых числа A_i и B_i (оба числа от 1 до 10⁹) - возможное время приезда i-го друга.

Формат выходных данных
Выведите N пар чисел L_i и R_i - номера дней, в которые приедет и уедет i-й друг соответственно (A_i ≤ L_i ≤ R_i ≤ B_i). Если i-го друга приглашать не нужно, выведите пару чисел -1 -1. Если правильных ответов несколько - выведите любой из них.
 
 

Примеры

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

Увлекшись машинным обучением, Вася совсем забыл про свои экзамены в университете, завалил их и пошел служить в армию. Однако, и тут ему пригодились его навыки программиста — у работников столовой возникла проблема с тем, что блюда постоянно повторяются, и солдаты начали слишком этому возмущаться. Узнав, что Вася разбирается в программировании, работники попросили его написать программу, которая сделает распределение блюд.
Работники столовой считают, что единственное, что характеризует распределение блюд — их «степень немонотонности» — число разных блюд, которые даются в последовательные приемы пищи. То есть, если представить расписание блюд как массив 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

Недавно Вася решил всерьез заняться машинным обучением и распознаванием образов. Однако, наука это обширная, а
начинать с чего-то надо, поэтому его учитель информатики посоветовал ему начать с анализа ASCII рисунков.
Он дал Васе рисунок ASCII-графика, который выглядит следующим образом: он представляет собой прямоугольник n × m, состоящий из символов «*» и «.». Левая верхняя клетка прямоугольника считается началом координат — точкой (0, 0), верхняя строка таблицы — осью OX, направленной слева направо, а левый столбец — осью OY, направленной сверху вниз. Таким образом, клетка (x, y) таблицы отвечает за точку (x, y) на графике функции, и если в этой клетке таблицы стоит «*», то f(x) = y, а противном случае в клетке таблицы стоит «.». Гарантируется, что функция, график которой дан Васе, непрерывна и однозначно определена на всем промежутке, то есть:
В каждом столбце таблицы стоит ровно один символ «*»;
В соседних столбцах символы «*» находятся либо в соседних по стороне, либо в соседних по углу клетках.
Для начала, чтобы проанализировать этот график, Вася хочет найти количество локальных максимумов в нем, то есть таких x, что f(x - 1) > f(x) < f(x + 1) (если одно из значений f(x - 1) или f(x + 1) не определено, счиается, что неравенство выполняется).
Входные данные
В первой строке входного находятся два натуральных числа n и m — количество строк и количество столбцов в таблице соответственно (1 ≤ n, m ≤ 100).
В каждой из следующих n строк содержится строка из m символов — описание таблицы. Гарантируется, что таблица представляет собой график функции, описанной в условии.
Выходные данные
В единственной строке выведите одно число — количество локальных минимумов в данном графике функции.
 

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

На сковородку одновременно можно положить k котлет. Каждую котлету нужно с каждой стороны обжаривать m минут непрерывно. За какое наименьшее время удастся поджарить с обеих сторон n котлет?

Входные данные
Вводятся 3 числа: k, m и n. Все числа не превосходят 32000.

Выходные данные
Вывести время, за которое все котлеты будут обжарены.

Примеры

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

В каждую крайнюю клетку квадратной доски поставили по фишке. Могло ли оказаться, что выставлено ровно k фишек? (Например, если доска 2х2, то выставлено 4 фишки, а если 6х6 - то 20).

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

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

Примеры

№	Входные данные	Выходные данные
1	20	YES
2	13	NO

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

Входные данные
Вводится одно число - размер поля.

Выходные данные
Программа должна вывести одно число - минимальное количество слонов, которые можно расставить на данной доске так, чтобы они контролировали все поле.
 

Примеры

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