Информатика

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

#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;
}

#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];
}

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

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

 

 

Описана рекурсивная функции с тремя параметрами 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), во всех остальных случаях.

 

 

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

 

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

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

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

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

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

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

 

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

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

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

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

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

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

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

 

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

 

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

Ввод	Вывод
3	12

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

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

Входные данные
Первая строка ввода содержит одно целое число 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

 

Пусть x – целое положительное число, а k – натуральное число от 1 до 10. Пусть s(x, k) равно сумме цифр числа x, представленного в системе счисления по основанию k.

 

Задано n чисел a1, a2, ..., an. Необходимо вычислить последовательность bi по формуле \(b_i = s(a_i, k_1) \cdot s(a_i, k_2)\). После этого отсортировать последовательность bi по неубыванию.

 

Первая строка содержит три целых числа: n, k1, k2 (\(1 <= n <= 1000\), \(2 <= k_1, k_2 <= 10\)). Вторая строка содержит n целых чисел: ai (\(1 <= a_i <= 10^9\)).

 

В ответе выведите n чисел – bi в требуемом порядке.
 

 

Примеры

№	Входные данные	Выходные данные
1	9 10 10 1 2 3 4 5 6 7 9 8	1 4 9 16 25 36 49 64 81
2	10 2 2 1 2 4 8 16 32 64 128 256 512	1 1 1 1 1 1 1 1 1 1

Входные данные 
Входная строка содержит два положительных целых числа n и m (\(1 <= n, m <= 10^9\)).

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

Задано натуральное число n. Необходимо перевести его в k-ичную систему счисления и найти разность между произведением и суммой его цифр в этой системе счисления.

 

Например, пусть \(n = 239\), \(k = 8\). Тогда представление числа n в восьмеричной системе счисления — \(357\), а ответ на задачу равен \(3 \cdot 5 \cdot 7 ? (3 + 5 + 7) = 90\).
 

 

Строка содержит два натуральных числа: n и k (\(1 <= n <= 10^9\), \(2 <= k <= 10\)). Оба этих числа заданы в десятичной системе счисления.

 

Выведите ответ на задачу (в десятичной системе счисления).
 

 

Примеры

№	Входные данные	Выходные данные
1	239 8	90
2	1000000000 7	-34

Несмотря на кризис, компания Soft-Soft работает успешно. Директор компании принял решение выплатить сотрудникам премии. На следующий день был обнародован список счастливчиков. Чтобы не разглашать размер выплат, в списке напротив фамилий красовались странные цифры и даже буквы. Сотрудники быстро догадались, что размер премий записан в различных системах счисления. Но где и какая система счисления используется, сообразила только секретарша Танечка, которая вспомнила, что директор просил ее принести информацию о возрасте сотрудников. Она поняла, что директор отбрасывал десятки из числа, указывающего возраст, а к оставшимся единицам добавлял число 2. Полученное значение служило основанием для представления начисленной премии.

 

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

 

В первой строке  записаны два целых числа N и K – возраст и размер премии, разделенные пробелом. Возраст не превышает 100, размер премии указан в некоторой системе счисления (запись числа не содержит незначащих нулей, использует арабские цифры и заглавные английские буквы).

 

Выведите одно число – размер премии в десятичной системе счисления.
 

 

Примеры

№	Входные данные	Выходные данные
1	28 2800	2800
2	30 101	5

Из заданного набора чисел выберите одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).

 

Входные данные 
Первая строка  содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.

 

Выходные данные 
В ответе выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.

 

Примеры

№	Входные данные	Выходные данные
1	10 3 5 7 9 11 13 15 17 19 21	15
2	11 2 4 6 8 10 13 39 105 200 201 143	105