O termo cache pode ser entendido como uma área de armazenamento onde dados frequentemente usados são guardados para um acesso futuro mais rápido, poupando tempo e recursos. Um exemplo de uso de caches está nos navegadores de internet. Não é por acaso que sites que você frequenta constantemente costumam abrir mais rapidamente do que os que visita pela primeira vez. Isso se deve ao fato de que o cache do navegador guarda os objetos dessas páginas (imagens, fontes, vídeos, etc.), poupando o tempo de download em exibições futuras. Na época da internet discada era muito fácil perceber quando uma página não estava em cache.

No entanto, caches têm uma tendência desagradável de encher. Quando isso acontece, alguns objetos devem ser retirados para criar espaço para novos objetos. Chamamos de política de substituição o método usado para a escolha do objeto que será removido do cache. Você foi contratado por uma empresa que está desenvolvendo novas políticas de substituição e irá ajudar a avaliar esses novos algoritmos.

Na aplicação que você irá testar, quando o sistema é iniciado, o cache começa vazio. Assim, para que um objeto seja acessado, ele precisa primeiro ser inserido no cache. Além disso, todos os objetos têm o mesmo tamanho e um objeto que está no cache nunca se torna inválido. Desse modo, quando um objeto que não estiver no cache for solicitado, pode ser necessário (dependendo da ocupação do cache) remover um dos objetos guardados anteriormente e substituí-lo pelo demandado.

Para se avaliar uma política de substituição, podemos contar quantas vezes precisamos inserir algum objeto no cache em alguma sequência de acessos determinada. Dependendo da política utilizada para escolher o objeto a ser removido, o número de inserções pode ser maior ou menor. Mas se conhecêssemos toda a sequência de acessos, então seria possível calcular o número mínimo de inserções que é necessário por qualquer política de substituição.

Sua tarefa é escrever um programa cache que receba uma sequência de acessos e calcule o número mínimo de inserções necessárias.

Entrada

A primeira linha contém três inteiros $c, n, m$, onde $c$ é o tamanho do cache, $n$ é o número objetos distintos que existem no sistema e $m$ é o comprimento da sequência de acessos. Cada uma das próximas $m$ linhas contém um único inteiro entre $0$ e $n − 1$ que identifica um objeto da sequência de acessos.

2 3 5
0
1
2
2
1

Saída

A saída contém o número mínimo de inserções necessárias para atender a sequência de acessos da entrada.

3

Neste exemplo, o cache tem tamanho 2, o número de objetos é 3 e queremos realizar 5 acessos. O número de inserções necessárias depende de que objetos escolhemos para sair do cache quando ele está cheio e queremos acessar um outro objeto. Para o exemplo acima, a sequência de acessos abaixo utiliza apenas 3 inserções.

Observe que, se ao invés de ter removido o 0, tivéssemos removido o 1, o número de inserções seria maior.

Dicas

Intuitivamente, queremos que estejam no cache os objetos que voltarão a ser acessados mais em breve. Assim, é melhor remover do cache o objeto que está presente e que não será mais acessado, ou que será acessado mais tarde. Para escolher o item a ser removido, utilize uma fila de prioridades cuja chave representa a ordem do próximo acesso.

Esta tarefa tem alguns testes grandes. Antes de tentar passar em todos os casos de teste, concentre-se em resolver as instâncias menores. Depois disso, procure identificar as operações mais custosas de seu algoritmo e pense em como implementá-las eficientemente. Um algoritmo de tempo quadrático não será suficiente para passar nos casos maiores.

Critérios

Seu programa deve usar uma fila de prioridade para resolver esta tarefa eficientemente.

← Anterior Voltar Próximo →