Verificar se é um quadrado perfeito
É possível realizar uma pesquisa binária (binary search) em qualquer lista ordenada: seja uma lista de alturas crescentes, números inteiros, números de ponto flutuante, etc. Pode até ser o conjunto de inteiros , o conjunto de números naturais ou o conjunto de números racionais . Ainda assim, escolheríamos um intervalo de possíveis soluções e descartaríamos a parte desnecessária a cada iteração.
Desafio
Dado um inteiro positivo
n, é preciso verificar se n é um quadrado perfeito sem utilizar a função sqrt.Entrada
A entrada consiste num único inteiro
n (2 ≤ n ≤ ).Saída
O programa deve imprimir
Yes caso n seja um quadrado perfeito e No caso contrário.Exemplos
Entrada | Saída |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Sugestão
Se
n é um quadrado perfeito ⇒ existe um outro número x tal que . Portanto, é possível tentar encontrar x num intervalo [1, 2, …, n].Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB