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

Требуется вывести все различные представления натурального числа 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

Рекурсия

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

Расчет асимптотики - 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

Рекурсия

✓ 8✗ 491 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

Рекурсия

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

Как поделить картошку#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

Рекурсия

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

Плацкартный вагон#31790

В плацкартном вагоне 54 места, пронумерованных числами от 1 до 54. Вагон разбит на 9 купе. Первые 36 мест расположены по левую сторону от прохода, места 1–4 находятся в первом купе, места 5–8 – во втором и т. д. В девятом купе находятся места с номерами 33– 36. По правую сторону от прохода находятся боковые места, их номера от 37 до 54, причём они нумеруются в противоположном направлении: места 37 и 38 находятся напротив девятого купе, а места 53 и 54 – напротив первого. Ниже приведена схема всех мест в вагоне.

Группа школьников едет на олимпиаду и будет всю дорогу крутить спиннеры.

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

Программа получает на вход число N – количество свободных мест в вагоне (0 ≤ N ≤ 54). Следующие N строк содержат номера свободных мест – различные числа от 1 до 54 в произвольном порядке, по одному числу в строке.

Программа должна вывести одно целое число – максимальное число подряд идущих свободных купе (купе – 4 места слева от прохода и 2 боковых места) в этом вагоне.

Ввод	Вывод	Примечание
12 5 6 3 4 8 7 51 9 10 54 49 52	1	Свободно одно купе с местами 5, 6, 7, 8, 51, 52.
1 1	0	В вагоне только одно свободное место, поэтому свободных купе нет совсем.

Алгоритмы обработки реализация

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

Не про спиннеры#31789

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

Программа получает на вход два числа N и M – размеры исходного листа. Все числа – целые положительные, не превосходящие 75000.

Программа должна вывести одно число – количество прямоугольников, которые можно вырезать из данного листа бумаги (весь лист целиком также считается одним из возможных прямоугольников).

Ввод	Вывод	Примечание
2 2	9
3 1	6

Вывод формулы

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

Снова спинеры#31788

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

Программа получает на вход одно целое положительное число M, не превосходящее 2×10⁹

, – количество лопастей, которое есть у Дениса.

Программа должна вывести два целых числа – количество спиннеров с 3 лопастями и количество спиннеров с 4 лопастями, которые должен произвести Денис. Если у задачи есть

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

Ввод	Вывод	Примечание
10	2 1	10 = 3 × 2 + 4 × 1
1	0 0	Невозможно произвести спиннеры так, чтобы суммарное число лопастей было равно 1.

Вывод формулы

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

test#31786

sssserse

Цикл for

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

Робот#31782

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

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

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

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

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

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

В первой строке записано число K > 0 - количество операций, которые можно записать в память робота.

Вторая строка состоит из N > K строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой (N <= 200000).

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

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

Ввод	Вывод
2 zabacabab	5
2 abc	0

"Два указателя"

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

Садовник-художник#30783

Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?

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

В единственной строке записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).

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

В единственную строку нужно вывести одно число - количество способов покраски.

Ввод	Вывод
3	12

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

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

Городской парад#30782

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

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

Входные данные
Первая строка ввода содержит одно целое число N (\(1 <= N <= 100\)) – количество платформ.
Вторая строка содержит N различных целых чисел от 1 до N – номера платформ в порядке прибытия.

Выходные данные
Вывести сообщение "YES", если можно обеспечить правильный порядок платформ, или сообщение "NO", если нельзя.

Примеры

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

Очередь

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

Морской бой - 3#30781

Всем известна увлекательная игра «Морской бой». Сейчас играть в Морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат мира по Морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.

Корабль на поле — это связанная фигура, стоящая из одной или нескольких рядом расположенных клеток, имеющих общую сторону. Корабли могут быть абсолютно любых форм и размеров!

Входные данные
Первая строка содержит два целых числа N и M (\(1<= N,M <= 10^3\)), разделённых пробелами. Это размеры игрового поля. Далее идут N строк по M символов - описание игрового поля. Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетку корабля, '-' – свободное водное пространство.

Выходные данные
В ответе выведите через пробел три числа:
- количество целых кораблей;
- количество подбитых кораблей;
- количество уничтоженных кораблей.

Примеры

№	Входные данные	Выходные данные
1	3 8 ---SSS-- XX--S-X- X-S---S-	2 1 1

Очередь

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