Индивидуальные задания
1. Фестиваль. В клубе любителей кино состоит N (N≤20) членов. Ежегодно на Международный фестиваль в Канны посылается k (k≤N) членов киноклуба. Одна делегация не должна ездить дважды, т.е. каждый год состав делегации должен хотя бы на одного человека отличаться от состава любой предыдущей делегации. Напечатайте списки всех возможных делегаций.
Формат входных данных
В первой строке заданы количество членов клуба N и количество человек в делегации k. В следующих строках фамилии членов клуба в лексико- графическом порядке.
Формат выходных данных
В первой строке напечатайте количество всевозможных делегаций, а со второй строки – делегации в лексикографическом порядке. Фамилии членов делегации печатать через пробел.
Пример
input.txt |
output.txt |
5 3 Васильев Иванов Петров Тарасов Харитонов |
10 Васильев Иванов Петров Васильев Иванов Тарасов Васильев Иванов Харитонов Васильев Петров Тарасов Васильев Петров Харитонов Васильев Тарасов Харитонов Иванов Петров Тарасов Иванов Петров Харитонов Иванов Тарасов Харитонов Петров Тарасов Харитонов |
2. ABBA. В алфавите племени Мумбо-Юмбо имеется только две буквы – А и В, а в каждом слове равное количество обеих букв. Например, АВВА – слово длины 4 из словаря племени.
Найдите для данного слова длины 2k следующее за ним в лексикографическом порядке слово такой же длины или указывающий, что данное слово – последнее.
Формат входных данных
В первой строке задано слово.
Формат выходных данных
Напечатать следующее слово за заданным словом, а если заданное слово последнее, то напечатать 0.
Пример
input.txt |
output.txt |
ABABAABB |
ABABABAB |
3. Жемчужное ожерелье. Круглое ожерелье состоит из N жемчужин. Каждая жемчужина либо черного (Ч), либо белого (Б) цвета. Получите количество всевозможных вариантов ожерелий, которые можно составить из N жемчужин.
Ожерелья являются замкнутыми. Это означает, например, что два ожерелья, состоящие из четырех жемчужин: Б-Б-Б-Ч и Б-Ч-Б-Б являются одинаковыми.
Формат входных данных
Содержит единственное целое число N (N≤8).
Формат выходных данных
Первая строка количество полученных ожерелий. В следующих строках описание ожерелий.
Пример
input.txt |
output.txt |
3 |
4 |
Примечание. В данном примере можно получить следующие ожерелья:
ЧЧЧ
ЧЧБ ЧББ БББ
4. Последовательность. Получить последовательность a1,a2,..,an цифр 0, 1, 2, в которой нет смежных одинаковых членов (например, последовательность 2,0,1,1,… не годится, так как рядом расположены два одинаковых члена 1).
Формат входных данных
В первой строке задано одно натуральное число n.
Формат выходных данных
Напечатать в лексикографическом порядке все последовательности удовлетворяющие вышеуказанному условию.
Пример
input.txt |
output.txt |
3 |
012 021 102 120 201 210 |
5. Стоимость. Даны N предметов различной стоимости, из них требуется отобрать несколько предметов так, чтобы суммарная стоимость отобранных вещей составляла бы ровно S рублей. Напечатать всевозможные варианты.
Формат входных данных
В первой строке заданы два числа N и S.. Во второй строке заданы N натуральных чисел p1, p2,..,pn- стоимости предметов.
Формат выходных данных
Напечатать все полученные варианты решения задачи. Если это невозможно – напечатать -1.
Пример
input.txt |
output.txt |
5 12 2 4 7 6 5 |
2 4 6 7 5 |
4 16 12 5 13 2 |
-1 |
6. План работы цеха. В цехе имеется N станков и столько же рабочих. Мастер знает эффективность работы каждого рабочего на каждом станке. Ему необходимо распределить рабочих по станкам с учетом следующих ограничений:
1) ни один из рабочих не должен быть назначен на работу на самом неэффективном для него станке (иначе он не получит премию);
2) не менее четверти общего числа рабочих должны работать на станках, на которых эффективность их труда максимальна (надо успеть выполнить задание).
Найдите распределение рабочих по станкам, удовлетворяющее указанным условиям.
Формат входных данных
В первой строке задано число N, в следующих N строках заданы по N чисел, где i-е число определяет эффективность работы рабочего на i-м станке.
Формат выходных данных
Список номеров рабочих, где i-е число соответствует номеру рабочего стоящего на i-м станке.
Пример
input.txt |
output.txt |
5 2 3 5 4 5 5 3 2 1 4 1 2 6 3 2 4 3 5 4 1 1 2 2 1 5 |
2 1 3 4 5 |
7. Купюры. Составить алгоритм подсчета количества способов, которыми можно разменять S рублей медными купюрами достоинством 1, 5, 10, 50, 100, 500 рублей.
Формат входных данных
Содержит единственное целое число S.
Формат выходных данных
Первая строка количество способов размена. Если невозможно напечатать -1.
Пример
input.txt |
output.txt |
20 |
9 |
8. Патронташ. Имеется n патронташей на a1,a2,..,an патронов 12 и 16 калибра. Требуется выбрать k из них и наполнить их патронами 12 калибра, а оставшиеся патронами 16 калибра так, чтобы патронов 12 калибра было в два раза больше чем патронов 16 калибра.
Формат входных данных
В первой строке заданы два натуральных числа n и k. Во второй строке заданы n натуральных чисел a1,a2,..,an.
Формат выходных данных
Напечатать номера выбранных патронташей в порядке следования. Если это невозможно – напечатать -1.
Пример
input.txt |
output.txt |
3 2 4 6 8 |
1 3 |
4 5 8 24 12 |
-1 |
9. Центр тяжести. На плоскости задано множество N (1<N≤20) материальных точек. Найти такое подмножество этого множества, содержащее ровно M (M<N) точек, центр тяжести которого находится наиболее близко к началу координат.
Формат входных данных
В первой строке – числа N и M. В последующих N строках точки, для которых заданы координаты и масса.
Формат выходных данных
Выдать номера точек в порядке следования, попавших в искомое множество.
Пример
input.txt |
output.txt |
4 3 5 3 5 3 1 1 3 3 3 1 2 2 |
2 3 4 |