1890. Mário

Olá meus amigos nerds, hoje iremos ajudar nosso amigo Mário a resolver seus problemas. Não me pergunte, que Mário? Pois, não resistirei fazer aquela piadinha infame, ainda mais que o problema de hoje fala de armários.

O problema 1890. Mário nos pede para ajudar nosso amigo Mário a organizar seus armários, de modo a atender de melhor seus clientes. Mais especificamente, dado um conjunto de armários livres e numerados (e com rodinhas) nos é pedido que calcule qual é o menor número de movimentações de armários que deve ser feito para que esses armários livres sejam dispostos de modo a haver n armários livres em sequência.

Solução

Esse é um problema interessante, pois a princípio ele parece bem difícil, mas na realidade é fácil. Observe, inicialmente, que o número de movimentos (trocas) necessários para dispor n armários vazios em sequência é menor que n (pelo menos um armário vazio já estará no lugar). Observe ainda, que a sequência de armários vazios necessariamente começará em um dos L armários (obvio). Se decidirmos começar nossa sequência de armários a partir do armário i, teremos que trocar de posição todos os armários ocupados a partir de i até (i+n). Assim, se contarmos quantos armários ocupados existem a partir de cada i em L e escolhermos o menor desses números teremos nossa resposta. Essa  é precisamente a ideia do algoritmo abaixo, onde contamos o número de armários desocupados (que é complementar ao número de armários ocupados) uma vez que essa é a informação que a entrada do problema nos fornece.

maiorNumArmariosDesocupados = 0

for i in (L-n) //L-n é a última posição em que eu posso iniciar uma sequência de n armários

    Seja x o número de armários desocupados existentes dentro da janela [i, i+n]
    if x > maiorNumArmariosDesocupados
        maiorNumArmariosDesocupados = x

numTrocas = n - maiorNumArmariosDesocupados

Implementação

Observe que em minha implementação eu armazeno apenas as posições dos armários vazios. Isso me permite otimizar um pouco o meu for.

19960. Telemarketing

Olá meus amigos nerds, em primeiro lugar desculpem-me por meu hiato, na última semana estive trabalhando, juntamente com alguns amigos, em um sistema de recomendação de problemas para o spoj e acabei ficando sem tempo de conversar com vocês.

Hoje vamos contar quantas ligações faz um atendente de telemarketing, já que é isso que o problema 19960. Telemarketing nos pede.

O problema nos fornece uma lista de ligações que devem ser feitas na ordem fornecida, juntamente com o tempo necessário para se fazer cada ligação e nos pede que contemos quantas ligações cada um dos n atendentes de telemarketing devem fazer.

Solução

Lendo o problema, é possível perceber que para saber quantas ligações cada atendente fez é necessário simularmos as ligações feitas. O problema então reside em fazer essa simulação de modo eficiente.

Uma forma simples de simularmos as ligações é simularmos o que ocorre em cada instante de tempo, obviamente simular cada instante de tempo além de ser desnecessário é muito custoso. Felizmente, podemos restringir nossa simulação a dois momentos:

• inicio de uma ligação - momento que um vendedor se torna indisponível
• fim de uma ligação - momento em que um vendedor se torna ocioso

O seguinte algoritmo realiza a simulação, onde uma fila de prioridades é usada para manter de modo eficiente qual será o próximo vendedor ocioso (e portanto o responsável por fazer a ligação)

Seja Ti o tempo gasto em ligações pelo vendedor i.
para cada vendedor
   Ti = 0
Adicione cada vendedor a fila de prioridade f, ordenada pelo tempo Ti
para cada ligação
   Seja v o vendedor que está no topo da fila
   Esse vendedor realiza essa ligação (incremente o número de ligações que ele fez)
   Seja Tl o tempo da ligação
   Ti += Tl

Esse tipo de simulação apresentada no algoritmo acima é conhecida como simulação de eventos discretos (você pode saber mais sobre ela aqui).

Implementação

Observe que usei apenas inteiros nessa simulação, já que 30*1.000.000 cabe em 32 bits (int).