Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Банды Фомина №2#30699

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(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

✓ 11✗ 821 100средняяВойти и решать

Марсианская колония#82085

На Марсе строится колония! Каждому жилому модулю присваивается номер от 1 до N. По марсианским законам, модули с простыми номерами получают улучшенную систему жизнеобеспечения.

Глава колонии хочет знать:
1. Сколько модулей получат улучшенную систему?
2. Какие именно это модули?

ВХОДНЫЕ ДАННЫЕ:
Одно число N (1 ≤ N ≤ 10^7) - количество модулей.

ВЫХОДНЫЕ ДАННЫЕ:
Первая строка: количество простых чисел от 2 до N.
Вторая строка: все простые числа от 2 до N через пробел (в порядке возрастания).
Если простых чисел нет, во второй строке ничего не выводить.

Простые числа и разложение на множители Решето Эратосфена

✓ 16✗ 94600лёгкаяВойти и решать

Дробная арифметика#55147

Напишите программу, реализующую сложение, вычитание, умножение и деление дробей. Формат дробей во входных и выходных данных:

знак числа (пишется только в случае, когда его отсутствие изменяет число);
целая часть числа (нулевая целая часть не пишется, если есть числитель и знаменатель);
пробел (не пишется, если отсутствует целая или дробная часть);
числитель (если он не равен нулю);
знак / (если есть числитель);
знаменатель (если есть числитель).

Примеры представления дробных чисел: -7 3/4, 8 1/2, -7/11, 0, 11.

Ограничения (как на входные, так и на выходные данные): целая часть может принимать значения из диапазона 0...30 000, числитель и знаменатель могут принимать значения от 1 до 30 000, при делении второй операнд не равен нулю.

Входные данные
В первой строке вводится дробь (первый операнд), во второй - знак операции ("+" - сложение, "-" - вычитание, "*" - умножение, "/" - деление), в третьей строке - дробь (второй операнд). Обе дроби могут быть сократимы.

Выходные данные
В единственной строке выводится несократимая правильная дробь (результат) в описанном формате.

"Длинная" арифметика НОД и алгоритм Евклида реализация

✓ 2✗ 3—Войти и решать

Марсианские факториалы#55063

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K
различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце - это конечно же нули - ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с 5!=1·2·3·4·5 . А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 - так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N!=1·2·3·...·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Входные данные
В первой строке входных данных содержатся числа N и K, разделенные пробелом, (1 <= N <= 10⁹, 2 <= K <= 1000).

Выходные данные
Выведите число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

Простые числа и разложение на множители Разные системы счисления

✓ 1✗ 0—Войти и решать

Степень для отрицательного показателя#53643

Напишите рекурсивную функцию, возводящую число a в степень n. Гарантируется, что все числа "помещаются" в стандартные вещественные (a и ответ) и целые (n) типы.

Входные данные
Вводится 2 числа - a и n (число n может быть отрицательным).

Выходные данные
Необходимо вывести значение aⁿ

Быстрое возведение в степень Остатки Рекурсия

✓ 1✗ 0—Войти и решать

Круглые числа#53620

Будем называть числа круглыми, если они содержат в своей записи только цифры 0 и 5. Составим последовательность неотрицательных целых круглых чисел в порядке возрастания: 0, 5, 50, 55, 500, 505 и так далее.

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

Входные данные
Вводится одно натуральное число K- номер круглого числа в порядке возрастания.

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

Двоичная система счисления Разные системы счисления

✓ 2✗ 0—Войти и решать

Непохожие числа#48938

Будем называть два натуральных числа \(x\) и \(y\) непохожими, если они различны и нет двух различных отличных от \(1\) чисел \(a\) и \(b\), таких, что и \(x\) и \(y\) делятся как на \(a\), так и на \(b\). Например, 6 и 9 непохожи, так как единственное число, отличное от 1, на которое делятся оба числа "— 3. А вот числа 12 и 18 не являются непохожими, так как оба делятся на 2, 3 и 6.

Задано натуральное число \(x\), а также натуральные числа \(l\) и \(r\). Требуется найти все числа \(y\), такие что \(l \le y \le r\), и числа \(x\) и \(y\) непохожи.

Формат входных данных
На первой строке ввода задано число \(x\) (\(1 \le x \le 10^9\)).

На второй строке ввода задано число \(l\), на третьей строке ввода задано число \(r\) (\(1 \le l \le r \le 10^9\); \(r - l \le 1000\)).

Формат выходных данных
На первой строке выведите число \(k\) "— количество непохожих на \(x\) чисел на отрезке от \(l\) до \(r\), включительно.

На второй строке выведите все эти числа в возрастающем порядке.

НОД и алгоритм Евклида Простые числа и разложение на множители

✓ 11✗ 61800средняяВойти и решать

Уравновесить подарки#44036

У Деда Мороза есть N мешков с подарками. Каждый мешок имеет вес a₁, a₂, ..., a_N. Для равномерной нагрузки на сани Деду Морозу необходимо, чтобы вес всех мешков был одинаковым. Чтобы этого добиться, Дед Мороз своим волшебным посохом может выполнить одну из следующих операций любое количество раз, возможно ноль раз.

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

На каждую операцию у Деда Мороза уходит 1 секунда.

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

Входные данные
Программа получает на вход в первой строке целое число N (2 <= N <= 1000). Во второй строке записаны N чисел a_i - вес i-го мешка с подарками (1 <= a_i <= 10⁹).

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

Примеры

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

НОД и алгоритм Евклида Простые числа и разложение на множители

✓ 58✗ 161900средняяВойти и решать

XOR#39625

Исключающим "или" (XOR) называется булева функция, а также логическая и битовая операция от двух аргументов, результат которой истинен тогда и только тогда, когда один из аргументов истинен, а второй - ложен.
Циклический побитовый сдвиг вправо - операция, при которой младший разряд переносится в начало числа и становится старшим, а все остальные сдвигаются вправо на одну позицию.
К двум 16-битовым числам A и B, записанным в 16-ричной системе счисления, была применена операция исключающего "или", а затем к результату - операция побитового циклического сдвига вправо на K разрядов. Одно из двух исходных чисел было забыто, требуется его восстановить.
Входные данные
в строку через пробел записаны числа A, K и результат X. Числа A и X заданы в 16-ричной системе счисления, K - в десятичной.
Выходные данные
число B.

Примеры

№	Входные данные	Выходные данные
1	1A2B 4 4E5D	FFFF
2	AB00 1 5C9A	1234

Разные системы счисления Системы счисления

✓ 3✗ 191 000средняяВойти и решать

Конфеты детям#38503

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

Арифметические алгоритмы (Теория чисел)Остатки

✓ 2✗ 1—Войти и решать

RSA: Расшифровка#31923

Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел, оканчивающееся нулем, с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (\(3<=p,q<10\)), далее вводится сообщение состоящее из натуральных чисел, каждое не превышающее 100. Сообщение заканчивается нулем.

Выходные данные
Выведите расшифрованное сообщение.

Примеры

№	Входные данные	Выходные данные
1	3 7 1 11 12 0	123

Быстрое возведение в степень МЦКО-10. RSA Расширенный алгоритм Евклида

✓ 6✗ 351 200средняяВойти и решать

RSA. Расшифровать небольшое сообщение.#31918

Даны два простых числа p и q. Надо расшифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод	Вывод
3 7 3 1 11 12	1 2 3

Быстрое возведение в степень МЦКО-10. RSA Остатки

✓ 0✗ 381 400средняяВойти и решать

RSA. Зашифровать небольшое сообщение.#31917

Даны два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод	Вывод
3 7 3 1 2 3	1 11 12

Быстрое возведение в степень МЦКО-10. RSA Остатки

✓ 18✗ 46800средняяВойти и решать

Несократимые дроби#31849

Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем n.

Входные данные
В первой строке задается число знаменателей для которых надо найти количество правильных несократимых дробей N (\(N <=100\)). Каждая последующая строка число n (\(n < 10^9\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 23 23456 7 17	22 11712 6 16

Арифметические алгоритмы (Теория чисел)Функция Эйлера

✓ 215✗ 234600лёгкаяВойти и решать

Задание 16. Программирование. Подсчёт с двойным условием#95098

Напишите программу, которая в последовательности натуральных чисел подсчитывает количество тех чисел, которые одновременно удовлетворяют двум условиям:

Оканчиваются на 0 в системе счисления с основанием 9;
Не оканчиваются на 0 в системе счисления с основанием 7.

Формат входных данных

В первой строке задаётся количество элементов \(N\) (\(1 \le N \le 1000\)). В каждой из следующих \(N\) строк — одно натуральное число.

Формат выходных данных

Одно целое число — количество подходящих чисел.

Остатки

✓ 44✗ 7600лёгкаяВойти и решать

Двоичные единицы#90463

Рассмотрим натуральное число \(x\). Требуется прибавить к нему минимальное возможное целое неотрицательное число \(y\), чтобы двоичная запись получившегося числа \(x+y\) имела ровно \(k\) единиц.

Формат входных данных
Первая строка ввода содержит натуральное число \(x\) (\(1 \le x \le 10^{18}\)).

Вторая строка ввода содержит натуральное число \(k\) (\(1 \le k \le 60\)).

Формат выходных данных
Выведите минимальное возможное целое неотрицательное число \(y\), такое что двоичная запись числа \(x+y\) имеет ровно \(k\) единиц.

Двоичная система счисления

✓ 2✗ 6—Войти и решать

Против постулата Бертрана#90462

Постулат Бертрана утверждает, что для любого \(n \ge 2\) найдётся простое число \(p\), для которого \(n < p < 2n\). Постулат Бертрана был сформулирован в качестве гипотезы в 1845 году французским математиком Бертраном, проверившим её до \(n = 3\,000\,000\), и доказан в 1852 году Чебышёвым.

Петя хочет повторить подвиг Бертрана и убедиться в справедливости его постулата для разных значений \(n\). Однако, поскольку он не сомневается в корректности доказательства Чебышёва, он немного изменил цель: для данного \(n\), Петя хочет найти максимальный по длине отрезок составных чисел, который лежит строго между \(n\) и \(2n\).

Требуется найти такие \(l\) и \(r\), чтобы \(n < l \le r < 2n\), все числа от \(l\) до \(r\), включительно, были составными и \(r - l\) было максимально. Если подходящих отрезков несколько, необходимо вывести тот, у которого \(l\) минимально.

Формат входных данных
На вход подаётся одно целое чиcло \(n\) (\(3 \le n \le 10^7\)).

Формат выходных данных
Выведите искомые \(l\) и \(r\).

Решето Эратосфена

✓ 2✗ 16—Войти и решать

It's All About the Base#90370

Беси пошла компьютерные курсы и восхищена темой «Системы
счисления». Напомним, что число, записанное в системе счисления
B имеет цифровые места, представляющие 1, B, B^2, B^3 … справа
налево. Например, для 10-ой системы счисления мы имеем цифры,
представляющие 1, 10, 100, 1000, … Последовательность цифр 1234
в 10-й системе означает
1(1000) + 2(100) + 3(10) + 4(1).
Та же последовательность в 5-ой системе означает
1(125) + 2(25) + 3(5) + 4(1)
И даёт число 194 в 10-й системе.
Беси заметила, что если основание системы счисления B возрастает,
возрастает и число, им представляемое. Например, 1234 в 7-ой системе
счисления представляет большее число, чем 1234 в 6-ой системе
счисления.

Когда мы записываем число в системе счисления с основанием B,
каждая цифра может быт в диапазоне от 0 до B-1. Поэтому, например,
в 10-й систем счисления, цифры находятся в диапазоне 0..9,
а в 5-ой систем счисления, цифры находятся в диапазоне 0..4.

Можно рассматривать системы счисления с основанием больше чем 10.
Например, компьютерные специалисты часто используют в качестве
основания системы счисления основание 16, и используют буквы A..F
для обозначения величин 10..15. Например, BEEF в 16-ой системе соответствует
11(4096) +14(256) + 14(16) + 15,
что после сложения даёт 48879 в 10-ой системе счисления.
Беси заинтригована концепцией использования оснований больше 10.
Она берёт число N и выписывает его в двух различных системах счисления X и Y,
каждое из которых в диапазоне 10..15,000. Интересно, что в обоих случаях
она получает последовательность из 3 цифр, каждое из которых в диапазоне 1..9.
К сожалению, из-за плохой памяти Беси забыла N X Y. Пожалуйста, помогите
ей по двум 3-цифровым последовательностям, которые она выписала,
определить системы счисления X и Y, которые она использовала.
Заметим, что программа, которая просто будет перебирать все возможные
сочетания X и Y (примерно 15,000^2 вариантов) не пройдёт по времени,
и не получит полный балл.

Формат входных данных

Входной файл начинается с целого числа K, затем оно содержит K строк,
каждая из которых отдельный тест. Каждый тест состоит из двух
3-значных чисел. Первое - число N, записанное в системе счисления с
основанием X, второе - число N, записанное в системе счисления с
основанием Y. N X Y могут различаться для каждого теста.

Формат выходных данных

Ваш вывод должен содержать K строк, по одной для каждого теста.
На каждой строке выведите два числа X и Y для соответствующего теста,
разделённые одиночными пробелами. Гарантируется существование и
единственность решения.

Примечание
Число 8892, записанное в системе счисления с основанием 47 есть 419,
и это же число, записанное в системе счисления с основанием 35 есть 792.

Системы счисления

—Войти и решать

Times 17#89834

Фермер Джон осознал, что разработка программного обеспечения - это прибыльный бизнес и решил писать маленькие программы местного значения.
Его первая программа такая простая: его клиент хочет, чтобы он ввел число N и вывел 17*N, при этом оба числа должны быть в двоичной системе счисления и число N может иметь до 1000 цифр.
PROBLEM NAME: times17
Формат входных данных
* Строка 1: Двоичное представление числа N (не более 1000 цифр).
Формат выходных данных
* Строка 1: Двоичное представление N*17.
Примечание
Двоичное число 10110111 равно 183 десятичное. 183 x 17 = 3111, а это 110000100111 в двоичном виде.

"Длинная" арифметика

—Войти и решать

Awkward Digits#89796

Problem 2: Awkward Digits [Brian Dean]
Бесси учиться конвертировать числа между системами счисления, с различными основаниями, но она делает ошибки, поскольку тяжело держать ручку между копытами.
Когда Бесси записывает результат конвертирования, она всегда записывает одну цифру с ошибкой. Например, если она конвертирует число 14 в двоичную систему, корректный результат будет 1110, но она может написать вместо него «0110» или «1111». Бесси никогда не добавляет и не удаляет цифры, но у нее может получится число с ведущим нулем в результате ее ошибки.
Вам дается ответ, записанный Бесси при конвертировании числа N К основаниям 2 и 3. Определите исходное значение числа N в десятичной системе счисления. Вы можете полагать, что N не превосходит 1 миллиард, и что всегда существует уникальное значение N.
PROBLEM NAME: digits
Формат входных данных
* Строка 1: представление числа N в двоичной системе счисления, одна цифра записана некорректно. (основание=2)
* Строка 2: представление числа N в троичной системе счисления, одна цифра записана некорректно (основание=3).
Формат выходных данных
* Строка 1: корректное значение числа N.
Примечание
Корректное значение числа 14 ("1110" в двоичной системе, "112" в троичной).

Системы счисления

✓ 10✗ 4—Войти и решать