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

Целочисленное деление и остаток#31885

Напишите программу, которая по заданным двум числам a и b, выводит на экран результат целочисленного деления и остаток, в заданном формате (смотри примеры).

Входные данные
На вход программы подается два числа: a и b.

Выходные данные
Необходимо вывести две строки:
- в первой строке - арифметическое выражение и результат целочисленного деления a на b;
- во второй строке - арифметическое выражение вычисления остатка от деления a на b.
Формат вывода смотри в примере.

Примеры

№	Входные данные	Выходные данные
1	15 6	15/6=2 15%6=3

Целые числа

✓ 3 131✗ 16 780200лёгкаяВойти и решать

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

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

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

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

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

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

Сумма элементов последовательности#31862

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

Входные данные
На вход программе подаются числа, по одному числу в строке.

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

Примеры

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

Цикл while

✓ 6 691✗ 6 578200лёгкаяВойти и решать

Ханойские башни#31845

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

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

Вводится натуральное число n ( 0 < n < 11).

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

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

Примеры

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

Рекурсия

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

Троечные последовательности#31844

Вводится число N. Сгенерируйте в анти-лексикографическом порядке все последовательности длины N (1≤N≤9), состоящие из чисел 3, 4, 5, в которых количество троек не превосходит двух.

В "анти-лексикографическом" обозначает "в порядке, обратном к лексигографическому" (см. пример).

В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.

В анти-лексикографическом, соответственно, наоборот.

Примеры

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

Рекурсия

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

Двоичные последовательности#31843

Вводится число N (1<=N<=9). Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не больше двух.

В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.

Рекурсия

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

Звездочки#31842

Дана строка, содержащая только английские буквы (большие и маленькие). Добавить символ ‘*’ (звездочка) между буквами (перед первой буквой и после последней символ ‘*’ добавлять не нужно).

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

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

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

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

Примеры

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

Рекурсия

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

Количество цифр#31841

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

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

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

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

Выведите количество цифр, которые присутствуют в строке.

Примеры

№	Входные данные	Выходные данные
1	74kz31n8pn26f2iv10c7u8x356gl73jlka67i929z08i5mnn35h0n	28

Рекурсия

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

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

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

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

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

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

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

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

Примеры

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

Рекурсия

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

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

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

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

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

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

Рекурсия

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

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

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

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

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

Примеры

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

Рекурсия

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

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

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

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

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

Примеры

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

Рекурсия

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

31823#31823

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

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

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

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

31822#31822

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

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

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

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

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	(()) [[]] [()] ()[] []() ()() ([]) [][]

Рекурсия

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

Разложение на слагаемые#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

Рекурсия

✓ 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лёгкаяВойти и решать

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

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

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

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

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

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

Примеры

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

Рекурсия

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