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

Лесопилка#33135

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

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

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

Входные данные

На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.

Выходные данные

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

Ввод	Вывод
2 30 7 20 80	7

Динамическое программирование Остатки

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

Подпоследовательность#31927

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до 10⁹, разделенных пробелами.

Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

Ввод	Вывод
6 1 2 701000 299000 1000 999000	2 3
3 1 2 3	-1

Остатки

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

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

Кролик Клевер#31884

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

Формат входных данных
Программа получает на вход два числа: N - количество друзей у кролика (не более 1000), K - количество яблок (не более 1000000). Каждое число записано в отдельной строке.

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

Линейные алгоритмы Остатки

✓ 7 615✗ 7 425200лёгкаяВойти и решать

Разложение числа на 5 и 3#30771

На сколько пятерок и троек можно разложить число, чтобы количество разложений было минимально.

Входные данные
На вход подается одно натуральное число N (\(7 < N < 1000\)).

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

Примеры

№	Входные данные	Выходные данные
1	8	1 1
2	11	1 2
3	15	3 0

Остатки

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

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

ABCD-код#21810

Вася часто ходит в гости к Пете. Для того, чтобы попасть к Пете во двор, надо ввести код,

состоящий из четырех цифр. Обычно друзья ходили вместе, но в этот раз Вася пришел один, а

Петя ждет его у себя.

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

факт, что квадрат числа, составленного из первых двух цифр кода, в сумме с квадратом числа,

состоящего из последних двух цифр кода, имеет при делении на семь остаток один. То есть, если код

представляет собой «ABCD», где «A», «B», «C», «D» — некоторые цифры, тогда AB²+CD² имеет

остаток 1 при делении на 7. Например, код 2843, является одним из возможных кодов, поскольку

28² + 43² = 2633 = 376 · 7 + 1, а 8243 — нет, поскольку 82² + 43² = 8573 = 1224 · 7 + 5.

У Васи есть несколько вариантов того, каким может быть код. Помогите ему определить, какие

из вариантов могут быть кодом от входа в Петин двор.

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

В первой строке находится число t (1 ≤ t ≤ 10 000) — число вариантов кода,

которые помнит Вася. В следующих t строках содержится по четыре цифры — варианты кода.

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

В ответе выведите t строк. В i-й строке выведите «YES», если i-й код может быть кодом

для входа в Петин двор, иначе выведите «NO».

Вычисление по заданной формуле Остатки

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

15501#15501

Используя оператор выбора напишите программу к следующей задаче:
Дано натуральное число N (N>=4).
1) Если оно делится на 4, вывести на экран строку N=4*k (где k — соответствующее частное);
2) если остаток от деления на 4 равен 1, вывести на экран результат N=4*k + 1;
3) если остаток от деления на 4 равен 2, вывести на экран результат N=4*k + 2;
4) если остаток от деления на 4 равен 3, вывести на экран результат N=4*k + 3.

Пример 1

входные данные

выходные данные

12=4*3

Пример 2

входные данные

выходные данные

22=4*5+2

Остатки Условный оператор

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