Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Find sqrt(n) with precision

Given a positive integer n, it’s possible to find the with precision using binary search. You are asked to find the square root of n with precision by performing a binary search on the result k times.

#### Input

The input contains two integers n (2 ≤ n ≤ ) and k (1 ≤ k ≤ 100).

#### Output

The program should print the with a precision of performing k binary search splits.

#### Examples

 Input Output 10 2 3.75

#### Explanation

Iteration 1: (0 + 10) / 2 = 5 ⇒ lower ⇒ (0, 5)
Iteration 2: (0 + 5) / 2 = 2.5 ⇒ higher ⇒ (2.5, 5)
Stop ⇒ (2.5 + 5) / 2 = 3.75

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB