58 lines
2.7 KiB
TeX
58 lines
2.7 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{Análise de Dados}{1}{256}{Arthur Andrade D'Olival}
|
|
|
|
É o seu primeiro dia no \textbf{Departamento de Controle de Qualidade}.
|
|
|
|
Você esperava analisar planilhas, gráficos e talvez alguns modelos estatísticos... mas o laboratório te surpreende.
|
|
|
|
Logo ao entrar, seu gerente te conduz até uma máquina barulhenta, repleta de cabos coloridos e um enorme botão vermelho no topo.
|
|
|
|
--- “Aqui nós fazemos \textbf{análise de dados}.”, ele diz, com um sorriso confiante.
|
|
|
|
Você concorda, achando que entendeu, até perceber que a máquina está literalmente lançando um dado de seis faces a cada segundo.
|
|
|
|
Sim, você vai analisar \textbf{dados de verdade}.
|
|
|
|
Mas há um problema: os dados do laboratório sofrem de \textit{fadiga de repetição}.
|
|
Se uma mesma face aparecer muitas vezes seguidas, o mecanismo emperra e a máquina trava, o que, segundo o manual, “não é recomendável”.
|
|
|
|
Cada face $i$ ($1 \le i \le 6$) possui um limite $d_i$: o número máximo de vezes que ela pode aparecer consecutivamente antes de causar uma falha.
|
|
|
|
Sua tarefa é determinar quantas sequências de lançamentos de comprimento $n$ podem ser geradas sem que a máquina quebre.
|
|
|
|
Como o número de sequências válidas pode ser gigantesco, o gerente exige que o resultado seja dado módulo $10^9 + 7$.
|
|
|
|
\Entrada
|
|
|
|
A entrada contém um inteiro \(n\) que representa o número de lançamentos do dado, onde \(1 \leq n \leq 5000\).
|
|
Em seguida, são dados seis inteiros \(d_1, d_2, d_3, d_4, d_5, d_6\), cada um representando o número máximo de vezes consecutivas que a face correspondente pode aparecer, com \(1 \leq d_i \leq 15\).
|
|
|
|
\Saida
|
|
|
|
A saída consiste em um único inteiro representando o número total de sequências válidas de lançamentos, considerando o resultado módulo \(10^9 + 7\).
|
|
|
|
\section*{Observações}
|
|
|
|
Problema adaptado de \href{https://leetcode.com/problems/dice-roll-simulation/}{Leetcode 1223}.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{2} & \texttt{34}\\
|
|
\texttt{1~1~2~2~2~3} & \\
|
|
\rowcolor{gray!20}\texttt{2} & \texttt{30}\\
|
|
\rowcolor{gray!20}\texttt{1~1~1~1~1~1} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
No primeiro caso de teste, \(n = 2\) e os valores \(d\) são \((1, 1, 2, 2, 2, 3)\).
|
|
As faces \(1\) e \(2\) não podem aparecer repetidas consecutivamente, enquanto as demais possuem limites mais altos, resultando em \(34\) sequências válidas.
|
|
Como há \(2\) lançamentos de dado e \(6\) faces, sem restrições haveria \(6 \times 6 = 36\) combinações possíveis.
|
|
Entretanto, as sequências \((1, 1)\) e \((2, 2)\) são inválidas devido às restrições de \(d_1 = 1\) e \(d_2 = 1\).
|
|
Logo, o total de combinações válidas é \(36 - 2 = 34\). \end{ProblemaAutor}
|
|
\end{document}
|