Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 33529. Парад
Темы: Циклы   

В параде принимают участие M военных. Командование парада решило, что наиболее эффектное построение военных – в форме квадрата, то есть число участников построения
должно быть точным квадратом. Но поскольку число M может не быть точным квадратом, разрешается разбить военных на несколько полков, каждый из которых строится в форме
квадрата. Для красоты все полки должны быть одинакового размера, также командование парада хочет, чтобы размер каждого полка был как можно больше. Определите максимально возможный размер полка.
Программа получает на вход одно целое положительное число M, не превосходящее 2×109, – количество участников парад. Программа должна вывести одно число – максимально возможный размер полка.

Ввод Вывод
180 36

ID 37011. Таблицы
Темы: Циклы   

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

1

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

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


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

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

Размер таблицы - натуральное число, не превосходящее 100.

Примеры
Входные данные Выходные данные
1 4 1 6 11 16

ID 37012. Кузнечики
Темы: Циклы   

На прямой тропинке на расстоянии 1 метр друг от друга сидят два кузнечика. Время от времени один из кузнечиков прыгает на несколько сантиметров влево или вправо. Требуется узнать, каково было минимальное расстояние, на которое сближались кузнечики в процессе прыжков. (Расстояние считается только в те моменты, когда оба кузнечика сидят на земле).

Входные данные: В первой строке вводится одно число N (1 <= N <= 100) – общее количество прыжков, а затем N чисел, описывающих прыжки. Модуль числа равен длине прыжка в сантиметрах; число отрицательное, если кузнечик начинал этот прыжок по направлению к другому кузнечику, и положительное – если от другого кузнечика. Числа по модулю не превосходят 100 и все отличны от 0. (Кузнечики могут перепрыгивать друг через друга. Гарантируется, что кузнечики не приземляются друг на друга.)

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

Примеры
Входные данные Выходные данные
1 5
1
2
3
4
5
100

ID 37014. Ёлочка
Темы: Циклы   

Вам требуется нарисовать на экране ёлочку высоты H.

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

Выходные данные: Выведите ёлочку из звёздочек (см. примеры).


Примеры
Входные данные Выходные данные
1 2
 *
***
2 4
   *
  ***
 *****
*******

ID 2964. Вложенные циклы - 1
Темы: Цикл for    Цикл while    Циклы   

Вводятся два числа N и K. Выведите количество чисел из диапазона от 1 до N (включительно) таких, что их сумма цифр делится на K.
 
Примеры
Входные данные Выходные данные
1 100 3 33
2 22 4 5

ID 37013. Найти карточку
Темы: Циклы   

Для настольной игры используются карточки с номерами от 1 до N (N – натуральное число, не превышающее 106). Одна карточка потерялась. Найдите ее. 

Входные данные: Дано N, далее N-1 номеров оставшихся карточек.

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

Примеры
Входные данные Выходные данные
1 5
1
2
3
4
5
2 4
3
2
4
1

ID 33533. Клад
Темы: Циклы    Строки   

Путь к кладу задан в виде указаний, какое количество шагов нужно пройти в одном из четырёх направлений: север (N), юг (S), запад (W), восток (E). Весь маршрут записан в виде строки, содержащей последовательность из чисел и следующих за числами букв, указывающих направление перемещения. Например, строка «7N5E2S3E» означает "пройти 7 шагов на север, 5 шагов на восток, 2 шага на юг, 3 шага на восток». В маршруте может быть много команд перемещения, поэтому каждый такой маршрут можно сократить.
Например, ранее приведённый маршрут можно сократить до «5N8E". По данному маршруту до клада сократите его до строки минимальной длины.

Программа получает на вход строку, состоящую из целых неотрицательных чисел, не превосходящих 107 каждое, и одной буквы (N, S, W, E ) следующей за каждым
числом. Других символов (в том числе пробелов), кроме цифр и букв направлений, в строке нет. Длина строки не превосходит 250 символов. Гарантируется, что начальная
и конечная точки маршрута различаются.
Программа должна вывести маршрут, ведущий в ту же точку, записанный в таком же виде, как во входных данных, используя минимальное число символов. Если ответов
несколько, программа должна вывести один (любой) из них.
 

Ввод Вывод Примечание
7N5E2S3E 5N8E Правильным ответом будет также «8E5N»
10N30W20N 30N30W Правильным ответом будет также «30W30N»

ID 33696. Второй максимум
Темы: Циклы   

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

Входные данные
В первой строке задается число N (\(2<=N<=10^4\)). Далее идут N строк, в каждой строке по одному целому числу, не превышающему 105 по модулю. 

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

 

Примеры
Входные данные Выходные данные
1 7
10
15
20
35
14
35
10
35
2 5
10
5
7
11
9
10

ID 38239. Преферанс
Темы: Циклы    Перебор   

В некоторой карточной игре используется колода, в которой 4 туза. В игре принимает участие 4 игрока, каждому из которых раздается равное число карт, а две карты откладываются в прикуп.

Каждый игрок похвастал, сколько у него тузов. Определите, сколько игроков заведомо солгали.

Например, они сказали 1, 1, 1, 2. Следовательно, заведомо солгал 1 игрок. (Какие-то трое могли сказать правду, но все четверо правду сказать не могли, так как тузов всего 4).

Входные данные
Вводятся 4 числа (от 0 до 9 каждое), разделенных пробелом – количество тузов по словам первого, второго, третьего и четвертого игроков.

Выходные данные
Выведите одно число – минимальное количество игроков, которые заведомо солгали. Если все одновременно могли сказать правду, выведите число 0.

Примеры
Входные данные Выходные данные
1 1 1 1 2 1
2 1 1 1 1 0

ID 38270. Детский сад
Темы: Условный оператор    Циклы   

В младшей группе детского сада «Телепузики» всего n детей. Каждый из них, как и любой четырехлетка, легко может начать плакать просто из-за того, что его одногруппники тоже плачут. Ну и что, что он не знает, в чем дело? Товарищи же не могут ошибаться.

Воспитательница работает в детском саду уже много лет, и отлично разбирается в детском настроении. Ей достаточно посмотреть на ребенка, чтобы понять, насколько он сегодня плаксив: заплачет ли он сегодня сам из-за того, что компот невкусный, разрыдается ли из-за того, что Катя и Ваня уже плачут, а он еще нет, или же будет сосредоточенно играть c кубиками, не обращая внимание на слезы и сопли товарищей.

Зная сегодняшнюю плаксивость каждого из детей, определите, будет ли сегодня рыдать вся группа одновременно, или обойдется без массовой истерики.

Входные данные
В первой строке дано целое число n (1n1000) — количество детей в группе. В следующей строке через пробел перечислены n чисел, причем i-е по счету число qi (0qin−1  ) обозначает плаксивость i-го ребенка. Число qi обозначает количество детей, которые должны заплакать, чтобы этот ребенок тоже заплакал. Если qi = 0, значит, этот ребенок точно сегодня заплачет просто так, вне зависимости от своих товарищей. Считается, что ребенок не может начать плакать, если вокруг него не плачет нужное количество детей. Если ребенок начал плакать, то он уже не успокоится до вечера.

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

Примеры
Входные данные Выходные данные
1 4
1 0 1 2
YES
2 3
1 1 1
NO

ID 38287. Башни
Темы: Циклы   

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

Москва в представлении Егора представляет собой длинное прямое шоссе, вдоль которого расположено n башен, пронумерованных в порядке их следования числами от 1 до n. Все башни имеют различные высоты, которые выражаются целыми числами от 1 до n . Высота башни с номером i составляет hi .

Однако Егор не любит возрастающие последовательности. Его разочаровывают тройки башен, таких что с возрастанием их индексов их значения тоже возрастают. Более формально, тройка башен с номерами i , j и k разочаровывает Егора, если i < j < k и hi < hj < h k .

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

Входные данные
Первая строка входных данных содержит единственное число n — количество башен в Москве ( 1 ≤ n ≤ 8000 ).

Вторая строка входных данных содержит n различных натуральных чисел, i -е из них h i — высота i -й башни ( 1 ≤ hi ≤ n ).

Выходные данные
Выведите одно число — количество троек башен, которые разочаруют Егора.

Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ».
 

Примеры
Входные данные Выходные данные
1 5
1 3 4 2 5
5
2 3
3 1 2
0

ID 38330. Дома и магазины
Темы: Одномерные массивы    Циклы   

На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

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

Входные данные
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

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

Примеры
Входные данные Выходные данные Пояснение
1 2 0 1 1 0 1 0 2 1 2 3 В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома: ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него. Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому ответ 3.

ID 38339. Блины
Темы: Цикл while    Одномерные массивы    Циклы   

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

N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai.

Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.

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

Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа ai – количество блинов на тарелке i-го человека. Значения ai даны в порядке неубывания, то есть ai ≤ ai+1. Сумма значений всех ai не превосходит 2·109.

Программа должна вывести одно целое число – минимальное время, за которое все гости закончат есть свои блины после перекладывания части блинов на тарелку нового гостя.

Примеры
Входные данные Выходные данные Пояснение
1 4
1
3
5
6
4 За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.

ID 38499. Раскраска кеглей
Темы: Циклы    Комбинаторика   

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

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

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

 

Примеры
Входные данные Выходные данные
1 2 2 2
1 1 10 10

 

ID 38514. Соревнование с напитками
Темы: Циклы   

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

 

ID 38520. Сумма трех целых
Темы: Циклы    Вложенные циклы   

Вам даны два целых числа K и S. Три переменные X, Y и Z принимают целые значения, удовлетворяющие условию \(0<=X,Y,Z<=K\). Сколько существует различных значений X, Y и Z, таких что \(X+Y+Z=S\)?

Входные данные
На вход подается два целых числа K (\(2<=K<=2500\)) и (\(0<=S<=3\cdot K\)).

Выходные данные
Выведите количество троек X, Y и Z, удовлетворяющих условию.
 

 

Примеры
Входные данные Выходные данные Пояснения
1 2 2 6 Есть шесть троек X, Y и Z, которые удовлетворяют условию:
Х = 0, Y = 0, Z = 2
Х = 0, Y = 2, Z = 0
Х = 2, Y = 0, Z = 0
Х = 0, Y = 1, Z = 1
Х = 1, Y = 0, Z = 1
Х = 1, Y = 1, Z = 0
2 5 15 1 Лишь одна тройка удовлетворяют условию задачи:
Х = 5, Y = 5, Z = 5

 

ID 38522. Уменьшим-увеличим
Темы: Строки    Циклы   

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

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

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

 

Примеры
Входные данные Выходные данные
1
5
IIDID
2
2
7
DDIDDII
0

 

ID 38592. Снежный покров
Темы: Цикл for    Циклы   

В некоторой деревне есть 999 башен высотой 1, (1 + 2), (1 + 2 + 3), ..., (1 + 2 + 3 + ... + 999) метров с запада на восток. Расстояние между двумя соседними башнями 1 метр. Некоторое время шел снег, прежде чем он наконец прекратился. Для двух соседних башен, расположенных на расстоянии 1 метра друг от друга, мы измерили длины частей этих башен, которые не покрыты снегом, и получили a метров для западной башни и b метров для восточной башни. Предполагая, что толщина снежного покрова и высота над уровнем моря одинаковы во всем населенном пункте, найдите общую глубину снежного покрова. Предположим также, что глубина снежного покрова всегда составляет не менее 1 метра.

Входные данные
Во входной строке содержится два целых чисел a и b (\(1\leq a<b<499500=1+2+3+...+999\)). Все входные данные удовлетворяют условию задачи.

Выходные данные
Выведите глубину снежного покрова.
 

 

Примеры
Входные данные Выходные данные Пояснение
1 8 13 2 Высота двух башен - 10 метров и 15 метров соответственно. Таким образом, мы видим, что глубина снежного покрова составляет 2 метра.
2 54 65 1  

 

ID 38622. День программиста
Темы: Целые числа    Циклы    Вложенные циклы   

Перед празднованием Дня программиста офис IT компании украсили последовательностью чисел длины N, a = {a1, a2, a3, ..., aN}. Багз Хантер, сотрудник отдела тестирования, хотел бы поиграть с этой последовательностью. В частности, он хотел бы повторить следующую операцию как можно больше раз.
Для каждого i, удовлетворяющего 1<=i<=N, выполните одно из следующих действий: «разделить ai на 2» и «умножить ai на 3». Нельзя выполнять «умножить ai на 3» сразу для каждого i в течении одной операции, значение ai после любого действия должно быть целым числом. 
Одну операцию Багз Хантер делает за 1 секунду независимо от количества чисел в последовательности. Определите максимум через сколько секунд Багз Хантер вернется к своей работе?

Входные данные
В первой строке записано целое число N (1<=N<=10000). Во второй строке записаны N целых чисел ai (1<=ai<=109).

Выходные данные
Выведите одно число -  максимальное количество секунд, через которое Багз Хантер вернется к своей работе.
 

 

Примеры
Входные данные Выходные данные Пояснение
1 3
5 2 4
3 Последовательность изначально 5,2,4.
Три операции можно выполнить следующим образом:
- сначала умножьте a1 на 3, умножьте a2 на 3 и разделите a3 на 2. Теперь последовательность 15,6,2;
- затем умножьте a1 на 3, разделите a2 на 2 и умножьте a3 на 3. Теперь последовательность 45,3,6;
- наконец, умножьте a1 на 3, умножьте a2 на 3 и разделите a3 на 2. Теперь последовательность 135,9,3.
Далее, с каждым числом можно выполнить только умножение на 3, но это действие недопустимо сразу для всех чисел ai.
Поэтому ответ 3.
2 4
631 577 243 199
0  
3 10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776
39  

 

ID 38646. Сумма цифр числа
Темы: Целые числа    Циклы   

Для целых чисел 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<=1011). Во второй строке - целое число (1<=s<=1011).

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

 

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

 

ID 38647. Путешествие Громозеки
Темы: Циклы   

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

Входные данные
В первой строке задается целое число N (2<=N<=105) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x1<x2?<...<xN?<=10, xi+1?−xi?<=L). В третьей строке записано число L (1<=L<=109).  В четвертой строке - число Q (1<=N<=105). 
В последних Q строчках находится по два различных числа aj и bj (1<=aj?,bj?<=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.

 

ID 38749. Голосование
Темы: Циклы    Конструктив    Разбор случаев   

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

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

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

Примеры
Входные данные Выходные данные Пояснение
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  

ID 38841. Найдите отсутствующего
Темы: Циклы   

Однажды на дистанционном уроке, проводимом при помощи какого-то сервиса видеоконференций, учитель заметил, что отсутствует один из N учащихся класса. Чтобы понять, кто именно отсутствует, учитель попросил каждого присутствующего ученика написать в чат его номер в классном журнале: число от 1 до N. Тогда после окончания урока, просмотрев сохранённый чат, учитель сможет понять, какой из учеников не написал свой номер. Помогите ему - напишите программу, которая сделает это.

Входные данные
В первой строке входных данных записано целое число N (1 <= N <= 105 ) — количество учеников в классе. Следующие N-1 строк содержат по одному числу — номера присутствовавших на уроке учеников в произвольном порядке. Среди этих чисел каждое число от 1 до N, кроме какого-то одного, встречается ровно один раз.

Выходные данные
Программа должна вывести одно число — номер отсутствовавшего ученика.
 

Примеры
Входные данные Выходные данные
1 5
2
5
1
3
4

ID 38922. До до Нового года!
Темы: Циклы   

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

Входные данные
В первой строке задано целое число N (2 <= N <= 105). В следующих N строках расположены целые положительные четные числа pi (100 <= pi <= 106), каждое число в отдельной строке.

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

Примеры
Входные данные Выходные данные
1
3
4980
7980
6980
15950

ID 38926. Снежик Сугробович - 2
Темы: Циклы   

В некотором мире сейчас 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  

ID 38928. До Нового года - 1
Темы: Циклы    Комбинаторика   

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

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

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

 

Примеры
Входные данные Выходные данные
1 2 2 2
1 1 10 10

 

ID 39060. Треугольная последовательность
Темы: Циклы   

Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...

По данному натуральному n выведите первые n членов этой последовательности. В задаче разрешается использовать только один цикл.


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

Выходные данные
Выведите ответ на задачу.
 
Примеры
Входные данные Выходные данные
1 2 1 2
2 5 1 2 2 3 3

ID 39062. Сломанный принтер
Темы: Циклы    Задача на реализацию   

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет.  Например, в цифрах 04, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области.  В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей.  Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей.  Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.


Входные данные
На вход подается число h (0 <= h <= 510).

Выходные данные
Выведите число, которое необходимо напечатать.
 
Примеры
Входные данные Выходные данные
1 15 48888888
2 70 88888888888888888888888888888888888

ID 39063. Среднее значение последовательности
Темы: Циклы   

Дана непустая последовательность целых чисел, оканчивающаяся нулем. Ноль в последовательность не входит, служит признаком ее окончания. Определите среднее значение всех элементов последовательности.

Входные данные 
Вводится последовательность целых чисел, оканчивающаяся числом 0 (само число 0 в последовательность не входит, а служит как признак ее окончания).

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

Примеры
Входные данные Выходные данные
1 4
2
7
0
4.333333333333333

ID 39242. Машина для печенья
Темы: Циклы   

Машина для изготовления печенья производит B печенья в следующие моменты времени: A секунд, 2A секунд, 3A секунд и каждое последующее число, кратное A секундам после включения. Определите сколько печенья будет изготовлено машиной к моменту времени T+0,5 секунд после включения.

Входные данные
Программа получает на вход одну строку, содержащую три числа A, B и T.  1 <= A, B, T <= 20, A <= T. Все числа целые положительные.

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

Примеры
Входные данные Выходные данные
1 3 5 7 10
2 3 2 9 6

ID 39243. Первоклассное сложение
Темы: Циклы   

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

Вам даны положительные целые числа А и B. Посчитайте A+B (в десятичной системе счисления). Если это не связано с переносом в каком-либо разряде, выведите Easy, в противном случает выведите Hard.


Входные данные
Программа получает на вход одну строку, содержащую два целых числа  А и B (1 <= A, B <= 1018).

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

Примеры
Входные данные Выходные данные
1 229 390 Hard
2 123456789 9876543210 Easy

ID 27050. Числовая последовательность - 5
Темы: Циклы   

Вычислить

\(P =  (1 + \sin 0.1 ) \cdot (1 + \sin 0.2 ) \cdot ...\cdot (1 + \sin 1 )\)
 
 
Входные данные
Нет.  

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

ID 27049. Числовая последовательность - 4
Темы: Циклы   

Дано вещественное число х. Вычислить

\(s = {{(x-1)\cdot(x-3)\cdot(x-7)\cdot...\cdot(x-63)}\over{(x-2)\cdot(x-4)\cdot(x-8)\cdot...\cdot(x-64)}}\)

 
Входные данные
Вводится вещественное число х (-50 <= х <= 50). Гарантируется, что для заданного х решение свуществует.

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

ID 27048. Числовая последовательность - 3
Темы: Циклы   

Дано натуральное число N, вещественное число А. Вычислить

\(S = {{1 \over A} + {1 \over {A^2}} + {1 \over A^4} +... + {1 \over A^{2\cdot N - 2}} }\)

 
Входные данные
В первой строке вводится натуральное число N (0 < N <= 10). Во второй строке вводится вещественное число А (-5 <= А<= 5, А!=0).


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

ID 27047. Числовая последовательность - 2
Темы: Циклы   

Дано натуральное число N, вещественное число А. Вычислить

\(P = A \cdot (A  -  N) \cdot (A - 2 \cdot N) \cdot...\cdot (A - N^2)\)
 
Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-10<=А<=10).


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

ID 27046. Числовая последовательность - 1
Темы: Циклы   

Дано натуральное число N, вещественное число А. Вычислить

\(P = A \cdot (A  +  1) \cdot...\cdot (A + N - 1)\)
 
Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-100<=А<=100).

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

 

ID 27003. Сумма ряда - 1
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {(-1)^{n-1} \over{n^n}}\)
 
Выведите на экран сумму такого ряда.

ID 27004. Сумма ряда - 2
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {{1\over 2^n} + {1 \over 3^n}}\)
 
Выведите на экран сумму такого ряда.

ID 27005. Сумма ряда - 3
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {{2\cdot n-1} \over{2^n}}\)
 
Выведите на экран сумму такого ряда.

ID 27006. Сумма ряда - 4
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {1 \over{(3 \cdot n - 2)\cdot(3\cdot n+1)}}\)
 
Выведите на экран сумму такого ряда.

ID 27007. Сумма ряда - 5
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {{n!} \over{(2\cdot n)!}}\)
 
Выведите на экран сумму такого ряда.

ID 27008. Сумма ряда - 6
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {n! \over{n^n}}\)
 
Выведите на экран сумму такого ряда.

ID 27009. Сумма ряда - 7
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {2^n \cdot n! \over{n^n}}\)
 
Выведите на экран сумму такого ряда.

ID 27010. Сумма ряда - 8
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {n! \over{3 \cdot n^n}}\)
 
Выведите на экран сумму такого ряда.

ID 27011. Сумма ряда - 9
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {{n!} \over{(2^n)!}}\)
 
Выведите на экран сумму такого ряда.

ID 27012. Сумма ряда - 10
Темы: Циклы   

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {(2)^{n} \over{(n-1)!}}\)
 
Выведите на экран сумму такого ряда.

ID 39397. Громозека и Алиса - 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

ID 39473. Количество подпоследовательностей
Темы: ЕГЭ    Циклы   

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, начинающиеся с первого элемента последовательности. Найдите количество подпоследовательностей, сумма которых кратна K.

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 108) и число (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

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

Примеры
Входные данные Выходные данные
1 5 3
33
41
19
22
40
2