Olá meus amigos nerds, hoje estou com preguiça então falarei de um problema fácil. Mentirinha, estou é fazendo um recomendador de problemas para o spoj, em breve falarei mais sobre ele.
Por incrível que pareça existem dezenas de problemas fáceis no spoj. E o problema 1745. Recuperação é um deles. Nesse problema, é pedido que dado uma lista de inteiros se encontre um inteiro nessa lista tal que ele seja igual a soma dos outros inteiros que o antecedem na lista.
Solução
De forma mais formal queremos um número a[k] tal que:
a[k] = a[1] + a[2] + ... + a[k-1]
a[k] = a[1] + a[2] + ... + a[k-1]
Então basta percorrer a lista e testar essa propriedade. É o que o algoritmo abaixo faz:
soma = 0
for cada elemento a[i] da lista
if a[i] == soma
numeroPedido = a[i]
break;
soma += a[i]
Basta então imprimir numeroPedido
Implementação
Observe que numeroPedido deve ser inicializado com um valor inválido (menor que a menor soma possível, ou maior que a maior soma possível), se você usar numeroPedido = -1 (eu fiz isso da primeira vez :P) você vai levar merecidamente um belo de um wrong answer.
Nenhum comentário:
Postar um comentário