8781. Floresta

Olá meus amigos nerds. Como não podemos fazer muito para tirar a lama la do rio Doce, hoje vamos, pelo menos, ajudar a plantar algumas árvores. Já que é isso que o problema 8781. Floresta nos pede para fazer. Mais especificamente, dado o número de árvores que se deseja plantar, queremos saber de quantas formas elas podem ser plantadas, respeitando-se as restrições do problema.

Solução

Esse é essencialmente um problema de matemática. Queremos plantar carvalhos formando um quadriculado (um retângulo cheio de carvalhos dentro). Sejam a e b os lados desse retângulo. Então:

# de carvalhos dentro do retângulo = a*b

Como no centro de cada quadradinho de carvalhos temos que plantar um encalipto. O número de encaliptos plantados será:

# de encaliptos plantados = (a-1)*(b-1)

Assim o número total de árvores plantadas será:

n = ab + (a-1)*(b-1)
= 2ab -a -b + 1

resolvendo em relação a b temos:

2ab - b = n + a - 1
b = (n + a - 1)/(2a - 1)

Ou seja, todos os pares de números inteiros da forma [a, (n+a-1)/(2a-1)] satisfazem as condições do problema. Então é só contar quantos pares desses números existem.

Como retângulos axb e bxa não são considerados como elementos distintos, podemos supor que a <= b, assim:

a <= (n + a - 1)/(2a - 1)

donde tiramos a condição de parada do for: 2*a^2 - 2*a + 1 <= n

Implementação