| Условие задачи | | Прогресс |
|
Темы:
Остатки
Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).
Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 109, разделенных пробелами.
Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.
|
Ввод |
Вывод |
|
6
1 2 701000 299000 1000 999000
|
2 3 |
3
1 2 3 |
-1 |
| |
![]()
|
|
Темы:
Остатки
На сколько пятерок и троек можно разложить число, чтобы количество разложений было минимально.
Входные данные
На вход подается одно натуральное число N (\(7 < N < 1000\)).
Выходные данные
Выведите два целых числа через пробел: число пятерок и число троек.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8 |
1 1 |
| 2 |
11 |
1 2 |
| 3 |
15 |
3 0 |
| |
![]()
|
|
Темы:
Остатки
Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.
Числами Фибоначчи называется числовая последовательность F1 , F2 , ..., Fn , ... , которая устроена следующим образом: F1 = 1 , F2 = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то Fi = Fi - 1 + Fi - 2 . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .
Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F3 = 3 , F4 = 5 , F5 = 8 , F6 = 13 и F7 = 21 . Среди них на 3 делятся два числа: F3 = 3 и F7 = 21 .
Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.
Входные данные
Первая строка входных данных содержит число L , а вторая — число R ( 1 ≤ L ≤ R ≤ 105 ).
Выходные данные
Выведите единственное число — количество чисел Фибоначчи с номерами от L до R , включительно, которые делятся на 3.
| № |
Входные данные |
Выходные данные |
| 1 |
3
7 |
2 |
| |
![]()
|
|
Темы:
Остатки
Арифметические алгоритмы
На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.
Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.
Лена дала коробку другу, который получил номер l, после чего каждый друг Лены, начиная с друга с номером l, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером r взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.
Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.
Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 1011 , 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 |
Лена ошиблась и такой ситуации быть не могло. |
| |
![]()
|
|
Темы:
Остатки
ЕГЭ - вычислительные задачи
У Анны Николаевны есть N ящиков с конфетами. В i-м ящике лежит Ai количество конфет. Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их M детям. Найдите количество пар (l, r), удовлетворяющих следующим условиям:
- l и r целые числа и удовлетворяют условию 1<=l<=r<=N;
- Al + Al+1 + ... + Ar делится на M.
Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа N (1<=N<=105) и M (2<=M<=109). Вторая строка содержит N чисел Ai (1<=Ai<=109, 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 |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Малая теорема Ферма
Остатки
Быстрое возведение в степень
Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).
Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.
Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел ai (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – li и ri (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.
Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
1 3 7 1 4 100
3
1 3
3 4
2 6 |
21
7
8400 |
| |
![]()
|