Question
Answer the question in Python, thank you. Vyasa has to complete a programming assignment overnight. He has to write n lines of code before morning.
Answer the question in Python, thank you.
Vyasa has to complete a programming 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 maximize 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.
Input
2 300 2 59 9 The first line is T the number of test cases. This will be followed by T lines of input. Each line of input will have two numbers nand k. nis the number of lines of code to write and kis the productivity factor, where 1 n106and 2 k10
Output
Do not worry if your times do not match ours exactly. They are given just for comparison purposes. For this assignment, main has been written completely for you, and nothing needs to be changed in it. You will be solving this problem in 2 ways. First, you will write a function that uses a linear search to solve the problem. Then you will write a function that uses a modified binary search algorithm to solve it again. Both functions will return the same answer, but the binary search method will usually be faster. It is recommended that you write a helper function, which given a value v representing the number of lines Vyasa writes before his first cup of coffee and a value k, the productivity factor, will calculate the number of lines Vyasa will write before falling asleep. This can be called in both the linear and binary functions to make the computations easier.
Starter Code
import sys
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):
# 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):
# 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):
def main():
# read number of cases
line = sys.stdin.readline()
line = line.strip()
num_cases = int (line)
for i in range (num_cases):
line = sys.stdin.readline()
line = line.strip()
inp = line.split()
n = int(inp[0])
k = int(inp[1])
start = time.time()
print("Binary Search: " + str(binary_search(n, k)))
finish = time.time()
print("Time: " + str(finish - start))
print()
start = time.time()
print("Linear Search: " + str(linear_search(n, k)))
finish = time.time()
print("Time: " + str(finish - start))
print()
print()
if __name__ == "__main__":
main()
Binary Search: 152 Time: 9.512901306152344e05 Linear Search: 152 Time: 0.0005910396575927734 Binary Search: 54 Time: 4.696846008300781e05 Linear Search: 54 Time: 9.012222290039062e05
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started