Ամբողջ քառակուսիի ստուգում
Ցանկացած սորտավորված հաջորդականության վրա հնարավոր է իրականացնել Երկուական որոնում (Binary Search)։ Անկախ նրանից՝ այն բարձրությունների աճող ցանկ է, ամբողջ թվերի հաջորդականություն, իրական (floating-point) թվերի շարք թե մի այլ բան։ Նույնիսկ կարելի է այն կիրառել ամբողջ թվերի բազմության (), բնական թվերի բազմության () կամ ռացիոնալ թվերի բազմության () վրա։ Ըստ էության, մենք վերցնում ենք հնարավոր լուծումների որոշակի միջակայք և յուրաքանչյուր քայլին «հեռացնում» այն մասը, որն այլևս անհրաժեշտ չէ:
Առաջադրանք
Ձեզ խնդրում են գրել ծրագիր, որը ստանում է դրական ամբողջ թիվ
n և ստուգում է, թե արդյոք այն ամբողջ քառակուսի է, առանց օգտագործելու sqrt ֆունկցիան:Մուտք
Մուտքի միակ տողում տրված է մեկ ամբողջ թիվ
n (2 ≤ n ≤ ):Ելք
Ծրագիրը ելքում պետք է տպի
Yes, եթե n-ը ամբողջ քառակուսի է, իսկ հակառակ դեպքում No:Օրինակներ
Մուտք | Ելք |
9 | Yes |
8 | No |
16 | Yes |
26 | No |
Հուշում
Եթե
n-ը ամբողջ քառակուսի է ⇒ գոյություն ունի այնպիսի x, որ ։ Հետևաբար, կարելի է փորձել գտնել x-ը [1, 2, …, n] միջակայքում։Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB