## Instructions

**Objective**

Write a program to perform a coffee search problem in python.

## Requirements and Specifications

Vyasa has to complete a python assignment overnight. He has to write n lines of code before morning. He is dead tired and he tries drinking some black coffee to keep him awake. But each time he drinks a cup of coffee he stays awake for a short amount of time but his productivity goes down by a constant factor k.

This is how he plans to write the program. He will write the first v lines of code, then drink his first cup of coffee. Since his productivity has gone down by a factor of k he will write v // k lines of code. He will have another cup of coffee and then write v // k**2 lines of code. He will have another cup of coffee and write v // k**3 lines of code and so on. He will collapse and fall asleep when v // k ** p becomes 0.

Now Vyasa does want to complete his assignment and maximise on his sleep. So he wants to figure out the minimum allowable value of v for a given productivity factor that will allow him to write at least n lines of code before he falls asleep.

**Source Code**

```
import time
# Input: v an integer representing the minimum lines of code and
# k an integer representing the productivity factor
# Output: computes the sum of the series (v + v // k + v // k**2 + ...)
# returns the sum of the series
def sum_series (v, k):
sum = 0
curr = v
while curr > 0:
sum += curr
curr = int(curr / k)
return sum
# Input: n an integer representing the total number of lines of code
# k an integer representing the productivity factor
# Output: returns v the minimum lines of code to write using linear search
def linear_search(n, k):
curr = 1
while sum_series(curr, k) < n:
curr += 1
return curr
# Input: n an integer representing the total number of lines of code
# k an integer representing the productivity factor
# Output: returns v the minimum lines of code to write using binary search
def binary_search(n, k):
top = n
bottom = 1
while top - bottom > 1:
middle = int((top + bottom)/2)
result = sum_series(middle, k)
if result < n:
bottom = middle
else:
top = middle
return top
# Input: no input
# Output: a string denoting all test cases have passed
def test_cases():
# write your own test cases
ns = [511, 365]
ks = [2, 3]
sols = [256, 244]
for i in range(0, len(ns)):
linear = linear_search(ns[i], ks[i])
binary = binary_search(ns[i], ks[i])
assert sols[i] == linear
assert sols[i] == binary
return "all test cases passed"
def main():
test_cases()
in_file = open("work.in", "r")
out_file = open("work.out", "w")
num_cases = int((in_file.readline()).strip())
for i in range(num_cases):
inp = (in_file.readline()).split()
n = int(inp[0])
k = int(inp[1])
start = time.time()
out_file.write("Binary Search: " + str(binary_search(n, k)) + '\n')
finish = time.time()
out_file.write("Time: " + str(finish - start) + '\n')
out_file.write('\n')
start = time.time()
out_file.write("Linear Search: " + str(linear_search(n, k)) + '\n')
finish = time.time()
out_file.write("Time: " + str(finish - start) + '\n')
out_file.write('\n')
out_file.write('\n')
if __name__ == "__main__":
main()
```

## Similar Samples

"Discover our portfolio of programming homework samples at ProgrammingHomeworkHelp.com. From fundamental exercises to advanced projects, our examples in Java, Python, C++, and more showcase our expertise in delivering precise solutions. These samples highlight our commitment to helping students grasp complex concepts effectively. Explore how our solutions can assist you in mastering programming assignments and achieving academic excellence."

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python