In fact, he is the most. But first things first.
 
 

Statement of the problem

 
I master the python, I solve everything on Codewars. Faced with a known problem about skyscraper and eggs. The only difference is that the original data - not 100 floors and 2 eggs, but a little more.
 
Given: N eggs, M attempts to throw them, an endless skyscraper.
 
 
Identify: the maximum floor from which you can throw an egg without breaking it. Eggs are spherical in vacuum and, if one of them did not break, falling, for example, from the 99th floor, then the rest will also withstand a drop from all floors less than one hundred.
 
 
0 <= N, M <= 20000.
 
The run time of two dozen tests is 12 seconds.
 
Triangle of Pascal , so it is officially called. Infinite table of binomial coefficients. So the answer to the problem with N eggs and M throws is the sum of the first N coefficients in the expansion of the Newton binomial of the Mth power, except for the zero one.
 
 
An arbitrary binomial coefficient can be calculated through the factorials of the line number and the coefficient number in the line: bk = m! /(N! * (M-n!)). But the most pleasant - you can consistently calculate the numbers in a row, knowing its number and zero coefficient (always one): bk[n]  = bk[n-1]* (m - n + 1) /n. At each step the numerator decreases by one, and the denominator increases. And the laconic final solution looks like this:
 
 

def height (n, m):
h, bk = ? 1 # height and zero binomial coefficient
for i in range (? n + 1):
bk = bk * m //i
h + = t
m- = 1
return h

 
33 ms. on the calculation of f (947? 10000)! This solution can also be optimized, although it works well in the specified ranges. If n lies in the second half of the triangle, then you can invert it to m-n, calculate the sum of the first n coefficients and subtract it from 2 ^ m-2. If n is close to the middle and m is odd, then the calculations can also be shortened: the sum of the first half of the line will be 2 ^ (m-1) -? the last factor in the first half can be calculated through the factorials, its number is (m-1) /? and then either continue to add coefficients, if n in the right half of the triangle, or take away, if in the left. If m is even, then you can not count half the line, but you can find the sum of the first m /2 + 1 coefficients, calculating the average through factorials and adding half of it to 2 ^ (m-1) -1. On the input data in the vicinity of 10 ^ 6 this greatly reduces the execution time.
 
 
Even after a successful decision, I began to look for someone else's research on this issue, but found only the same thing, with interviews, with only two eggs, and this is not sports. The Internet will be incomplete without my decision, I decided, and that's it.