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

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

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

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

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

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

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

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

Примеры

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

Рекурсия

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

Монетки#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

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

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

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

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

Плацкартный вагон#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

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

Заполнение конем#31784

Дана шахматная доска nхn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.

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

На вход программе подается натуральное число n (n ≤ 8).

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

Если обход невозможен, то выведите в выходной файл 0, если возможен, то 1, а на следующих строчках выведите матрицу nn, иллюстрирующую порядок обхода. Выравнивать числа по столбцам не обязательно.

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

Ввод	Вывод
3	0
5	1 1 20 17 12 3 16 11 2 7 18 21 24 19 4 13 10 15 6 23 8 25 22 9 14 5

Обход в глубину Рекурсия

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

Постоянная Капрекара#30772

Возьмем четырехзначное число, в котором не все цифры одинаковы, например, 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара. Если разность получается трехзначная, надо в начале добавить ноль.

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

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

Выходные данные: выведите в первой строке постоянную Капрекара, во второй – количество шагов для ее получения.

Задачи на моделирование Строки

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

По мотивам ЕГЭ 2018 - 2#30769

На вход программы подается натуральное число N (\(N<= 100000\)), а затем N строк, в в которых по одному целому числу. Необходимо посчитать количество пар чисел, у которых индексы отличаются не меньше чем на три и произведение кратно 29.
Напишите эффективную по памяти и времени программу.

Примеры

№	Входные данные	Выходные данные
1	6 29 7 8 29 4 5	3

ЕГЭ - вычислительные задачи

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

Максимальное произведение смежных элементов#30768

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

Примеры

№	Входные данные	Выходные данные
1	7 2 3 -2 -3 -1 4 6	72

Пояснения: наибольшее произведение можно получить для последовательности -3 -1 4 6.

ЕГЭ - вычислительные задачи

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