PKU 2797 - Guards

Autor da análise: gabrielrcpgabrielrcp

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

Resumo

Você precisa contratar seguranças para guardar um local. São necessários, no mínimo, que hajam sempre $n_1$, $n_2$, e $n_3$ seguranças nos turnos de dia durante a semana, de dia no fim de semana, e de noite, respectivamente, $1 \leq n_1, n_2, n_3$ \leq 1000$.
Você pode contratar guardar segundo 4 contratos diferentes, cada tipo de contrato tem associado constantes $k, m_1, m_2, m_3$. Ele diz que você deve contratar um número $n k$ de seguranças, e você terá $(n m_1, n m_2, n m_3)$ seguranças trabalhando em cada um dos turnos.
Dados $(n_1, n_2, n_3)$, pede-se para calcular qual o número mínimo de seguranças que podemos contratar.

Solução

Primeiramente vamos montar a tabela com os valores de $(k, m_1, m_2, m_3)$ para cada contrato:

Contrato $k$ $m_1$ $m_2$ $m_3$
Contrato 1 3 1 1 1
Contrato 2 1 1 0 0
Contrato 3 4 2 2 1
Contrato 4 5 3 0 2

Note que se pudessemos contratar apenas guardas pelos contratos 1 e 2, temos uma estratégia gulosa que resolve o problema em $\mathcal O (1)$. Ela consiste em contratar o número mínimo de guardas pelo contrato 1 de modo que satisfaça os turnos de fim de semana e de noite, e depois contratar o que faltar pelo contrato 2.

Agora é só fazer uma força bruta, testando todas as configurações possíveis de guardas dos tipos 3 e 4.

A quantidade de guardas de grupos de 4 guardas do tipo 3 que precisamos contratar é limitada por $\max (\frac{n_1}{2}, \frac{n_2}{2}, n3) + 1 <= 1001$. Enquanto que a quatidade de grupos de guardas do tipo 4 é limitada por $\max(\frac{n_1}{3}, \frac{n_3}{2}) +1 \leq 501$. Assim o número máximo de combinações testadas é da ordem de $500.000$. Você ainda pode diminuir isso um pouco se desconsiderar combinações dos dois que já "estourem".

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