PKU 3088 - Push Botton Lock

Autor da análise: sacomotosacomoto

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3088

Resumo

Dado um conjunto $B = \{ 1, 2, .., n \}$, chame de combinações qualquer subconjunto (não vazio) de $B$, e chame de sequência qualquer série (a ordem é relevante) de combinações. Para um dado $n$ o problema pede o número de sequências distintas com combinações disjuntas. Por exemplo, para $B = \{ 1,2,3 \}$ temos que $(1 2)(3)$ e $(1 3)$ são válidas, mas $(1 2) (2 3)$ e $(1 1)(2 3)$ não são.

Solução

Vamos montar uma recorrência para o número de sequências, onde $n$ é o numero de elementos do conjunto base e $k$ é o número de termos (subconjuntos) da sequência, desta forma temos que:

(1)
\begin{align} f(n, k) = f(n-1, k) + k \sum_{i = 1}^{n-1} \binom{n-1}{i} f(i, k - 1) \end{align}

com os casos de contorno, $f(n, k) = 0$ para $n < k$ e $f(n, k) = 2^n - 1$ para $k = 1$.

Então, o número de sequências pedidas é $\sum_{i=1}^{n} f(i, k)$.

Para demonstrar a recorrência basta considerar a seguinte partição para as sequências possíveis com conjunto base $B = \{ 1, 2, .., n \}$ e exatamente $k$ termos: aquelas que possuem o elemento $n$ em algum de seus termos e as que não possuem.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License