Циклы

Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет N раз, и когда они смотрели его в i-й (1<=i<=N) раз, соотношение было Pi:Ni. Известно, что Незнайка и Пончик имели хотя бы один голос, когда впервые увидели отчет. Найдите минимально возможное общее количество голосов, полученных Незнайкой и Пончиком, когда они проверили отчет в N-й раз. Можно предположить, что количество голосов, полученных Незнайкой и Пончиком, никогда не уменьшается.

Входные данные
В первой строке задается целое число N (1<=N<=1000). В следующих N строках записано по 2 числа Pi и Ni (1<=P_i,N_i<=1000). Pi и Ni - взаимно простые числа. 

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 3 1 1 3 2	10	Количество голосов, полученных Пончиком и Незнайкой, изменяется так 2,3 → 3,3 → 6,4. Общее количество голосов в конце составляет 10, что является минимально возможным числом.
2	4 1 1 1 1 1 5 1 100	101	Возможно, что ни Пончик ни Незнайка не получили голосов между моментом, когда они смотрели отчет, и моментом, когда они смотрели его в следующий раз.
3	5 3 10 48 17 31 199 231 23 3 2	6930

Проверьте, есть ли среди данных N чисел нули.

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

Вводится число N, а затем N чисел.

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

Выведите YES, если среди введенных чисел есть хотя бы один нуль, или NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	3 4 19 14	NO

С клавиатуры вводится неотрицательное целое число N - количество чисел. Затем вводятся N чисел.
Напишите программу, которая подсчитывает количество нулей, положительных и отрицательных чисел среди введенных чисел.

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

Формат выходных данных
Необходимо вывести три числа в одной строке, разделенных пробелом: сначала количество нулей, затем количество положительных и отрицательных чисел.

Подсчитайте количество натуральных делителей числа 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 коротышек Цветочного города и сообщил "И вот, братцы, от солнца оторвался кусок и летит прямо к нам. Скоро он упадёт и всех нас задавит. Ужас что будет! Вот пойдите спросите Стекляшкина." Все коротышки знали, что Незнайка болтун, но все-таки решили побежать побыстрее к Стекляшкину и узнать правду. Стекляшкин живет на той же улице, так что коротышкам пришлось бежать по одной прямой. Через 10 секунд i-й коротышка убежал от Незнайки на расстояние ai. Определите максимальное  расстояние между двумя любыми коротышками, которые побежали к Стекляшкину. 

Входные данные
В первой строке записано целое число 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

По данным натуральным n и k вычислите значение \(C^k_n = {n! \over k!(n-k)!}\) (число сочетаний из n элементов по k).

Входные данные
Вводятся 2 числа - n и k (n, k ≤ 30 ).

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

Примеры

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

По данному натуральному n вычислите сумму \(1^2+2^2+...+n^2\).

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

Выходные данные
Необходимо вывести  вычисленную сумму.

Примеры

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

У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше L за один день. Он никогда не спит под открытым небом. То есть он должен находться в отеле в конце дня.
На планете Блук N отелей и все расположены на одной улице. Координата i-го отеля (1<=i<=N) равна xi.
Путешествуя по планете Блук, Громозека запланировал Q переездов. Каждым переездом он планирует менять отель aj на bj (1<=j<=Q). Для каждого переезда найдите минимальное количество дней, которое нужно Громозеке, чтобы добраться от aj-го отеля до bj-го, следуя его принципам.
Гарантируется, что он всегда может поехать из aj-го отеля до bj-го отеля.

Входные данные
В первой строке задается целое число N (2<=N<=10⁵) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x₁<x₂<...<x_N<=10⁹ , x_i+1−x_i<=L). В третьей строке записано число L (1<=L<=10⁹).  В четвертой строке - число Q (1<=N<=10⁵). 
В последних Q строчках находится по два различных числа aj и bj (1<=a_j,b_j<=N). Все числа целые.

Выходные данные
Выведите Q строк. В j-й строке (1<=j<=Q) должно быть указано минимальное количество дней, которое Громозеке нужно, чтобы добраться из  aj-го отеля до bj -го отеля.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5	4 2 1 2	По 1-му переезду он может проехать от 1-го отеля до 8-го за 4 дня следующим образом: День 1: Переезд из 1-го отеля во 2-й отель. Пройденное расстояние - 2. День 2: Переезд из 2-го отеля в 4-й. Пройденное расстояние - 10. День 3: Переезд из 4-го отеля в 7-й. Пройденное расстояние - 6. День 4: Переезд из 7-го отеля в 8-й. Пройденное расстояние - 10.

 

Для целых чисел b ( b >= 2 ) и n ( n >= 1 ) пусть функция f(b, n) определяется следующим образом:
\(f (b, n) = n, когда\ n < b \\ f (b, n) = f (b, floor (n / b)) + (n \ mod \ b), когда \ n >= b\)

Здесь
floor(n / b) обозначает наибольшее целое число, не превышающее n / b;
n mod b обозначает остаток от n, деленный на b.

Менее формально f(b, n) равно сумме цифр n, записанных в базе b. Например, справедливо следующее:
\(f (10,87654) = 8 + 7 + 6 + 5 + 4 = 30\\ f (100,87654) = 8 + 76 + 54 = 138\)

Вам даны целые числа n и s. Определите, существует ли целое число b (b >= 2) такое, что f(b, n) = s. Если ответ положительный, найдите наименьшее из таких b.


Входные данные
В первой строке вводится целое число n (1 <= n <= 10¹¹). Во второй строке - целое число s (1 <= s <= 10¹¹).

Выходные данные
Выведите ответ на задачу. Если ответа нет, то выведите -1.
 

 

Примеры

№	Входные данные	Выходные данные
1	87654 30	10
2	87654 138	100
3	87654 45678	-1
4	31415926535 1	31415926535
5	1 31415926535	-1

 

Пусть S(n) обозначает сумму цифр числа n в десятичной системе счисления. Например, S(123) = 1 + 2 + 3 = 6. Мы будем называть целое число n числом Громозеки, если для всех положительных целых чисел m таких, что m > n, выполняется условие \(\frac {n}{S(n)} <= \frac {m}{S(m)}\). По заданному целому числу K, перечислите K наименьших чисел Громозеки.

Входные данные
На вход подается целое число K (K>=1, K-ое наименьшее число Громозеки не больше 10¹⁵).

Выходные данные
Выведите K строк. В i-й строке должен быть указан i-й наименьший номер Громозеки.
 

 

Примеры

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

 

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

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

Выходные данные
Выведите ответ Yes, если Громозека будет есть такую печеньку, No - если не будет.
 

 

Примеры

№	Входные данные	Выходные данные
1	12	Yes
2	101	No

 

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: P - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

 

Примеры

№	Входные данные	Выходные данные
1	6 G W Y P Y W	Four
2	9 G W W G P W P G G	Three
3	8 P Y W G Y W Y Y	Four

У вас есть целочисленная переменная x. Первоначально \(x = 0\). Кто-то дал вам строку S длины N, и, используя эту строку, вы выполнили следующую операцию N раз. В i-й операции вы увеличили значение x на 1, если Si = I, и уменьшили значение x на 1, если Si = D. Найдите максимальное значение, которое принимает x во время операций (в том числе до первой операции и после последней операции).

Формат входных данных
В первой строке задается число N (\(1<=N<=100\)), во второй - строка S. Длина строки N. Строка содержит только символы I и D.

Формат выходных данных
Выведите максимальное значение x, полученное во время операций.

Громозека собирается принять участие в финальном раунде STCoder Contest. В этом соревновании N задач, пронумерованных от 1 до N. Громозека знает, что на  решение задачи i (\(1<=i<=N\)) требуется Ti секунд. Кроме того, участникам предлагается M видов напитков, пронумерованных от 1 до M. Если Громозека выпьет напиток i (\(1 <= i <= M\)), его мозг будет стимулироваться и время, необходимое ему для решения задачи Pi станет Xi секунд. Это не влияет на время решения других задач.
Участнику разрешается выпить ровно один из напитков до начала конкурса. Для каждого напитка Громозека хочет знать, сколько секунд ему понадобится, чтобы решить все задачи, если он выпьет этот напиток. Предположим, что время, необходимое ему для решения всех задач, равно сумме времени, необходимого для решения отдельных задач. Ваша задача - написать вместо Громозеки программу для расчета времени.

Входные данные
На вход подаются целые числа. В первой строке число N (\(1<=N<=100\)), во второй строке N чисел Ti (\(1<=T_i<=10^5\)). В третьей строке задано число M (\(1<=M<=100\)). Далее идет M строк, в каждой из которых задана пара Pi,Xi (\(1<=P_i<=N\), \(1<=X_i<=10^5\)).


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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 2 1 4 2 1 1 2 3	6 9	Если Громозека выпьет напиток под номером 1, время, необходимое ему для решения каждой задачи, составит 1, 1 и 4 секунды, соответственно, всего 6 секунд. Если Громозека выпьет напиток 2, время, необходимое ему для решения каждой задачи, составит 2, 3 и 4 секунды, соответственно, всего 9 секунд.
2	5 7 2 3 8 5 3 4 2 1 7 4 13	19 25 30

 

В ряд расположены N ящиков. Изначально в i-м ящике слева находится ai конфет.  Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.

Входные данные
В первом строке задается два числа N (\(2<=N<=10^5\)) и x (\(0<=x<=10^9\)).  Во второй строке содержится N целых чисел ai (\(0<=a_i<=10^9\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 2 2	1	Необходимо съесть одну конфету во второй коробке. Тогда количество конфет в каждой коробке станет (2,1,2).
2	6 1 1 6 1 2 0 4	11	Например, можно съесть шесть конфет во второй коробке, две в четвертой и три в шестой. Тогда количество конфет в каждой коробке станет (1,0,1,0,0,1).
3	5 9 3 1 4 1 5	0	Цель уже достигнута
4	2 0 5 5	10	Все конфеты должны быть съедены.

 

Алёна собирает вещи в отпуск. С собой в самолёт она может взять ручную кладь и багаж. Для ручной клади у Алёны есть рюкзак, а для багажа – огромный чемодан.
По правилам перевозки масса ручной клади не должна превосходить S кг, а багаж может быть любой массы (за сверхнормативный багаж Алёна готова доплатить). Разумеется,
наиболее ценные вещи – ноутбук, фотоаппарат, документы и т. д. – Алёна хочет положить в ручную кладь.
Алёна разложила все свои вещи в порядке уменьшения их ценности и начинает складывать наиболее ценные вещи в рюкзак. Она действует следующим образом – берёт
самый ценный предмет, и если его масса не превосходит S, то кладёт его в рюкзак, иначе кладёт его в чемодан. Затем она берёт следующий по ценности предмет, если его можно
положить в рюкзак, то есть если его масса вместе с массой уже положенных в рюкзак вещей не превосходит S, то кладёт его в рюкзак, иначе в чемодан, и таким же образом процесс
продолжается для всех предметов в порядке убывания их ценности.
Определите вес рюкзака и чемодана после того, как Алёна сложит все вещи.

Первая строка входных данных содержит число S – максимально разрешённый вес рюкзака. Во второй строке входных данных записано число N – количество предметов.
В следующих N строках даны массы предметов, сами предметы перечислены в порядке убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по
ценности предмета и т. д.). Все числа натуральные, число S не превосходит 2×10⁹, сумма весов всех предметов также не превосходит 2×10⁹. Значение N не превосходит 10⁵.

Программа должна вывести два числа – вес рюкзака и вес чемодана (вес пустого рюкзака и чемодана не учитывается).

Примеры

№	Входные данные	Выходные данные	Пояснение
1	20 5 6 10 5 2 3	18 8	Максимально возможная масса рюкзака 20 кг. Дано 5 предметов весом 6, 10, 5, 2, 3. Сначала предмет весом 6 кладётся в рюкзак, затем предмет весом 10 тоже кладётся в рюкзак. Предмет весом 5 нельзя положить в рюкзак, так как тогда вес рюкзака станет 21 кг, поэтому предмет весом 5 кладётся в чемодан. Затем предмет весом 2 кладётся в рюкзак, а предмет весом 3 – в чемодан. Вес рюкзака 6 + 10 + 2 = 18, вес чемодана 5 + 3 = 8.

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 1910 = 1·2⁴+0·2³+0·2²+1·2¹+1·2⁰ в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:
10011
11001
11100
01110
00111
10011
…
и результатом игры, следовательно, окажется число 1·2⁴+1·2³+1·2²+0·2¹+0·2⁰ = 28.

Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.
Формат входных данных
Входной файл содержит одно целое число N (0 ≤ N ≤ 32767).
Формат выходных данных
Ваша программа должна вывести в выходной файл одно целое число, равное результату игры.

Примеры

№	Входные данные	Выходные данные
1	19	28

Последовательность чисел a1, a2, …, ai,… называется Фибоначчиевой, если для всех i >= 3 верно, что ai = ai–1 + ai–2, то есть каждый член последовательности (начиная с третьего) равен сумме двух предыдущих. Ясно, что задавая различные числа a1 и a2 мы можем получать различные такие последовательности, и любая Фибоначчиева последовательность однозначно задается двумя своими первыми членами.

Будем решать обратную задачу. Вам будет дано число N и два члена последовательности: aN и aN+1. Вам нужно написать программу, которая по их значениям найдет a1 и a2.


Входные данные
Вводятся число N и значения двух членов последователности: aN и aN+1 (1 <= N <= 30, члены последовательности - целые числа, по модулю не превышающие 100).
Если вы пишите на языке программирования Python, то считывание aN и aN+1 элементов должно быть организовано так: 
x, y = map(int, input().split()).

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

Примеры

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