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

Наибольшая строка#31840

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

При решении этой задачи запрещено использовать циклы и слово max.

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

Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков и строка содержит только десятичные цифры.

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

Выведите максимальную цифру, которая встречается во введенной строке.

Примеры

№	Входные данные	Выходные данные
1	11111111	1

Рекурсия

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

Вычисление факториала#31839

Составить программу с рекурсивной функцией для расчета факториала.

Входные данные
В первой строке вводится натуральное число N ( N<=12 ).

Выходные данные
Выведите факториал числа.
Примеры

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

Рекурсия

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

Сумма битов#31838

Составить программу с рекурсивной функцией для расчета суммы битов в натуральном числе.

Входные данные
В первой строке вводится натуральное число N ( N<=10⁹ ).

Выходные данные
Выводите сумму битов.

Примеры

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

Рекурсия

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

Произведение битов#31837

Составить программу с рекурсивной функцией для расчета произведения битов в натуральном числе.

Входные данные
В первой строке вводится натуральное число N ( N<=10⁹ ).

Выходные данные
Выводите произведение битов.

Примеры

№	Входные данные	Выходные данные
1	16	0
2	7	1

Рекурсия

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

31824#31824

Выберите тип устройства Флэш-карта

1) Память
2) Ввод
3) Вывод
4) Не знаю

Экзамены и диагностики

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

31823#31823

Выберите тип устройства Микрофон

1) Память
2) Ввод
3) Вывод
4) Не знаю

Задача на реализацию

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

31822#31822

Выберите тип устройства Принтер

1) Память
2) Ввод
3) Вывод
4) Не знаю

Задача на реализацию

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

31821#31821

Выберите тип устройства Лазерный диск

1) Память
2) Ввод
3) Вывод
4) Не знаю

Экзамены и диагностики

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

31820#31820

Выберите тип устройства Монитор

1) Память
2) Ввод
3) Вывод
4) Не знаю

Задача на реализацию

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

31818#31818

Выберите тип устройства Клавиатура

1) Память
2) Ввод
3) Вывод
4) Не знаю

Ввод, вывод данных

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

Скобки-2#31804

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

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

В первой строке находится единственное число N. \(1 <= N <= 14\), N - чётное.

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

Каждое выражение выводится в отдельной строке.

Примеры

№	Входные данные	Выходные данные
1	2	() []
2	4	(()) [[]] [()] ()[] []() ()() ([]) [][]

Рекурсия

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

Разложение на слагаемые#31803

Требуется вывести все различные представления натурального числа N в виде суммы натуральных чисел. Представления, отличающиеся друг от друга порядком слагаемых, не являются различными.

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

Входная строка содержит целое число N (2 ≤ N ≤ 40).

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

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

Примеры

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

Рекурсия

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

Расчет асимптотики - 9#31800

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

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

int main()
{
	int n, m;
	vector < vector<int> > up1(n, vector <int>(m));
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		vector <int> L(m + 1, 1), R(m + 1, m);
		stack <int> q;
		for (int j = 1; j <= m; j++)
		{
			while (!q.empty() && up1[i][j] < up1[i][q.top()])
			{
				R[q.top()] = j - 1;
				q.pop();
			}
			q.push(j);
		}
		while (!q.empty())
			q.pop();
		for (int j = m; j >= 1; j--)
		{
			while (!q.empty() && up1[i][j] < up1[i][q.top()])
			{
				L[q.top()] = j + 1;
				q.pop();
			}
			q.push(j);
		}
		for (int j = 1; j <= m; j++)
			ans = max(ans, up1[i][j] * (R[j] - L[j] + 1));
	}
	cout << ans;
	return 0;
}

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

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

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

Расчет асимптотики - 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лёгкаяВойти и решать

Расчет асимптотики - 3#31798

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

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

int K;

struct query
{
    int l, r, ind;
};

bool cmp(query a, query b)
{
    if (a.l / K != b.l / K)
        return a.l / K < b.l / K;
    else
        return a.r < b.r;
}

int main()
{
    int n, q;
    cin >> n >> q;
    // для простоты, считайте, что q = n
    K = (int)sqrt(n);

    vector <int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector <query> ask(q);
    vector <int> ans(q);
    for (int i = 0; i < q; i++)
    {
        cin >> ask[i].l >> ask[i].r;
        ask[i].l--; ask[i].r--;
        ask[i].ind = i;
    }
    sort(ask.begin(), ask.end(), cmp);

    // Посчитайте асимптотику только части кода, 
    // расположенной ниже этого комментария

    int sum = 0, L = ask[0].l, R = ask[0].r;
    for (int i = ask[0].l; i <= ask[0].r; i++)
        sum += arr[i];
    ans[ask[0].ind] = sum;

    for (int i = 1; i < q; i++)
    {
        for (int j = L; j < ask[i].l; j++)
            sum -= arr[j];
        for (int j = L - 1; j >= ask[i].l; j--)
            sum += arr[j];
        for (int j = R + 1; j <= ask[i].r; j++)
            sum += arr[j];
        for (int j = R; j > ask[i].r; j--)
            sum -= arr[j];
        ans[ask[i].ind] = sum;
        L = ask[i].l; R = ask[i].r;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << endl;

    return 0;
}

1) каждая итерация O(sqrt(n))
2) суммарно O(nsqrt(n))
3) каждая итерация O(logn)
4) суммарно O(nlogn)

Алгоритм Мо

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

Расчет асимптотики - 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лёгкаяВойти и решать

Сумма кубов#31795

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

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

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

Входные данные
Вводится натуральное число N <= 2*10⁹.

Выходные данные
Требуется вывести не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.

Примеры

№	Входные данные	Выходные данные
1	239	IMPOSSIBLE
2	17	2 2 1

Рекурсия

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

Функция - 2*#31793

Описана рекурсивная функции с тремя параметрами F(a, b, c):

F(a, b, c) = 1, если a ≤ 0 или b ≤ 0 или c ≤ 0;

F(a, b, c) = F(20, 20, 20), если a > 20 или b > 20 или c > 20;

F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c), если a < b и b < c;

F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1), во всех остальных случаях.

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

Входные данные содержат три целых числа a, b, c - параметры функции F (-10⁴ ≤ a,b,c ≤ 10⁴).

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

В ответе выведите значение функции F(a, b, c).

Примеры

№	Входные данные	Выходные данные
1	1 1 1	2
2	2 2 2	4
3	10 4 6	523
4	50 50 50	1048576

Рекурсия

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

Как поделить картошку#31792

Вася и Петя пошли копать картошку. В конце дня они накопали N мешков с картошкой весом W₁, W₂, ... W_N. Как им поделить мешки с картошкой между собой, чтобы разница масс была минимальной.

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

В первой строке записано число N – количество мешков (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы мешков W₁, W₂ , … W_N (1 ≤ W_i ≤ 10⁵).

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

В единственную строку нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух куч с мешками.

Ввод	Вывод
5 5 3 5 7 8	2

Рекурсия

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