Solução Informática - Nível Iniciante - Semana 41

Solução escrita por João Pedro Castro

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops

Primeiramente, vamos ver em que casos não existe uma resposta válida. Para chegar à um MEX de $k$ teremos que ter todos os $k$ números de $0$ até $k - 1$, e para isso ser realizado tanto $n \geq k$ (para termos espaço), quanto $x \geq k - 1$ (para que o limite não impeça que os coloquemos), se alguma dessas condições forem falsas podemos imprimir $-1$.  Agora, depois de adicionar todos os números de $0$ até $k - 1$, de soma total: $\frac{(k - 1)(k - 1 + 1)}{2} = \frac{k(k - 1)}{2}$ (usando a Soma de Gauss), temos $n - k$ espaços restantes no array, e como só queremos a maior soma possível faz sentido colocar $x$ em todos os espaços restantes, já que ele é o maior número permitido; o único caso em que isso não pode ocorrer é quando $k = x$, e como $k$ não pode aparecer no array temos que colocar $k - 1$ (ou seja, tratar $x := x - 1$). Logo, a resposta final é $\frac{k(k - 1)}{2} + x(n-k)$. Tendo uma complexidade por teste de $O(1)$, logo uma complexidade total de $O(t)$, que passa tranquilamente.

Clique aqui para conferir o código