TAPETE14 - Tapetes

Olá meus amigos nerds! Um dos objetivos desse blog é ser útil a quem está aprendendo, assim, hoje vamos resolver um problema a pedido por vocês.

Hoje vamos embalar tapetes, já que é isso que o problema TAPETE14 - Tapetes pede para fazer. Mais especificamente, queremos maximizar o valor da carga de tapetes dado que temos que transportar exatamente n tapetes que somam exatos l metros.

Solução

Olhando por cima esse problema parece o clássico problema da mochila, cada tenho uma mochila de tamanho n e quero enche-la com o máximo valor possível. Mas não é, uma vez que eu tenho a restrição de ter exatamente n objetos dentro dela. A solução para esse problema no entanto é mais simples.

Dado que o valor do tapete aumenta com o quadrado de seu comprimento é sempre melhor eu aumentar o tamanho de apenas um tapete, ou seja, embalar n-1 tapetes de tamanho 1 e um tapete de tamanho l - (n - 1) (correspondente ao comprimento restante da embalagem). Vou provar essa afirmação para n=2, mas ela é válida para qualquer n.

Sejam a e b os comprimentos dos dois tapetes que eu quero embalar. Logo:

a + b = l

Sendo que eu quero maximizar:

argmax(a^2 + b^2)
a < l (o tamanho de todos os tapetes tem que ser maior que 0)
b < l

mas a = l - b, logo:

argmax((l - b)^2 + b^2) = argmax(l^2 -2*l*b + 2*b^2)

l é uma constante. Como o coeficiente de b^2 é positivo o polinômio tem apenas um ponto de mínimo, ou seja, para maximiza-lo basta aumentar b. O maior valor possível de b é l - 1.

Assim para n qualquer teríamos a fórmula para o valor máximo = (l-n+1)^2 + (n - 1) [comprimento do maior tapete ao quadrado mais soma do valor dos n-1 tapetes de tamanho 1].

Implementação

Há um erro na indicação do tamanho da entrada. n, l <= 10^6 e não 106. Assim n^2 não cabe em 32 bits, logo temos que usar um inteiro de 64 bits (long long).