1537. Полоса

Дан прямоугольник размера 1×n, разбитый на клетки 1×1. Каждая клетка может быть закрашена либо в белый, либо в чёрный цвет.

Кодом данного прямоугольника называется последовательность чисел, каждое из которых равно количеству подряд идущих чёрных клеток при просмотре прямоугольника слева направо.

Например, код для прямоугольника, изображённого выше, равен 2 3 2 8 1. Количество белых клеток в коде не учитывается; при этом каждая группа чёрных клеток должна быть отделена от следующей хотя бы одной белой клеткой. Следовательно, одному и тому же коду могут соответствовать несколько различных прямоугольников. В частности, следующий прямоугольник также имеет указанный код:

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

Вход. Первая строка содержит количество тестов t (1 < t < 20). Каждая из следующих t строк  является отдельным тестом и содержит:

· длину прямоугольника n (1 ≤ n ≤ 200);

· количество чисел в коде k (0 ≤ k ≤ (n + 1) / 2) ;

· k чисел, описывающих код.

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

Пример входа	Пример выхода
3 4 0 5 2 1 2 4 2 2 2	1 3 0

РЕШЕНИЕ

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

Анализ алгоритма

Пусть имеется w белых квадратов и k групп черных квадратов.

Поскольку группы черных квадратов не касаются друг друга, то между ними обязательно должна быть хотя бы одна белая клетка. То есть должно существовать как минимум k – 1 белых квадратов. Если w < k – 1, то разместить группы невозможно, и ответ равен 0.

Разделим белые клетки на два типа:

· Обязательные k – 1 белых клеток, которые стоят между чёрными группами;

· Свободные – остальные w – (k – 1) белых клеток.

Эти свободные белые клетки можно распределять произвольно в любом месте по отношению к группам черных квадратов.

Свободные белые клетки можно размещать в следующих местах:

· перед первой чёрной группой;

· между группами;

· после последней чёрной группы.

Количество всех таких мест равно k + 1.

Определим комбинаторную модель:

· у нас имеется w – (k – 1) свободных одинаковых белых клеток;

· свободные белые клетки следует распределить по k + 1 различным местам;

· ограничения на количество белых клеток в каждом месте отсутствуют;

Это классическая задача сочетаний с повторениями (starts & bars).

Известно, что распределить n одинаковых объектов по k различным местам без ограничений на количество объектов в каждом месте можно способами.

Тогда в нашем случае распределить w – (k – 1) одинаковых белых клеток по k + 1 различным местам можно = способами.

Пример

Рассмотрим второй тест. Существует 3 полосы длины 5 с кодом 1 2:

Общее количество чёрных клеток: s = 1 + 2 = 3.

Количество белых клеток: w = n – s = 5 – 3 = 2.

Между группами обязательно должна быть хотя бы одна белая клетка.

· Количество обязательных белых клеток равно k – 1 = 1;

· Количество свободных белых клеток равно w – (k – 1) = 2 – 1 = 1;

Для 1 свободной белой клетки имеется k + 1 = 3 места.

Распределить 1 свободную белую клетку по 3 местам можно = 3 способами.

Реализация алгоритма

Читаем входные данные.

t = int(input())

for _ in range(t):

data = list(map(int, input().split()))

n = data[0]

k = data[1]

При k = 0 ответ 1.

if k == 0:

print(1)

continue

Извлекаем код для прямоугольника code.

code = data[2:]

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

s = sum(code)

w = n – s

Если w < k – 1, то разместить группы невозможно, и ответ равен 0.

if w < k - 1:

print(0)

continue

Вычисляем и выводим ответ.

print(math.comb(w + 1, k))

Java реализация

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger Cnk(BigInteger n, BigInteger k)

{

BigInteger ONE = BigInteger.ONE, CnkRes = ONE;

if (k.compareTo(n.subtract(k)) > 0) k = n.subtract(k);

for(BigInteger i = ONE; i.compareTo(k) <= 0; i = i.add(ONE))

CnkRes = CnkRes.multiply(n.subtract(i).add(ONE)).divide(i);

return CnkRes;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

int group[] = new int[200];

while(tests-- > 0)

{

int n = con.nextInt(), g = con.nextInt();

int w = 0;

for(int j = 0; j < g; j++)

{

group[j] = con.nextInt();

w += group[j];

}

w = n - w;

if (w < g - 1) System.out.println("0");

else System.out.println(Cnk(BigInteger.valueOf(w+1),

BigInteger.valueOf(w-g+1)));

}

}

}