# Task

In the city, a bus named Fibonacci runs on the road every day.

There are `n` stations on the route. The Bus runs from station1 to stationn.

At the departure station(station1), `k` passengers get on the bus. 

At the second station(station2), a certain number of passengers get on and the same number get off. There are still `k` passengers on the bus.

From station3 to stationn-1, the number of boarding and alighting passengers follows the following rule:

- At stationi, the number of people getting on is the sum of the number of people getting on at the two previous stations(stationi-1 and stationi-2)
- The number of people getting off is equal to the number of people getting on at the previous station(stationi-1).

At stationn, all the passengers get off the bus. 

Now, The numbers we know are: `k` passengers get on the bus at station1, `n` stations in total, `m` passengers get off the bus at stationn.

We want to know: How many passengers on the bus when the bus runs out stationx.

# Input

- `k`: The number of passengers get on the bus at station1.
  - `1 <= k <= 100`


- `n`: The total number of stations(1-based).
  - `6 <= n <= 30`


- `m`: The number of passengers get off the bus at stationn.
  - `1 <= m <= 10^10`


- `x`: Stationx(1-based). The station we need to calculate.
  - `3 <= m <= n-1`


- All inputs are valid integers.

# Output

An integer. The number of passengers on the bus when the bus runs out stationx.

Difficulty: introductory

Starter code:

def calc(k,n,m,x):
	

Solutions:
def sim(k,n,p):
    r = [(k,k,0),(k,p,p)]
    for i in range(n-2):
        u,d = r[0][1]+r[1][1],r[1][1]
        r = [r[1],(r[1][0]+u-d,u,d)]
    return r[1][0]

def calc(k,n,m,x):
    z,o = sim(k,n-1,0), sim(k,n-1,1)
    return sim(k,x,(m-z)//(o-z))

def fibLikeGen():
    a,b = (1,0), (0,1)                  # a: station i-1, b: station i
    while 1:
        yield a,b
        a,b = b, tuple(x+y for x,y in zip(a,b))

gen    = fibLikeGen()
SUM_AT = [(), (1,0), (1,0)]             # (k,l)
        
def getCoefs(n):
    while len(SUM_AT) <= n:
        a,b = next(gen)
        SUM_AT.append(tuple(x+y for x,y in zip(a,SUM_AT[-1])))
    return SUM_AT[n] 


def calc(k,n,m,x):
    a,b = getCoefs(n-1)
    l   = (m-a*k) // b
    a,b = getCoefs(x)
    return a*k + b*l

def fib(n, a, b):
    for i in range(n):
        yield a
        a, b = b, a+b
        
def calc(k,n,m,x):
    if x <= 2:
        return k
    if x == 3:
        return 2 * k
    b = 2 + sum(fib(n-4-1, 1, 1))
    a = 1 + sum(fib(n-4-1, 1, 2))
    c = (m - b*k) // a
    b = 2 + sum(fib(x-4, 1, 1))
    a = 1 + sum(fib(x-4, 1, 2))
    return k*b + c*a

fib = {3: 0, 4: 1, 5: 1}
for i in range(6, 31):
    fib[i] = fib[i - 2] + fib[i - 1]

def coefficients(n):
    y, z = 2, 0 # coefficients for number of passengers at station 3
    for i in range(4, n):
        y += fib[i - 1]
        z += fib[i]
    return y, z

def calc(k, n, m, x):
    y, z = coefficients(n)
    station2 = (m - y * k) // z
    y, z = coefficients(x + 1)
    return y * k + z * station2

FIB = [0, 1]
for _ in range(1000): FIB.append(FIB[-2] + FIB[-1])

def calc(k, n, m, x):
    l = (m - (FIB[n-3] + 1) * k) // (FIB[n-2] - 1)
    return (FIB[x-2] + 1) * k + (FIB[x-1] - 1) * l

from functools import reduce, lru_cache


def calc(k,n,m,x):
    n_of_eq_var = sum(fib(i) for i in range(1, n-4)) + 2
    got_on_2nd = int(
        (m - k * n_of_eq_var) / sum(fib(i) for i in range(1, n-3))
    )
    
    return reduce(
        lambda result, i: result+fib(i, k, got_on_2nd), range(1, x-1), k
    )


@lru_cache(None)
def fib(n, fib_1=1, fib_2=1):
    for _ in range(n-2):
        fib_1, fib_2 = fib_2, fib_1+fib_2

    return fib_2 if n > 1 else fib_1

def calc(k,n,m,x):
     
    f1=1
    f2=0
    fz2=0
    s=0
    t=0
    for i in range(1,n-3) :
        s+=f2
        a=f1
        f1=a+f2
        f2=a
        if i==x-3 : 
            t =s 
            fz2=f2
    
    A=(m-k*(s+2))/(s+f2)
    return A*(t+fz2)+k*(t+2)

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}

    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize #makes things alot faster
def fib_spec(n): #that is the gain per station, so really we have to take the sum of all n's
    if n == 0:
        return (1, 0)
    elif n == 1:
        return (0, 1)
    else:
        k_1, s_1 = fib_spec(n-1)
        k_2, s_2 = fib_spec(n-2)
        return (k_1+k_2, s_1+s_2)


def calc(k,n,m,x):
    if x in (1,2):
        return k
    elif x == 3:
        return 2*k
    s_ = 0
    k_ = 1
    for i in range(n-3):
        tmp_k, tmp_s = fib_spec(i)
        s_ += tmp_s
        k_ += tmp_k
        if i == x-3:
            s_x, k_x = s_, k_
    s = (m-k*k_)//s_
    return k_x*k+s_x*s

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}

    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize
def fib_spec(n): #that is the gain per station, so really we have to take the sum of all n's
    if n == 0:
        return (1, 0)
    elif n == 1:
        return (0, 1)
    else:
        k_1, s_1 = fib_spec(n-1)
        k_2, s_2 = fib_spec(n-2)
        return (k_1+k_2, s_1+s_2)


def fib(k, s, n):
    if n == 0:
        return k
    elif n == 1:
        return s
    else:
        return fib(k, s, n-1) + fib(k, s, n-2)

def calc(k,n,m,x):
    if x in (1,2):
        return k
    elif x == 3:
        return 2*k
    s_ = 0
    k_ = 1
    for i in range(n-3):
        tmp_k, tmp_s = fib_spec(i)
        s_ += tmp_s
        k_ += tmp_k
    s = (m-k*k_)//s_
    
    s_ = 0
    k_ = 1
    for i in range(x-2):
        tmp_k, tmp_s = fib_spec(i)
        s_ += tmp_s
        k_ += tmp_k
    return k_*k+s_*s



def calc(k,n,m,x):
    # solve how many people get on board at station 2:
    on_list_x = [0, 1, 1, 2, 3]  # num of times x people get on
    on_list_k = [k, 0, k, k, 2*k]  # k people get on

    off_list_x = [0, 1, 1, 1, 2]
    off_list_k = [0, 0, 0, k, k]
    # total a*x + b*k at index n-1 == m
    while len(on_list_x) < n-1:
        on_list_x.append(on_list_x[-1] + on_list_x[-2])
        on_list_k.append(on_list_k[-1] + on_list_k[-2])
        off_list_x.append(off_list_x[-1] + off_list_x[-2])
        off_list_k.append(off_list_k[-1] + off_list_k[-2])
    num_x = sum(on_list_x) - sum(off_list_x)
    num_k = sum(on_list_k) - sum(off_list_k)
    x_val = (m - num_k) / num_x  # people at station 2
    
    # now all numbers of boarding and leaving people can be calculated:  
    passengers_station_x = (sum(on_list_x[:x]) - sum(off_list_x[:x]))*x_val + sum(on_list_k[:x]) - sum(off_list_k[:x])

    return int(passengers_station_x)