Остатки

В деревне Круглая первые дома построены вдоль главной кольцевой дороги длиной M километров. Эти дома имеют номера от 1 до M. Василий ведет здоровый образ жизни и ежедневно проезжает на велосипеде K километров по этой дороге. Сегодня он начал движение от дома с номером S. Возле какого дома он сегодня закончит свой велопробег? Василий всегда двигается в сторону увеличения номеров домов.

Входные данные
Программа получает на вход три строки. В первой строке записано число M (1 <= M <= 100) -  протяженность главной кольцевой дороги. Во второй строке записано число K (1 <= K <= 10⁵) - количество километров, которые проезжает Василий по этой дороге. В третьей строке записано число S (1 <= S <= M) - номер дома, от которого начал движение Василий.

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

Примеры

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

Для заданного натурального N найдите последнюю ненулевую цифру числа N!.

Входные данные
Программа получает на вход целое число N (0 <= N <= 10⁶).

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

Примеры

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

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


Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и натуральное число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1

 

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

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	4

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

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

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

Примеры

№	Входные данные	Выходные данные
1	7 43 21 13 9 19 17 26 95	2

В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

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


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

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

Примеры

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

 

 

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


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

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	92

 
 

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

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

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	2

 

 

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


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

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	2

 
 

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

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

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	3

У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит Ai количество конфет.  Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- Al + Al+1 + ... + Ar делится на M.

Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=10⁵) и M (2<=M<=10⁹). Вторая строка содержит N чисел Ai (1<=A_i<=10⁹, 1<=i<=N).

Выходные данные
Выведите количество пар (l, r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 4 1 5	3
2	13 17 29 7 5 7 9 51 7 13 8 55 42 9 81	6

На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.

Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.

Лена дала коробку другу, который получил номер l, после чего каждый друг Лены, начиная с друга с номером l, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером r взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.

Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.

Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 10¹¹ , 1 ≤ l, r ≤ n ) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку, и количество конфет в коробке, соответственно.

Выходные данные
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 4 12	2	Любые два друга могут быть сладкоежками, тогда каждый два раза получит коробку конфет и последним, кто возьмёт конфету, будет четвёртый человек.
2	5 3 4 10	3	Сладкоежками могут быть любые три друга, кроме друга, стоящего на третьем месте.
3	10 5 5 1	10	Только один друг возьмёт одну конфетку, но он может быть сладкоежкой, просто он не может взять две конфеты. Все остальные в кругу тоже могут быть сладкоежками, но они не могут взять ни одной конфеты.
4	5 4 5 6	-1	Лена ошиблась и такой ситуации быть не могло.

Дано число. В этом числе необходимо изменить одну цифру таким образом, чтобы новое число делилось на 3 и было бы максимально возможным. В исходном числе нужно
обязательно изменить одну цифру, даже если исходное число уже делилось на 3. Программа получает на вход одно длинное натуральное число. Длина числа может
достигать 100 цифр.
Программа должна вывести другое натуральное число, удовлетворяющее условиям:
1. Новое число должно отличаться от данного ровно одной цифрой.
2. Новое число должно делиться на 3.
3. Новое число должно быть максимально возможным из всех таких чисел.

Примеры

№	Входные данные	Выходные данные
1	123	723

Для выбора водящего в детской игре N человек становятся в круг, после чего произносится считалка. На первом слове считалки указывается на первого человека в кругу, на втором слове – на второго человека и т. д. После N-го человека снова идёт первый человек (все люди в кругу пронумерованы числами от 1 до N, круг зацикливается, после человека с номером N идёт человек с номером 1).
Всего в считалке M слов. Определите, на какого человека придётся последнее слово считалки.
Программа получает на вход два целых положительных числа. Первое число N – количество людей в кругу. Второе число M – количество слов в считалке. Оба числа не превосходят 10⁹.
Программа должна вывести одно целое число от 1 до N – номер человека в кругу на которого придётся последнее слово считалки.

Примеры

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

Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.

Числами Фибоначчи называется числовая последовательность F₁ , F₂ , ..., F_n , ... , которая устроена следующим образом: F₁ = 1 , F₂ = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то F_i = F_i - 1 + F_i - 2 . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .

Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F₃ = 3 , F₄ = 5 , F₅ = 8 , F₆ = 13 и F₇ = 21 . Среди них на 3 делятся два числа: F₃ = 3 и F₇ = 21 .

Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.

Входные данные
Первая строка входных данных содержит число L , а вторая — число R ( 1 ≤ L ≤ R ≤ 10⁵ ).

Выходные данные
Выведите единственное число — количество чисел Фибоначчи с номерами от L до R , включительно, которые делятся на 3.
 

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

Дружественные числа -– это два натуральных числа, таких, что сумма всех делителей одного числа (меньших самого этого числа) равна другому числу, и наоборот. Напишите программу, которая проверяет пару чисел на "дружественность". Используйте функцию, которая вычисляет сумму делителей числа.

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

Выходные данные: Программа должна вывести слово 'YES', если полученные числа – дружественные, и слово 'NO' в противном случае.

Примеры

№	Входные данные	Выходные данные
1	220 284	YES
2	1210 1092	NO

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

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

Примеры

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

 
 

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

Входные данные: В первой строке вводится число N - количество чисел в последовательности (N - положительное число, не превышающее 100) , а затем N целых чисел, по одному в строке (каждое число не превышает по модулю 1000).
Выходные данные: Выведите ответ на задачу

Примеры

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

 
 

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

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

Примеры

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

 
 

n школьников делят k яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не более, чем на 1.
Запрещено использовать какие-либо алгоритмические конструкции (if, while, for и т.п.), кроме арифметических операций 

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

№	Входные данные	Выходные данные
1	7 30	5