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

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

Классификация снежинок#31926

Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.

Напишите программу, которая поможет Стелле провести классификацию снежинок.

Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a₁ a₂ a₃ a₄ a₅ a₆ от 1 до 10⁹, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.

Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

Ввод	Вывод
5 1 2 3 4 5 6 3 4 5 6 1 2 3 2 1 4 5 6 6 5 4 3 2 1 2 3 6 5 4 1	2

Примечание
Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.

Быстрая сортировка

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

31922#31922

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

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

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

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA

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

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

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

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

Ввод	Вывод
3 7 1 11 12 16 17 0	1 2 3 4 5

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA

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

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

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

Входные данные
В первой строке вводятся p и q (3<=p,q<100), далее вводится сообщение состоящее из цифр.

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

"Длинная" арифметика МЦКО-10. RSA

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

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

Расширенный алгоритм Евклида#31903

Даны натуральные числа \(a, b, c.\) Если уравнение \(a \cdot x + b \cdot y = c\) имеет решения в целых числах, то выведите через пробел \(НОД(a,b)\), \(x\) и \(y\) (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.

Входные данные
Натуральные числа и не превышают по модулю 10000.

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

Примеры

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

Расширенный алгоритм Евклида

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

Быстрое возведение в степень#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 141600лёгкаяВойти и решать

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

Покраска забора#31880

Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась.
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Left_i и красил до дощечки с координатой Right_i(длину дощечки считать равной 1).
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно.

Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Left_i и Right_i. Все числа - целые
Ограничения:
\(0 <= L <= 2 \cdot 10^9\);
\(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).

Выходные данные
Вывести одно число - длину забора, которую необходимо докрасить Тому.

Примеры

№	Входные данные	Выходные данные
1	20 1 10 20	10
2	10 1 10 10	10
3	100 2 10 30 20 40	70

Быстрая сортировка

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

Анти-QuickSort#31879

Дано число N (1<=N<=1000), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине.

Входные данные: в первой строке задаётся число N
Во второй строке идут N чисел - элементы массива
Выходные данные: выведите требуемую перестановку элементов исходного массива

Примеры

№	Входные данные	Выходные данные
1	5 3 10 1 20 7	3 20 7 1 10

Быстрая сортировка

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

Сложить две дроби#31872

Даны две рациональные дроби: \(a \over b\) и \(c \over d\). Сложите их и результат представьте в виде несократимой дроби \(m \over n\).

Входные данные
Программа получает на вход 4 натуральных числа a, b, c, d, не превосходящих 100.

Выходные данные
Программа должна вывести 2 натуральных числа m и n такие, что \({m \over n} = {a \over b}+ {c \over d}\) и дробь \(m \over n\) – несократима.

Примеры

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

НОД и алгоритм Евклида

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

Применение Малой Теоремы Ферма#31866

Дано число a и простое число p. Найти такое минимальное число x, что \((a * x) \% p = 1\).

Входные данные
На вход подаются два натуральное числа a, p (\(a,\ p <= 10^{18} \)).

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

Примеры

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

Малая теорема Ферма

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

Сумма функции Эйлера#31850

Посчитать сумму функций Эйлера вида: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\alpha)\), где \(p\) - простое число, \(\alpha\)- натуральное число.

Входные данные
В одной строке через пробел подаются два числа \(p\) и \(\alpha\) (\(p <=11, \alpha <=60 \)).

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

Пример

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

Функция Эйлера

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

Расчет асимптотики - 4#31799

Для приведенного ниже кода, найдите асимптотику:

#include <bits/stdc++.h>
main()
{
    std::string s;
    std::cin >> s;
    int n = s.size(), p[50003], j, i = 1;
    for (; i < n; i++)
    {
        j = p[i - 1];
        for (; j && s[i] != s[j]; j = p[j - 1]);
        p[i] = (s[i] == s[j] ? ++j : j);
    }
    std::cout << n - p[n - 1];
}

1) O(n^2) 2) O(nsqrt(n)) 3) O(nlogn) 4) O(n)

Z-функция. Префикс-функция

600лёгкаяВойти и решать

Расчет асимптотики - 2#31797

Для приведенного ниже кода, найдите асимптотику:

int n;
vector <int> arr(n);
next_permutation(arr.begin(), arr.end());

1) O(n!) 2) O(n) 3) O(1) 4) O(nlogn)

Перестановки

500лёгкаяВойти и решать

Расчет асимптотики - 8#31796

Для приведенного ниже кода, найдите асимптотику:

#include <bits/stdc++.h>
using namespace std;

vector < vector<int> > g;
vector <int> color;

void dfs(int v, int p)
{
	color[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p)
			continue;
		if (color[to] == 1)
		{
			cout << "YES";
			exit(0);
		}
		if (color[to] == 0)
			dfs(to, v);
	}
	color[v] = 2;
}

int main()
{
	int n, m, a, b;
	cin >> n >> m;

	g.resize(n);
	color.resize(n);

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(0, -1);
	cout << "NO";
	return 0;
}

1) O(n) 2) O(m) 3) O(n + m) 4) O(nm)

Обход в глубину

800лёгкаяВойти и решать

Монетки#31794

В Волшебной стране используются монетки достоинством A₁, A₂,..., A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы сначала поступает число N (1 <= N <= 10⁹), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A₁, A₂,..., A_M (1 <= A_i <= 10⁹).

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

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Ввод	Вывод
100 6 11 20 30 40 11 99	3 40 30 30

Рекурсивный перебор Рекурсия

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

Кинотеатр#31791

В первом ряду кинотеатра N + 2 мест, крайние места заняты персоналом кинотеатра, но N мест посередине свободно. K школьников входят в зрительный зал по очереди, и, конечно же, каждый школьник достаёт спиннер и начинает его крутить до начала сеанса. Поэтому каждый школьник выбирает себе место как можно дальше от уже занятых мест. А именно, школьник находит самый большой свободный участок в ряду (любой, если таких несколько) и садится посередине него. Если число свободных мест на этом участке было нечётно, то школьник садится точно посередине участка, тогда слева и справа от него остаётся поровну свободных мест. Если же это число чётно, то школьник выбирает одно из двух свободных мест посередине, тогда с одной стороны от школьника будет на одно свободное место больше, чем с другой стороны.

По данным числам N и K определите, сколько мест осталось свободными с двух сторон от школьника, который занял место последним (K-м по счёту).

Программа получает на вход два целых числа N и K, 1 ≤ K ≤ N ≤ 10¹⁸, и должна вывести два целых числа в порядке неубывания – количество свободных мест с двух сторон от школьника, который последним занял место в ряду.

Ввод	Вывод	Примечание
10 1	4 5	В зале 10 свободных мест, первый школьник сел посередине, с одной стороны от него 4 места, с другой стороны – 5.
10 2	2 2	Второй вошедший в зал школьник садится посередине группы из 5 свободных мест, с каждой стороны от него остаётся по 2 свободных места.
10 3	1 2	После того, как два школьника сели на места, в зале остались группы свободных мест из 4, 2, 2 мест. Третий школьник садится посередине группы из 4 мест, поэтому с одной стороны от него 1 место, с другой стороны – 2 места.

Вывод формулы Задачи на моделирование

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