Neste post, analisaremos dois problemas do SPOJ:
http://www.spoj.pl/problems/CANDY/
http://www.spoj.pl/problems/CANDY3/
Problema CANDY I
O problema consiste em descobrir o menor número de movimentos necessários para que cada pacote de doces fique com a mesma quantidade de doces. Se a tarefa não for possível, imprima -1.
Observe que a tarefa só é possível se a soma da quantidade de doces de todos os pacotes for divisível pela quantidade de pacotes.
Para descobrir a menor números de movimentos necessários, basta soma as diferenças entre o número de doces de cada pacote menos a média de números de doces por pacote para os pacotes com números de doces superior a média. (Difícil né?)
Pseudocódigo
Entrada n o número de pacotes
vetor p[i] representando número de balas do pacote 1<=i<=n.
soma = 0
Para i = 1 até n faça
soma += p[i]
Se soma%n==0:
media = soma/n
cont = 0
Para i=1 até n faça
se p[i] > media
cont += p[i] - media
Problema CANDYIII
O problema CANDY III é bastante parecido com CANDYI. A tarefa consiste apenas em descobrir se é possível dividir o total de doces de maneira que todas as crianças recebam a mesma quantidade de doces.
Observe que em um problema com restrições razoáveis bastaria somar a quantidade de doces de todas as crianças e testar se o valor encontrado é divisível pela quantidade de criança. Particularmente, este problema não tem nenhuma restrição com relação a quantidade de doces de cada criança e nem em relação a quantidade de crianças.
Para resolver este problema, consideramos que a quantidade de doces de cada criança seria do tipo long long int. Considerando este fato, não temos a garantia que o somatório da quantidade de doces também cabe em long long int. Então, utilizaremos o seguinte resultado de aritmética modular:
(a+b)%n = (a%n + b%n)%n
Observe que este resultado pode ser utilizado para calcular somas difíceis rapidamente.
Por exemplo,
(12124214214214+214214521421412412+42124214215215214+12421412421421)%10
(12124214214214%10+214214521421412412%10+42124214215215214%10+
12421412421421%10)%10
(4+2+4+1)%10
11%10
1
Nenhum comentário:
Postar um comentário