Verifica di un quadrato perfetto
È possibile effettuare una ricerca binaria su qualsiasi lista ordinata: che si tratti di un elenco di altezze crescenti, numeri interi, numeri in virgola mobile e così via. Può persino trattarsi dell’insieme dei numeri interi , naturali o razionali . In ogni caso, si seleziona un intervallo di possibili soluzioni e, a ogni iterazione, si elimina la parte non necessaria.
Challenge
Dato un intero positivo
n, il tuo compito è verificare se n è un quadrato perfetto senza utilizzare la funzione sqrt.Input
L’input contiene un singolo intero
n (2 ≤ n ≤ ).Output
Il programma deve stampare
Yes se n è un quadrato perfetto e No altrimenti.Esempi
Ingresso | Uscita |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Hint
Se
n è un quadrato perfetto ⇒ esiste un altro numero x tale che . Di conseguenza, puoi provare a cercare x nell’intervallo [1, 2, …, n].Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB