Циклы

На соревнованиях по шахматной композиции каждому участнику дается 10 задач для решения. За каждую задачу можно получить от 0 до 5 баллов. За правильно решенную задачу участнику начисляется 5 баллов. Если задача решена не полностью или не верно, то участнику дается вторая попытка. В этом случае за задачу участник получает балл равный среднему баллу за две попытки, округленный по правилам математики. 
Баллы выставляются по порядку от первой до последней решенной задачи.

Маленький Витя Ч., участвуя на своем первом в жизни соревновании, забыл сколько задач он решил. Витя Ч. помнит, что получил всего 10 оценок, а также сами оценки по порядку.
Определите сколько всего задач решил Витя Ч., за сколько задач он получил максимальный балл с первой попытки, а также общую сумму баллов, которую он набрал.


Входные данные
Программа получает 10 строк, в каждой из которых записано по одному неотрицательному числу от 0 до 5. 

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

Примеры

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

Фермер Джон упорядочил N своих коров (1 ≤ N ≤ 1000) каждая из которых имеет одну из двух пород Holsteins или Guernseys. Он зафиксировал этот порядок в виде строки из N символов, каждый из которых либо H, либо G соответственно. К несчастью, когда коровы прибыли на ферму и он снова их выстроил, они образовали строку, отличную от исходной.

Назовём эти две строки A и B, где A - исходная строка, которую он хотел увидеть, B - строка которая получилась по прибытию коров. ФД попросил помощи у кузена Бена.

После нескольких месяцев работы, Бен создал замечательную машину MCBF-3000, которая способна взять любую подстроку и поменять в ней все G на H, а все H на G. Теперь ФД хочет узнать минимальное количество применений этой машины, которые позволят превратить строку B в строку A. Помогите ФД.

Входные данные
Первая строка содержит N, а следующие две строки содержат строки A и B. Каждая из строк состоит только из символов H и G.
Выходные данные
Выведите минимальное количество раз применения машины MCBF-3000 для трансформации строки B в строку A.

Примеры

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

Алиса и Громозека пошли гулять по городу. Заходя в первое кафе, Алиса посмотрела на часы и запомнила время входа. Далее она запоминала только количество минут, которое они с Громозекой тратили между двумя посещенными кафе (от входа в одно кафе, до входа в другое). По окончании прогулки, Алиса решила восстановить хронологию - время входа в очередное кафе.
Напишите программу, которая определит, в какое время Алиса и Громозека заходили в очередное кафе. 

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.
 

Примеры

№	Входные данные	Выходные данные
1	07:00 4 10 5 3	07:00 07:10 07:15 07:18

Среди чисел от 1 до N определите сколько чисел с максимальным количеством четных цифр в системе счисления с основанием r. Четными цифрами в любой системе счисления будем считать цифры 0, 2, 4, 6, 8.

Входные данные
Программа получает на вход 2 числа: N (1< N <= 10⁵) и r (2 <= r <= 9).

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

Примеры

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

На вход программы поступают пары чисел: натуральное число N и основание системы счисления r, в котором записано число N. Признак окончания ввода - пара 0 0. Выведите на экран пару чисел с максимальной суммой. Числа выводить в десятичной системе счисления. Под парой в данной задаче будем понимать два числа, расположенных рядом.

Входные данные
На вход подается неизвестно количество строк. В каждой строке, кроме последней, записаны по 2 числа: N (1 <= N <= 10⁷) и r (2 <= N <= 9). В последней строке записана пара 0 0 (признак окончания ввода).

Выходные данные
Выведите на экран ответ  пару чисел с максимальной суммой. Если таких пар несколько выведите первую из них.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 5 21 4 1 3 1 8 2 3 0 0	3 9	В исходных данных имеем такие числа 35, 214, 13, 18, 23 Пары следующие: (35, 214), (214, 13), (13, 18), (18, 23) Пара с наибольшей суммой (35, 214). В десятичной системе счисления это числа (3, 9) Ответ: 3 9

При каком минимальном натуральном нечетном числе n, программа выведет на экран число 3?
 

Python
s = 0 k = 0 for i in range (5600, n, 10): if i % 10 <= i // 100 % 10: k += 1 print(k)

При каком минимальном натуральном нечетном числе n, программа выведет на экран число 3. 
 

Python
s = 0 k = 0 for i in range (2461, n, 10): if i % 100 // 10 > i // 100 % 10: k += 1 print(k)

При каком минимальном натуральном нечетном числе n, программа выведет на экран число 17. 
 

Python
s = 0 k = 0 for i in range (2000, n): if i // 10 % 10 < i % 10: k += 1 print(k)

При каком минимальном натуральном числе n, программа выведет на экран строку 34 26.
 

Python
s = 0 k = 0 for j in range(2225, n):     k += j % 100 // 10     s += j // 1000 % 10 print(k, s)

При каком минимальном натуральном числе n, программа выведет на экран строку 10 90.
 

Python
s = 0 k = 0 for j in range(1000, n): k += j % 1000 // 10 s += j % 10 print(k, s)

При каком минимальном натуральном числе n, программа выведет на экран строку 16 23.
 

Python
s = 0 k = 0 for j in range(1111, n): k += j // 100 % 10 s += j // 10 % 10 print(k, s)

При каком минимальном натуральном числе n, программа выведет на экран строку 6 13.
 

Python
s = 0 k = 0 for j in range(125, n): k += j // 100 % 10 s += j // 10 % 10 print(k, s)

При каком минимальном натуральном числе n, программа выведет на экран два числа, такие, что первое - четное, второе - нечетное.
 

Python
s = 0 k = 0 for j in range(14, n): k += j // 10 % 10 s += j % 10 print (k, s)

Снежик Сугробович положил в ряд N ёлочных шаров, для того чтобы их покрасить. Он решил, что каждый шар будет одним из K цветов. При этом Снежик Сугробович хочет, чтобы любые два соседних ёлочных шара  были окрашены в разные цвета. Найдите количество возможных способов раскрасить ёлочные шары.

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).

 

Примеры

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

 

В некотором мире сейчас 31 декабря и все веселье только начинается. Снежик Сугробович слепил N больших снежков и расположил их в ряд слева направо. На каждом i-м снежке, если считать слева (1 <= i <= N), он написал целое число ai. Он предлагает вам сыграть в игру. Снежик Сугробович разрешил сломать не более N − 1 снежков по вашему выбору. 

Допустим, осталось K снежков. Снежик Сугробович будет удовлетворен и подарит вам хороший подарок, если для каждого целого числа i (1<=i<=K) на i-м снежке, если считать слева оставшиеся снежки, будет написано целое число i.
Найдите минимальное количество снежков, которое вам нужно сломать, чтобы получить подарок. Если не получится, то выведите -1.

Входные данные
В первой строке программа получает на вход целое число N (1 <= N <= 200000). Во второй строке - N натуральных чисел ai (1<=ai<=N). 

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 1 2	1	Сломайте первый снежок, числа на остальных снежках будут удовлетворять условию Снежика Сугробовича
2	3 2 2 2	-1
3	10 3 1 4 1 5 9 2 6 5 3	7
4	1 1	0

Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет 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

У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше 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

 

Громозека собирается принять участие в финальном раунде 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	Все конфеты должны быть съедены.