Home > Python >Python Exercise: Hangover

Hangover

Improving Time Complexity by Dichotomy

In some cases, the data area of a problem is an ordered interval. Dichotomy is used to divide the interval into two subintervals and then determine if the process of computation is in the left subinterval or the right subinterval. If the solution isn’t obtained, then repeat the above steps. For a problem whose time complexity is O(n), if dichotomy can be used to solve it, its time complexity can be improved to O(log2(n)).

Dichotomy is used in many algorithms, such as binary search, recursive halving method, quick sort, merge sort, binary search tree, and segment tree. Among these methods, binary search and recursive halving method are relatively simple algorithms.

The idea for binary search is as follows: Suppose the data area is an interval in ascending order. The search begins by comparing x with the number in the middle of the interval. If x equals this number, the search terminates. If x is smaller than the number, then we need only search in the left half; if x is greater than the number, then we need only search in the right half. We repeat the above steps until the search ends.

Using Dichotomy to Solve Hangover problem

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards, you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general, you can make n cards overhang by 1/2 + 1/3 + 1/4 + … + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs the third by 1/3, the third overhangs the fourth by 1/4, and so on, and the bottom card overhangs the table by 1/(n + 1).

Input
The input consists of one or more test cases separated by comma. Each test case is a single positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.
Output
For each test case, output the minimum number of cards d necessary to achieve an overhang of at least c card lengths as c => d.
Comment submitted by guru at June 1, 2020, 12:38 a.m. 
Hint: Construct a list hangover_len from 0 cards to number of cards 
with a hangover length of 5.20. Then use dichotomy to search list
to find the output for the input.

You need login to comment

Solution submitted by Dzeng at July 28, 2020, 3:37 p.m.
import math numbertofind = input("Enter the number you want to find. Type exit to exit. ") a = 2 b = 1/a thesum = 0 alist = [] while thesum <= 5.20: thesum += b alist.append((thesum, a)) a += 1 b = 1/a def findnumber (hangovernumber, alist): index1 = 275 index2 = 0 while True: if alist[math.floor((index1+index2)/2)][0] > hangovernumber: index1 = math.floor((index1 + index2)/2) if index2 == index1: return index1 elif alist[math.floor((index1+index2)/2)][0] < hangovernumber: index2 = math.ceil((index1 + index2)/2) if index2 == index1: return index1 else: return index1 while str(numbertofind) != "exit": print(alist[findnumber(float(numbertofind), alist)][1] - 2) numbertofind = input("Enter the number you want to find. Type exit to exit. ")

You need login to submit your solution