segunda-feira, 2 de setembro de 2013

Guerreiros Etruscos Nunca Jogam Xadrez

Exercício: http://www.urionlinejudge.com.br/judge/problems/view/1308

Com um pouco de observação, notamos que o exercício utiliza o conceito de progressão aritmética.

De acordo com a wikipédia, "Uma progressão aritmética (abreviadamente, P. A.) é uma sequência numérica em que cada termo, a partir do segundo, é igual à soma do termo anterior com uma constante r.", sendo 1 a constante r utilizada no exercício.

Note que a primeira linha contém um guerreiro, a segunda linha contém dois guerreiros (primeira linha mais um), na terceira linha temos três guerreiros (segunda linha mais um), e assim por diante.
O exercício ainda nos diz qual é o termo para cada linha: na linha i, temos i guerreiros.

Ok, mas o que o exercício pede então?
Ele nos pede para responder quantas linhas são necessárias para que se contenham N guerreiros.

Um simples termo não pode responder tal questão, pois sabemos apenas que a linha i comporta i guerreiros, mas não sabemos quanto à soma das i-1 linhas anteriores.

Poderíamos sair somando em uma variável auxiliar o valor i, começando com i = 1 até que a soma ultrapasse o desejado, e então i seria a resposta.
Porém essa é a solução força bruta, e precisamos de algo mais eficaz, visto que N <= 10¹⁸.

Se pesquisarmos na internet, encontraremos uma fórmula que nos diz a soma dos n primeiros termos de uma determinada progressão aritmética, que seria a seguinte:


Onde ai se referencia ao termo i (no nosso caso, quantidade de guerreiros na linha i).

Por exemplo, se quisermos saber a soma das 5 primeiras linhas de guerreiros, faríamos o seguinte:

n = 5
a1 = 1 (temos 1 guerreiro na linha 1)
a5 = 5 (temos 5 guerreiros na linha 5)

S5 = (5 * (1 + 5) ) / 2
S5 = 30 / 2 = 15

Ok, temos 15 guerreiros nas 5 primeiras linhas, mas o que o exercício pede é justamente o contrário: Visto que eu tenho N guerreiros, quantas linhas foram necessárias?

Pensem, sabemos o número de guerreiros (Sn), sabemos quantos guerreiros há na linha 1 (a1 = 1), só não sabemos quantas linhas são necessárias (n), e quantos guerreiros há na linha n (an).

Se aplicarmos tudo isso na fórmula... Bom, agora é com vocês.

Nenhum comentário:

Postar um comentário