Рассмотрим множество натуральных
чисел, меньших или равных n. Отметим, что все элементы множества
различны. Порядок элементов в множестве не существенен, то есть {3, 5, 9} и {5,
9, 3} являются одинаковыми множествами.
Количество элементов во множестве
и их сумму будем обозначать через k и s соответственно. Количество
множеств, удовлетворяющих этому условию, конечно. Если n = 9, k = 3 и s = 23, то
множество {6, 8, 9} будет единственным. Однако в общем случае множеств может
быть и несколько. Если n = 9, k = 3 и s = 22, то оба из
множеств {5, 8, 9} и {6, 7, 9} возможны.
Напишите программу, которая
найдет количество множеств с заданными условиями.
Вход. Состоит из нескольких тестов,
число которых не превышает 100.
Каждый тест состоит из одной
строки, содержащей три целых числа n, k и s (1 ≤ n
≤ 20, 1 ≤ k ≤ 10 и 1 ≤ s ≤ 155).
Последняя строка содержит три
нуля.
Выход. Для каждого теста вывести одно
число - количество множеств с заданными условиями. Никаких лишних символов
выводить не следует.
Считайте, что количество искомых
множеств не превышает 231 – 1.
|
Пример
входа |
Пример
выхода |
|
9 3 23 9 3 22 10 3 28 16 10 107 20 8 102 20 10 105 20 10 155 3 4 3 4 2 11 0 0 0 |
1 2 0 20 1542 5448 1 0 0 |
комбинаторика
- перебор
Сгенерируем
массив m, в котором n – k нулей и
k единиц. Причем единицы находятся в конце: m = (0, 0, …, 0,
1, 1, …, 1). Длина массива m равна n. Рассмотрим массив m как маску для
множества (1,
2, 3,…, n).
Рассмотрим все
перестановки множества m. Таким образом мы переберем все кортежи длины k из чисел (1, 2, 3,…, n). Причем кортежи
будут содержать разные числа. Подсчитаем количество кортежей, которые будут иметь
сумму s.
Читаем входные
данные.
while (scanf("%d %d %d", &n, &k,
&s), n + k + s)
{
Сгенерируем массив m = (0, 0, …, 0, 1, 1, …, 1).
memset(m, 0, sizeof(m));
for (i = n - 1; i >=
n - k; i--) m[i] = 1;
Перебираем все кортежи длины k из чисел (1, 2, 3,…, n). Количество
кортежей с суммой s подсчитываем в переменной res.
res = 0;
do
{
Находим сумму sum подмножества чисел (1, 2, 3,…, n), которому соответствует маска m.
sum = 0;
for (i = 0; i < n; i++)
if (m[i] == 1) sum += i +
1;
Если сумма равна s, то увеличиваем res на 1.
if (sum == s) res++;
} while (next_permutation(m, m +
n));
Для текущего теста выводим ответ.
printf("%d\n", res);
}