Flashcard FC303132
Como calcular o menor número possível de valores distintos em uma sequência de N inteiros quando um valor aparece exatamente k vezes e todos os outros aparecem menos de k vezes?
Sequências de Números, Figuras, Letras e Palavras
FGV · 2024
Como calcular o menor número possível de valores distintos em uma sequência de N inteiros quando um valor aparece exatamente k vezes e todos os outros aparecem menos de k vezes?
Mostrar resposta e comentário
Resposta
Subtraia k de N e divida o restante por k−1; o mínimo de distintos é \(1+\left\lfloor\frac{N-k}{k-1}\right\rfloor\) mais 1 se houver resto.Explicação:
Retire as k ocorrências do valor que aparece k vezes.
Os demais valores podem aparecer no máximo \(k-1\) vezes cada para não igualarem k.
Logo, repartimos \(N-k\) em blocos de tamanho \(k-1\): o número de blocos inteiros é \(\left\lfloor\frac{N-k}{k-1}\right\rfloor\).
Se houver resto, precisamos de mais um valor distinto para acomodá-lo.
Exemplo:
Se \(N=100\) e \(k=5\):
\(100-5=95\)
\(95\div(5-1)=95\div4=23\) resto \(3\)
Total de distintos = \(1+23+1=25\)
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/300222
Conteúdo do catálogo FC Concursos · Atualizado em