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

Solução escrita por Arthur Lobo

Conhecimento prévio necessário:

• Busca em grafos

Primeiro, enumeramos todos os possíveis valores de $x$, que podem variar de $0$ até $\lceil\sqrt{D} \rceil$. Isso acontece porque se $x > \lceil\sqrt{D} \rceil$, então o melhor $y$ é $0$. Isso faz com que qualquer solução $(x,0)$ ser pior do que $(\lceil\sqrt{D} \rceil,0)$.

Com o $x$ fixado, basta encontrar qual o melhor valor de $y$, ou seja, minimizar $|D - x^2 - y^2|$. Fazendo $C = D - x^2$, reduzimos o problema para, dado um inteiro $C$ minimizar $|C - y^2|$.

Se $C = D- x^2$ for menor ou igual a $0$, então o $y$ ótimo é $0$.

Se $C$ for maior que $0$, então o valor ótimo de $y$ será $\lfloor\sqrt{C} \rfloor$ ou $\lceil\sqrt{C} \rceil$.

Com essa solução, podemos varias $x$ de $0$ até $\lceil\sqrt{D} \rceil$ e encontrar os dois valores possíveis de $y$ em $O(1)$ utilizando a função sqrt do C++. Sendo assim, essa solução funciona em $O(\sqrt{D})$.

Clique aqui para conferir o código