"""
Problem 53: https://projecteuler.net/problem=53

Combinatoric selections

There are exactly ten ways of selecting three from five, 12345:

    123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,

nCr = n!/(r!(n−r)!),where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.
It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater
than one-million?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/17
'''

from functools import reduce
import math



def combins(n, r):
    '''
    >>> assert combins(5,3) == 10
    '''

    if r==0:
        return 1
    if r==1:
        return n
    if r > n:
        return 0
    if r > n//2:
        return combins(n, n-r)

    return reduce(lambda x, y: x*y, range(n-r+1, n+1))//math.factorial(r)


def solution(limit: int = 1000000) -> int:
    '''
    C(n,r), max(r) value when r=n/2

    '''
    count = 0

    for n in range(1, 101):
        maxCnr = combins(n, n//2)
        if maxCnr <= limit:
            continue
        else:
            if n % 2 == 0:
                count += 1
            else:
                count += 2

            for r in range(n//2-1, 0,-1):
                if combins(n,r) > limit:
                    count += 2
                else:
                    break 
    return count





if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 4075