Problem Description


 

Requirements

For a program, Eric has to write many lines of code before morning. He is dead tired and he wants to drink coffee to stay awake. Each cup of coffee helps him stay awake, but it also makes him jittery and he writes code slower. If he drinks too much coffee, he can't write any code at all. But, he wants to drink coffee as soon as possible, because feeling that tired is a horrible feeling. He wants to know - what is the minimum number of lines of code He needs to write before the first cup of coffee, so he can finish the code before his productivity reaches 0 and he falls asleep.

In addition, your code needs to gather efficiency data on linear and binary searches and determine how much faster the binary search is for different scenarios.

Example 1

Total lines of code to write: 199

After coffee, productivity drops by factor of: 2

Initial lines of code (how many lines of code before first cup of coffee): 20


 

RoundNew Lines of Code Lines of Code Written
120



 

Drink Coffee

20
220 // 2 = 1030
320 // 4 = 535
420 // 8 = 237
520 // 16 = 138
 20 // 32 = 0STOP

 

In this example, Eric reaches 0 productivity before he finishes the total lines of code. He will need to write more lines of code before having his first coffee.


 

Example 2


 

Lines of code to write: 199 (same as example 1)

After coffee, productivity drops by factor of: 2 (same as example 1)

Initial lines of code (how many lines of code before first cup of coffee): 120


 

RoundNew Lines of Code Lines of Code Written
1120




 

Drink Coffee

120
2120 // 2 = 60180
3120 // 4 = 30210
4120 // 8 = 15225
5120 // 16 = 7232
6120 // 32 = 3235
7120 // 64 = 1236
 120 // 128 = 0STOP

 

In this example, Eric completes all 199 lines of code before reaching 0 productivity. But, it is possible that he could have had his first cup of coffee sooner, maybe after writing 100 or 115 lines of code. He wants to know what is the least number of lines of code he can write initially so he can drink coffee as soon as possible, and still complete all the code before reaching 0 productivity.


 

Input

The first line of input files is the number of scenarios to analyze. This will be followed by one line for each scenario. Each line will have two numbers, the total number of lines of code to be written (between 1 and 1000000) and the productivity loss factor (between 2 and 10). You will read your input from standard input as given in the following format of work.in:

3

300 2

59 9

8000 5


 

Input validation:

The code can assume that the file is structured properly, that all tokens are integers and that all integers are within the specified range.
Output


 

In your output, each scenario will be separated by a header. Each scenario includes the following, with appropriate labels:

For binary search and then linear search:

The ideal number of lines of code to write before the first cup of coffee
How many times the sum_series method was called
How many seconds it took to find the solution
The last line of output states how much faster the binary search solution was.


 

The output for the example input file above is below.


 

=====> Case # 1

Binary Search:

Ideal lines of code before coffee:  152

sum_series called 13 times

Elapsed Time:  0.000051975 seconds


 

Linear Search:

Ideal lines of code before coffee:  152

sum_series called 152 times

Elapsed Time:  0.000386000 seconds


 

Binary Search was 7.4 times faster.



 

=====> Case # 2

Binary Search:

Ideal lines of code before coffee:  54

sum_series called 7 times

Elapsed Time:  0.000011921 seconds


 

Linear Search:

Ideal lines of code before coffee:  54

sum_series called 54 times

Elapsed Time:  0.000054121 seconds


 

Binary Search was 4.5 times faster.



 

=====> Case # 3

Binary Search:

Ideal lines of code before coffee:  6401

sum_series called 18 times

Elapsed Time:  0.000051975 seconds


 

Linear Search:

Ideal lines of code before coffee:  6401

sum_series called 6401 times

Elapsed Time:  0.013950109 seconds


 

Binary Search was 268.4 times faster.



 

Approach


 

It might not seem obvious at first, but this problem can be seen as a search problem. Given the following scenario from the input file, the code needs to determine the ideal number of lines of code to write before drinking the first cup of coffee in this case:

Total lines of code to be written: 300 (total_lines)
Productivity loss factor: 2 (prod_loss)

 

Related variables are:

Initial lines of code to be written before first cup of coffee (initial_lines)
Total lines that would be written before sleep, based on intial_lines (total_for_initial_lines)

 

Eric would like to have coffee as soon as possible, because he is tired. If he drinks coffee after writing 1 line of code, then he will write 1 // 2 lines of code after that, which is 0, and he will fall asleep before completing the work.


 

If Eric writes all 300 lines of code before the first cup of coffee, he will certainly complete all of the work. But, this is not the ideal solution, since he wants to drink coffee as soon as possible, and still complete the work.


 

The ideal initial number of lines of code to write before the first cup of coffee is somewhere between 1 and 300, inclusive. If you know how many lines of code can be finished for each number 1 - 300, then you could do a search of these results to find the ideal initial lines of code to write.


The sum_series method sum_series() accepts two variables:

the number of lines to write before drinking the first cup of coffee (1...300 in this example)
the productivity drop factor (2 in this example)
 

The method returns the number of lines of code that would be written in this case, before productivity reaches 0.

 

Template of Python file Work.py:


import sys
import time


# Purpose: Determines how many lines of code will be written
#          before the coder crashes to sleep
# Input: lines_before_coffee - how many lines of code to write before coffee
#        prod_loss - factor for loss of productivity after coffee
# Output: returns the number of lines of code that will be written
#         before the coder falls asleep
def sum_series(lines_before_coffee, prod_loss):
    pass
    '''##### ADD CODE HERE #####'''


# Purpose: Uses a linear search to find the initial lines of code to
#          write before the first cup of coffee, so that the coder
#          will complete the total lines of code before sleeping AND
#          get to have coffee as soon as possible.
# Input: total_lines - lines of code that need to be written
#        prod_loss - factor for loss of productivity after each coffee
# Output: returns the initial lines of code to write before coffee
def linear_search(total_lines, prod_loss):
    pass
    '''##### ADD CODE HERE #####'''


# Purpose: Uses a binary search to find the initial lines of code to
#          write before the first cup of coffee, so that the coder
#          will complete the total lines of code before sleeping AND
#          get to have coffee as soon as possible.
# Input: total_lines - lines of code that need to be written
#        prod_loss - factor for loss of productivity after each coffee
# Output: returns the initial lines of code to write before coffee
def binary_search(total_lines, prod_loss):
    pass
    '''##### ADD CODE HERE #####'''


''' ##### DRIVER CODE #####
 '''


def main():

    # Open input source

    debug = True
    if debug:
        in_data = open('work.in')
    else:
        in_data = sys.stdin

    # read number of cases
    line = in_data.readline().strip()
    num_cases = int(line)

    for i in range(num_cases):

        # read one line for one case
        line = in_data.readline().strip()
        data = line.split()
        total_lines = int(data[0])  # total number of lines of code
        prod_loss = int(data[1])  # read productivity loss factor

        print("=====> Case #", i + 1)

        # Binary Search
        start = time.time()
        print("Binary Search:")
        lines, count = binary_search(total_lines, prod_loss)
        print("Ideal lines of code before coffee:", lines)
        print("sum_series called", count, "times")
        finish = time.time()
        binary_time = finish - start
        print("Elapsed Time:", "{0:.8f}".format(binary_time),
              "seconds")
        print()

        # Linear Search
        start = time.time()
        print("Linear Search:")
        lines, count = linear_search(total_lines, prod_loss)
        print("Ideal lines of code before coffee:", lines)
        print("sum_series called", count, "times")
        finish = time.time()
        linear_time = finish - start
        print("Elapsed Time:", "{0:.8f}".format(linear_time),
              "seconds")
        print()

        # Comparison
        print("Binary Search was",
              "{0:.1f}".format(linear_time / binary_time),
              "times faster.")
        print()
        print()


if __name__ == "__main__":
    main()
 

Additional Test Cases:

Test input:
4
100 5
39 3
36 10
88888 7

Expected Output:
=====> Case # 1
Binary Search:
Ideal lines of code before coffee: 81
sum_series called 5 times
Elapsed Time: 0.00001502 seconds

Linear Search:
Ideal lines of code before coffee: 81
sum_series called 81 times
Elapsed Time: 0.00009012 seconds

Binary Search was 6.0 times faster.


=====> Case # 2
Binary Search:
Ideal lines of code before coffee: 27
sum_series called 6 times
Elapsed Time: 0.00001359 seconds

Linear Search:
Ideal lines of code before coffee: 27
sum_series called 27 times
Elapsed Time: 0.00003314 seconds

Binary Search was 2.4 times faster.


=====> Case # 3
Binary Search:
Ideal lines of code before coffee: 33
sum_series called 6 times
Elapsed Time: 0.00001001 seconds

Linear Search:
Ideal lines of code before coffee: 33
sum_series called 33 times
Elapsed Time: 0.00002670 seconds

Binary Search was 2.7 times faster.


=====> Case # 4
Binary Search:
Ideal lines of code before coffee: 76193
sum_series called 22 times
Elapsed Time: 0.00006223 seconds

Linear Search:
Ideal lines of code before coffee: 76193
sum_series called 76193 times
Elapsed Time: 0.17091823 seconds

Binary Search was 2746.7 times faster.
Test input:
5
1013 8
108 7
15 2
19 3
100 5

Expected Output:
=====> Case # 1
Binary Search:
Ideal lines of code before coffee: 888
sum_series called 14 times
Elapsed Time: 0.00003004 seconds

Linear Search:
Ideal lines of code before coffee: 888
sum_series called 888 times
Elapsed Time: 0.00114512 seconds

Binary Search was 38.1 times faster.


=====> Case # 2
Binary Search:
Ideal lines of code before coffee: 94
sum_series called 8 times
Elapsed Time: 0.00001621 seconds

Linear Search:
Ideal lines of code before coffee: 94
sum_series called 94 times
Elapsed Time: 0.00009084 seconds

Binary Search was 5.6 times faster.


=====> Case # 3
Binary Search:
Ideal lines of code before coffee: 8
sum_series called 1 times
Elapsed Time: 0.00000691 seconds

Linear Search:
Ideal lines of code before coffee: 8
sum_series called 8 times
Elapsed Time: 0.00001407 seconds

Binary Search was 2.0 times faster.


=====> Case # 4
Binary Search:
Ideal lines of code before coffee: 14
sum_series called 6 times
Elapsed Time: 0.00001287 seconds

Linear Search:
Ideal lines of code before coffee: 14
sum_series called 14 times
Elapsed Time: 0.00001788 seconds

Binary Search was 1.4 times faster.


=====> Case # 5
Binary Search:
Ideal lines of code before coffee: 81
sum_series called 5 times
Elapsed Time: 0.00001097 seconds

Linear Search:
Ideal lines of code before coffee: 81
sum_series called 81 times
Elapsed Time: 0.00008607 seconds

Binary Search was 7.8 times faster.