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

Будем называть пару различных целых чисел похожими, если у них \(k\) последних цифр совпадает.

Дано число \(n\), найдите количество пар различных похожих чисел, состоящих из \(n\) цифр. Ведущие нули запрещены. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми.

Формат входных данных
На первой строке находится целое число \(n\) (\(1 \le n \le 10\)).

На второй строке находится целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно число — количество пар похожих чисел, состоящих из \(n\) цифр.

Комбинаторика

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

Раскраска кеглей#38499

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

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).

Примеры

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

Комбинаторика

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

Сдача#34764

Определите количество различных способов выплаты сдачи в размере n рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль.

Например, 5 рублей можно выплатить четырьмя различными способами: 5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

Входные данные
На вход программе подается натуральное число n <= 100 — размер сдачи, которую необходимо выплатить.

Выходные данные
Выведите искомое количество способов выплаты.

Примеры

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

Вложенные циклы Задачи на моделирование Комбинаторика

✓ 2 063✗ 3 164500лёгкаяВойти и решать

Число сочетаний#33679

По данным числам n и k (0<=k<=n) вычислите \(С_n^k\) . Для решения используйте рекуррентное соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^k\).

Решение оформите в виде функции C(n, k).

Входные данные: Вводятся целые числа n и k.

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

Примеры

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

Задачи на процедуры и функции Комбинаторика Рекурсия

✓ 2 905✗ 4 902400лёгкаяВойти и решать

Точки на прямой#28417

Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.

Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

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

Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 10⁵; 1 ≤ d ≤ 10⁹). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 10⁹ — x-координаты точек, подаренных Пете.

Гарантируется, что координаты точек во входных данных строго возрастают.

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

Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Ввод	Вывод
4 3 1 2 3 4	4
4 2 -3 -2 -1 0	2
5 19 1 10 20 30 50	1

В первом примере нам подходит любая тройка различных точек.

Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.

В третьем примере нам подходит одна тройка: {1, 10, 20}.

"Два указателя"Комбинаторика

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

Номер перестановки#27020

Вам даны две строки - S и одна из её перестановок - P. Требуется найти номер строки P среди всех перестановок строки S, отсортированных по убыванию в лексикографическом порядке.

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

На вход подаются две строки - S и P (1 =< |S| <= 9). В строках содержатся только строчные буквы латинского алфавита.

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

Выведите одно число - номер перестановки P.

Ввод	Вывод
abcd dcba	1
abc abc	6

(с) Ахмад Ибрахим

Комбинаторика Перестановки

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

Тяжелая, вариант-2#24897

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

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, ранее которого не может быть начато выполнение этой задачи.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, ранее которого не может быть начато выполнение этой задачи. Числа отделены друг от друга одним пробелом.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 1	4

Комбинаторика Теория расписаний

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

Тяжелая, вариант-1#24759

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, не позднее которого эта задача должна быть выполнена.

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