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

Поможем дикой природе#56305

Фонд изучения дикой природы в течение \(t\) лет ежегодно выделяет денежные гранты в поддержку исследований северной фауны. На гранты претендуют три организации, одна из которых занимается изучением тюленей, вторая "— оленей, третья "— белых медведей.

Для упрощения бухгалтерского учёта фонд принял следующие решения:

размер любого гранта в денежных единицах должен быть степенью числа 2, то есть равен \(2^k\) для некоторого целого \(k \ge 0\);

все гранты, получаемые одной организацией в одном году, должны иметь различные размеры.

В \(i\)-м году фонд планирует полностью распределить \(n_i\) денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно бОльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в \(i\)-м году общей сумме грантов \(n_i\) определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

В первой строке входных данных записано целое число \(t\) — количество лет (\(1 \le t \le 100\)). В каждой из последующих \(t\) строк записано целое число \(n_i\)"— общая сумма грантов, которую необходимо полностью распределить в \(i\)-м году.

Выходные данные должны содержать \(t\) строк по три целых числа в каждой — суммы грантов, которые следует выделить каждой из трёх организаций в соответствующий год. Если оптимальных вариантов распределения несколько, необходимо вывести любой из них.

Быстрое возведение в степень Жадный алгоритм

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

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

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

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

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

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

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

Степень#42245

Напишите программу, вычисляющую \(2^N\).

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

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

Примеры

№	Входные данные	Выходные данные
1	4	16

Быстрое возведение в степень Цикл for

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

Раз-два-три-четыре-пять корову поменять#39514

N коров (1 ≤ N ≤ 10⁵) Фермера Джона стоят в ряд. i-ая корова слева имеет метку i (1 ≤ i ≤ N).
ФД дал коровам M пар целых чисел s (L₁,R₁)…(L_M,R_M), где 1 ≤ M ≤ 100. Затем он сказал коровам повторить ровно K (1 ≤ K ≤ 10⁹) раз процесс из M шагов:

Для каждого i от 1 до M:
Последовательность коров на позициях Li…Ri слева реверсивно меняют свой порядок.
Выведите метки всех коров слева направо для каждого i, (1 ≤ i ≤ N) после завершения описанного процесса.

Входные данные
Первая строка содержит числа N, M, K. Для каждого 1 ≤ i ≤ M строка i+1 содержит L_i и R_i, два целых числа в интервале 1…N, где L_i<R_i.

Выходные данные
На i-ой строке вывода, выведите i-ый элемент массива после выполнения всех инструкций K раз.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой [1,2,3,4,5,6,7] После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. Повторив оба шага ещё раз получим результат, приведенный в выводе.

Быстрое возведение в степень Вывод формулы Перестановки

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

Число 2 в степени N#33587

Дано натуральное число N (вводится с клавиатуры). Вычислите \(2^N\). Выведите на экран вычисленное значение (\(1<=N<=15\)).

Входные данные
На вход подается одно число N.

Выходные данные
Выведите на экран результат выражения \(2^N\).

Примеры

№	Входные данные	Выходные данные
1	3	8

Быстрое возведение в степень Линейные алгоритмы

✓ 17 494✗ 25 479100лёгкаяВойти и решать

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. Зашифровать числовое сообщение#31919

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

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

Ввод	Вывод
3 7 123456789	1 11 12 16 17 6 7 8 18

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

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

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средняяВойти и решать

Быстрое возведение в степень#31901

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\) при четном n,
\(a^n=a \cdot a^{n-1}\) при нечетном n.

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .

Входные данные
Вводится вещественное число a и целое число n.

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

Нельзя использовать стандартное возведение в степень.

Примеры

№	Входные данные	Выходные данные
1	2 7	128
2	1.00001 100000	2.71827

Быстрое возведение в степень

✓ 371✗ 1 140600лёгкаяВойти и решать

Возведение a в степень b по модулю c#31881

Зная a, b, c (целые неотрицательные числа, не превосходят \(2\cdot10^9\)). Вычислите a в степени b по модулю c (\(a^b mod \ c\)).

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

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

Примеры

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

Быстрое возведение в степень

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

Банды Фомина №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средняяВойти и решать