Problem:


Problem H: Nearest Station

うさぎがある電車のチケットをn 枚持っている. チケットにはそれぞれ0 からn − 1 までの番号がついていて, k 番のチケットを使うと, p&sdot;ak + q&sdot;bk 駅進むことができる.

うさぎは今いる駅からm 駅進んだ駅にあるニンジン食べ放題の店に行きたいが, なるべく歩く距離を短くしたい. 駅は等間隔に並んでいる. チケットを電車の上り線で進むことのみに用いるとき, うさぎは最小何駅分の徒歩で店に着けるか.

Input

1 ≤ n, m, a, b, p, q ≤ 1 000 000 000 000 (整数)

Output

うさぎは最小何駅分の徒歩で店に着けるか, その数を一行に出力せよ.

Sample Input 1

6 200 2 3 4 5

Sample Output 1

1

Sample Input 2

6 1 2 3 4 5

Sample Output 2

1



Sample input:
6 200 2 3 4 5


Sample output:
1

Submission status: Accepted

Solution code:
def solve():
    n,m,a,b,p,q = map(int,input().split())
    if a==1 and b==1:
        if (p+q)*n <= m:
            return m - (p+q)*n
        else:
            k = m//(p+q)
            return min(m-k*(p+q),(k+1)*(p+q)-m)
    else:
        ans = m
        for i in range(min(n-1,40),-1,-1):
            f = p*(a**i) + q*(b**i)
            if m < f:
                ans = min(ans, f-m)
            else:
                m -= f
            ans = min(ans,m)
        return ans

def main():
    print(solve())

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, M, A, B, P, Q = map(int, readline().split())
    ans = M
    if A == B == 1:
        v = P+Q
        k = min(N, M // v)
        ans = min(ans, M - k*v)
        if k+1 <= N:
            ans = min(ans, (k+1)*v - M)
    else:
        k = 0
        V = []
        va = 1; vb = 1
        while k < N:
            v = P*va + Q*vb
            V.append(v)
            if v > M:
                break
            va *= A; vb *= B
            k += 1
        def make(S):
            s = {0}
            for v in S:
                t = set(s)
                for e in s:
                    t.add(e + v)
                s = t
            return sorted(s)
        L = len(V)
        S0 = make(V[:L//2]); S1 = make(V[L//2:])
        t = len(S1)-1
        for s0 in S0:
            while t > 0 and s0 + S1[t] > M:
                t -= 1
            if s0 + S1[t] <= M:
                ans = min(ans, M - s0 - S1[t])
        t = len(S1)-1
        for s0 in S0:
            while t > 0 and s0 + S1[t-1] >= M:
                t -= 1
            if s0 + S1[t] >= M:
                ans = min(ans, s0 + S1[t] - M)
    write("%d\n" % ans)
solve()