28a Olimpíada Brasileira de Informática
Pilhas de moedas
Flávia possui várias moedas em sua coleção, que estão organizadas em N pilhas, cada pilha com um certo número de moedas. Vamos chamar o número de moedas de uma pilha de altura da pilha. A garota pretende adicionar algumas moedas à sua coleção, de forma que cada moeda nova deve ser adicionada em uma das pilhas existentes. As moedas originais, porém, devem permanecer nas suas pilhas. Flávia está se perguntando agora: qual o número mínimo de moedas que ela deve adicionar à coleção para que, considerando os valores de todas as N novas alturas de pilhas, a quantidade de números distintos seja no máximo K? Por exemplo, se a lista de alturas inicialmente é (3,5,8,4,5,8), temos que existem 4 valores distintos de alturas: 3, 4, 5 e 8. Se K = 2, poderíamos, com 3 moedas novas, adicionar duas na pilha de índice 1, e uma na pilha de índice 4. Assim, a lista de alturas ficará (5,5,8,5,5,8), que possui apenas dois valores distintos de alturas: 5 e 8. Note que, se inicialmente a lista de alturas já tem no máximo K valores distintos, Flávia já estaria feliz, e não iria precisar de nenhuma moeda nova.Entrada
A primeira linha da entrada contém um dois inteiros separados por espaços N, indicando o número de pilhas e K, indicado o número máximo de valores distintos. A segunda linha contém N inteiros Pi, indicando as alturas das pilhas.Saída
Imprima a menor quantidade adicional de moedas.Restrições
- 1 ≤ N ≤ 500
- 1 ≤ K ≤ N
- 1 ≤ vi ≤ 500
Informações sobre a pontuação
- Para um conjunto de casos de testes valendo 13 pontos, K = 1.
- Para outro conjunto de casos de testes valendo 21 pontos, K = 2.
- Para outro conjunto de casos de testes valendo 28 pontos, K , N, vi ≤ 50.
- Para outro conjunto de casos de testes valendo 38 pontos, nenhuma restrição adicional.
Exemplos
Entrada
6 2 5 3 8 4 5 8 |
Saída
3 |
Entrada
6 3 5 3 8 4 5 8 |
Saída
1 |