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()