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

Задача о назначениях lite#39368

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

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где A_i,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех A_i,j выполнено 1 <= A_i,j <= 10⁵.

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

Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.

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

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

Все перестановки#39367

Вам дано натуральное число n. Выведите все перестановки размера n в лексикографическом порядке.

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

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

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

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

Карточки#38635

На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос.

Входные данные
Вводится слово, составленное Петей – строка из маленьких латинских букв не длиннее 15 символов.

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

Примеры

№	Входные данные	Выходные данные
1	solo	12

Перестановки

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

Расчет асимптотики - 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лёгкаяВойти и решать

Двоичные строки заданной длины#27089

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

Входные данные
Задано единственное число N (натуральное, \(1 <= N <= 10\))

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

Примеры

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

Перестановки

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

Все двоичные строки длины n, содержащие ровно k единиц#27088

По данным числам N и K выведите все строки из нулей и единиц длины N, содержащие ровно K единиц, в лексикографическом порядке.

Входные данные
Заданы 2 числа: N и K (\(0 <= K <= N\), \(0 <= N <= 100\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 2	0011 0101 0110 1001 1010 1100

Перестановки

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

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

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

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

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

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

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

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

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

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

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

Обратная перестановка#27019

По данной перестановке π требуется найти π^-1.

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

В первой строке входных данных содержится число 0 < N <= 20000 – количество элементов в перестановке π. Во второй строке записана сама перестановка π.

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

Выведите π^-1

Ввод	Вывод
3 2 3 1	3 1 2

Разбор:
Вводим N и заводим массив от 1-го до N. Теперь начинаем считывать данную перестановку - хранить ее не обязательно, поэтому разумно будет вводить каждый элемент в одну и ту же переменную. Вводя i-й элемент кладем его порядковый номер (i) в ячейку массива с номером, равному этому числу, т.е. для каждого элемента данной перестановки сохраняем его место в этой перестановке. Теперь выводим полученный массив.

Алгоритмы обработки Перестановки

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

Три числа#21843

Вам дано три числа a, b и c. Вы должны в таком порядке приписать эти числа друг к другу, чтобы в результате получилось минимальное число. Например, если a = 12, b = 5, c = 3, приписыванием можно получить числа 1253, 1235, 3125, 3512, 5123, 5312. Минимальным, среди этих чисел является 1235.

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

В первой строке через пробел записаны три целых числа a, b и c (1 ≤ a, b, c ≤ 100).

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

Выведите минимальное число, которое можно получить, приписав a, b и c друг к другу в каком-нибудь порядке.

Примеры тестов

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

12 3 5

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

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

2 21 3

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

Перестановки реализация

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