Գտնել sqrt(n)-ը ճշտությամբ
Տրված է
n դրական ամբողջ թիվը։ Հարկավոր է հաշվել -ը որոշակի ճշտությամբ, օգտագործելով երկուական որոնում (Binary Search): Ձեզ խնդրում են գտնել n-ի քառակուսի արմատը, k անգամյա կիրառելով երկուական որոնում:Մուտք
Մուտքի միակ տողում տրված են երկու ամբողջ թվեր
n (2 ≤ n ≤ ) և k (1 ≤ k ≤ 100):Ելք
Ծրագիրը պետք է տպի -ի արժեքը, որը կստացվի
k անգամյա երկուական որոնման բաժանումները կիրառելուց հետո:Օրինակներ
Input | Output |
10 2 | 3.75 |
Բացատրություն
Քայլ 1: (0 + 10) / 2 = 5 ⇒ lower ⇒ (0, 5)
Քայլ 2: (0 + 5) / 2 = 2.5 ⇒ higher ⇒ (2.5, 5)
Վերջ ⇒ (2.5 + 5) / 2 = 3.75
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB