Problem:
 Score : 800 points    Problem Statement There are N stores called Store 1 , Store 2 , \cdots , Store N . Takahashi, who is at his house at time 0 , is planning to visit some of these stores.  It takes Takahashi one unit of time to travel from his house to one of the stores, or between any two stores.  If Takahashi reaches Store i at time t , he can do shopping there after standing in a queue for a_i \times t + b_i units of time. (We assume that it takes no time other than waiting.)  All the stores close at time T + 0.5 . If Takahashi is standing in a queue for some store then, he cannot do shopping there.  Takahashi does not do shopping more than once in the same store.  Find the maximum number of times he can do shopping before time T + 0.5 .      Constraints  All values in input are integers.  1 \leq N \leq 2 \times 10^5  0 \leq a_i \leq 10^9  0 \leq b_i \leq 10^9  0 \leq T \leq 10^9         Input Input is given from Standard Input in the following format:  N  T  a_1  b_1  a_2  b_2  \vdots  a_N  b_N       Output Print the answer.        Sample Input 1 3 7
2 0
3 2
0 3      Sample Output 1 2  Here is one possible way to visit stores:   From time 0 to time 1 : in 1 unit of time, he travels from his house to Store 1 .  From time 1 to time 3 : for 2 units of time, he stands in a queue for Store 1 to do shopping.  From time 3 to time 4 : in 1 unit of time, he travels from Store 1 to Store 3 .  From time 4 to time 7 : for 3 units of time, he stands in a queue for Store 3 to do shopping.   In this way, he can do shopping twice before time 7.5 .       Sample Input 2 1 3
0 3      Sample Output 2 0       Sample Input 3 5 21600
2 14
3 22
1 3
1 10
1 9      Sample Output 3 5       Sample Input 4 7 57
0 25
3 10
2 4
5 15
3 22
2 14
1 15      Sample Output 4 3

Solution (Python):
from operator import itemgetter
import bisect


n, t = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
INF = t + 1
LIMIT = 60



mrkt_a0 = []
mrkt_others = []

for i in range(n):
    a, b = info[i]
    if a == 0:
        mrkt_a0.append((a, b))
    else:
        comp = a / (1 + b)
        mrkt_others.append((a, b, comp))

mrkt_a0.sort(key=itemgetter(1))
mrkt_others.sort(key=itemgetter(2), reverse=True)



times_a0 = [0]
for a, b in mrkt_a0:
    times_a0.append(times_a0[-1] + 1 + b)


len_others = len(mrkt_others)
dp = [[INF] * LIMIT for i in range(len_others + 1)]
dp[0][0] = 0

for i in range(len_others):
    a, b, _ = mrkt_others[i]
    for cnt in range(LIMIT):
        
        dp[i + 1][cnt] = min(dp[i][cnt], dp[i + 1][cnt])
        
        if cnt + 1 < LIMIT:
            dp[i + 1][cnt + 1] = min(a * (dp[i][cnt] + 1) + b + dp[i][cnt] + 1, dp[i + 1][cnt + 1])

ans = 0
for cnt in range(LIMIT):
    if dp[-1][cnt] == t + 1:
        continue
    nokori = t - dp[-1][cnt]
    cnt_a0 = bisect.bisect_right(times_a0, nokori) - 1
    ans = max(ans, cnt + cnt_a0)

print(ans)

Solution (Python):
N,T=map(int,input().split())
shop=[]
easyshop=[]
for i in range(N):
    a,b=map(int,input().split())
    A,B=a+1,a+b+1
    if A==1:
        easyshop.append(B)
    else:
        shop.append(((A-1)/B,A,B))

shop.sort(reverse=True)
easyshop.sort()

if shop:
    dp=[0,shop[0][2]]
    for i in range(1,len(shop)):
        ndp=[]
        val,A,B=shop[i]
        for j in range(len(dp)):
            t=min(A*dp[j-1]+B,dp[j])
            if T>=t:
                ndp.append(t)
            else:
                break
        else:
            t=A*dp[-1]+B
            if T>=t:
                ndp.append(t)
        dp=ndp

    import bisect
    id=bisect.bisect_right(dp,T)
    ans=id-1
    if not easyshop:
        print(ans)
    else:
        n=len(easyshop)
        for i in range(1,n):
            easyshop[i]+=easyshop[i-1]
        for i in range(n):
            if T>=easyshop[i]:
                id=bisect.bisect_right(dp,T-easyshop[i])
                ans=max(ans,id+i)
            else:
                break
        print(ans)
else:
    import bisect
    n=len(easyshop)
    for i in range(1,n):
        easyshop[i]+=easyshop[i-1]
    ans=bisect.bisect_right(easyshop,T)
    print(ans)

Solution (Python):
def examA():
    S = SI()
    if len(S)%2==1:
        print("No")
        return
    for i in range(len(S)//2):
        if S[i*2:i*2+2]!="hi":
            print("No")
            return
    print("Yes")
    return

def examB():
    a, b, M = LI()
    A = LI()
    B = LI()
    D = [LI()for _ in range(M)]
    ans = min(A) + min(B)
    for x,y,c in D:
        cur = A[x-1]+B[y-1]-c
        ans = min(ans,cur)
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        
        W = [-1] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    
    odd = 0
    for l in L:
        if l==-1:
            print(-1)
            return
        if l%2==1:
            odd += 1
    G = []
    if odd*2<N:
        for i in range(N):
            if L[i]%2==1:
                G.append(i)
    else:
        for i in range(N):
            if L[i]%2==0:
                G.append(i)

    used = [False]*(N+1)
    ans = [0]*N
    if N//3>=len(G):
        cur = 3
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    else:
        cur = 1
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
            if cur>N:
                cur = 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    print(" ".join(map(str,ans)))
    return

def examD():
    N, T = LI()
    A = []
    A0 = []
    for _ in range(N):
        a, b = LI()
        if a==0:
            A0.append(b)
        else:
            A.append((a/(b+1),a,b))
    A.sort(reverse=True)
    n = len(A)
    S = min(31,n)
    dp = [[inf]*(n+1) for _ in range(S+1)]
    dp[0][0] = 0
    for i,(_,a,b) in enumerate(A):
        for j in range(S):
            now = dp[j][i] + 1
            dp[j][i+1] = min(dp[j][i+1],dp[j][i])
            if now==inf:
                continue
            dp[j+1][i+1] = min(dp[j+1][i+1],now+a*now+b)
    
    dp0 = [0]*(len(A0)+1)
    A0.sort()
    for i,b in enumerate(A0):
        dp0[i+1] = dp0[i]+b+1
    ans = 0
    for i in range(S+1):
        t = T - min(dp[i])
        if t<0:
            break
        cur = (bisect.bisect_right(dp0,t)-1) + i
        if ans<cur:
            ans = cur
    print(ans)
    return

def examE():
    N, M = LI()
    H = 2**N-1; W = 2**M -1
    ans = [[0]*W for _ in range(H)]
    for h in range(H):
        flagh = False
        for m in range(1,11)[::-1]:
            if (h+1)%(2**m)==0:
                flagh = 2**m*2
        for w in range(W):
            flagw = False
            for m in range(1,11)[::-1]:
                if (w+1)%(2**m)==0:
                    flagw = 2 ** m * 2
            if flagh and flagw:
                continue
            ans[h][w] = 1
    for v in ans:
        print("".join(map(str,v)))
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):
import sys
input = sys.stdin.readline
n, t = map(int, input().split())
shop = []
shop_0 = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        shop_0.append((a, b))
        n -= 1
    else:
        shop.append((a, b))
shop.sort(key = lambda x: (x[0])/(1+x[1]), reverse = True)
shop_0.sort()

inf = 10**18
dp = [[inf for i in range(30)] for j in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(29):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + (dp[i][j]+1)*(shop[i][0])+shop[i][1]+1)



ans = 0
for i in range(30):
    tmp = i
    T = dp[n][i]
    if T > t:
        continue
    else:
        for j in range(len(shop_0)):
            if T+shop_0[j][1]+1 <= t:
                T += shop_0[j][1]+1
                tmp += 1
            else:
                break
    ans = max(tmp, ans)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from bisect import bisect_right
from itertools import accumulate
from functools import cmp_to_key

def cmp(store1, store2):
    if store1 == store2:
        return 0
    a1, b1 = store1
    a2, b2 = store2
    return -1 if a2 * (b1 + 1) <= a1 * (b2 + 1) else 1

def resolve():
    n, T = map(int, input().split())
    AB = []
    zero = []
    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0:
            AB.append((a, b))
        else:
            zero.append(b + 1)

    AB.sort(key = cmp_to_key(cmp))
    zero.sort()
    zero = list(accumulate(zero))

    max_store = 30
    dp = [T + 1] * max_store
    dp[0] = 0
    for a, b in AB:
        for i in range(max_store - 2, -1, -1):
            t = dp[i]
            dp[i + 1] = min(dp[i + 1], (a + 1) * (t + 1) + b)

    res = 0
    for i in range(max_store):
        t = dp[i]
        if t > T:
            break
        rest = T - t
        res = max(res, i + bisect_right(zero, rest))

    print(res)
resolve()

Solution (Python):
n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab0 = []
ab1 = []
for i in range(n):
  if ab[i][0] == 0:
    ab0.append(ab[i][1])
  else:
    ab1.append(ab[i])
ab0.sort()
ab1.sort(key = lambda x:x[0]/(x[1]+1),reverse=True)
n = len(ab1)
dp = [[10**10 for i in range(31)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0] = 0
for i in range(1,n+1):
  a,b = ab1[i-1]
  for j in range(1,31):
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1+a*(dp[i-1][j-1]+1)+b)
m = len(ab0)
ans = 0
for j in range(31):
  if dp[n][j] > t:
    continue
  anstmp = j
  ttmp = t-dp[n][j]
  i = 0
  while i <= m-1 and ttmp >= ab0[i]+1:
    ttmp -= ab0[i]+1
    anstmp += 1
    i += 1
  ans = max(ans,anstmp)
print(ans)

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            cand = (dp[visited] + 1) * (coef + 1) + const
            if dp[visited + 1] > cand:
                dp[visited + 1] = cand  

    def accumulate(a):
        s = 0
        yield s  
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = 0
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  
        while cnt > 0 and acc[cnt] > rest:  
            cnt -= 1
        visited += cnt
        if visited > ans:
            ans = visited  
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = 0
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  
        while cnt > 0 and acc[cnt] > rest:  
            cnt -= 1
        visited += cnt
        if visited > ans:
            ans = visited  
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = 0
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  
        while cnt > 0 and acc[cnt] > rest:  
            cnt -= 1
        ans = max(ans, visited + cnt)
    print(ans) 


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = {0}
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  
        while cnt > 0 and acc[cnt] > rest:  
            cnt -= 1
        ans.add(visited + cnt)
    print(max(ans))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break



DP=[[T+1]*(k+1) for i in range(30)]
for i in range(k+1):
    DP[0][i]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(1,30):
    for j in range(1,k+1):
        nt=nexttime(DP[i-1][j-1],M[j-1][0],M[j-1][1])
        DP[i][j]=min(DP[i][j-1],nt)
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)

Solution (Python):
import sys
from bisect import bisect_right
 
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N)]

b0 = []
ab1 = []


for a,b in ab:
    if a == 0:
        
        b0.append(b+1)
    else:
        ab1.append([(b+1)/a, a, b])

N0 = len(b0)
N1 = len(ab1)

b0.sort()


if N0>0:
    b_ruiseki = [0]*N0
    b_ruiseki[0] = b0[0]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

ab1.sort()

INF = T + 100
 
dp = [[INF]*31 for i in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    
    for j in range(31):
        if j > i+1:
            break
        if j == 0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-1]+1 + ab1[i][1]*(dp[i][j-1]+1) + ab1[i][2])

for j in range(31):
    if dp[N1][j] > T:
        break    
    
    num0 = bisect_right(b_ruiseki, T - dp[N1][j])
    ans = max(ans, j + num0)
        
    
print(ans)

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





N, T = list(map(int, sys.stdin.buffer.readline().split()))
A, B = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(N)]))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)


A += 1
B += 1
T += 1


I = np.argsort((A - 1) / B)[::-1]
A = A[I]
B = B[I]

idx_zero = np.searchsorted((A == 1).astype(int), 1, side='left')
A1 = A[:idx_zero]
B1 = B[:idx_zero]
B2 = np.msort(B[idx_zero:])

MAX_COUNT = (10 ** 9).bit_length() + 2

dp = np.full((idx_zero + 1, MAX_COUNT), T + 1, dtype=int)
dp[:, 0] = 1
for x in range(MAX_COUNT - 1):
    next_col = dp[:-1, x] * A1 + B1
    np.minimum(next_col, T + 1, out=next_col)
    np.minimum.accumulate(next_col, out=next_col)
    dp[1:, x + 1] = next_col


cum = B2.cumsum()
counts = np.searchsorted(cum, T - dp[idx_zero], side='right')
ans = counts + np.arange(dp.shape[1])
print(ans[dp[idx_zero] <= T].max())

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from itertools import accumulate
def resolve():
    N, T = lr()
    ab = []
    a0b = [0]
    for i in range(N):
        a, b = lr()
        if a >= 1:
            ab.append([a, b])
        else:
            a0b.append(b+1)
    ab = sorted(ab, key=lambda x: x[0]/(x[1]+1))[::-1]
    a0b = sorted(a0b)
    dp = [T+1]*30
    dp[0] = 0
    for a, b in ab:
        for i in range(28, -1, -1):
            t = (a+1)*(dp[i]+1)+b
            if t < dp[i+1]:
                dp[i+1] = t
    ans = 0
    acc = list(accumulate(a0b))
    num = len(acc)-1
    for i in range(30):
        t = dp[i]
        if t > T+0.5:
            break
        while num > 0 and t+acc[num] > T+0.5:
            num -= 1
        ans = max(ans, i+num)
    print(ans)
resolve()

Solution (Python):
import sys
from bisect import bisect_right

N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]

b0 = []
ab1 = []
for a,b in ab:
    if a==0:
        b0.append(b+1)
    else:
        ab1.append([(b+1)/a, a, b])

N0 = len(b0)
N1 = len(ab1)

b0.sort()
if N0>0:
    b_ruiseki = [0]*N0
    b_ruiseki[0] = b0[0]
    for i in range(1,N0):
        b_ruiseki[i] = b_ruiseki[i-1] + b0[i]
else:
    b_ruiseki = []

ab1.sort()

INF = T + 100

dp = [[INF]*31 for _ in range(N1+1)]
dp[0][0] = 0
ans = 0
for i in range(N1):
    
    
    for j in range(31):
        if j>i+1:break
        if j==0:
            dp[i+1][j] = 0
        else:
            dp[i+1][j] = min(dp[i][j], (dp[i][j-1]+1)*(ab1[i][1]+1)+ab1[i][2])

for j in range(31):
    if dp[N1][j]>T:break    
    
    num0 = bisect_right(b_ruiseki, T - dp[N1][j])
    ans = max(ans, j + num0)
        
    
print(ans)

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0



for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Solution (Python):
import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0



for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)

Solution (Python):
from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
dp = [INF for _ in range(30)]
dp[0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m)[::-1]:
        dp[j] = min(dp[j], dp[j-1] + 1 +
                         shop[i][0]*(dp[j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[i]) + i)

print(ans)

Solution (Python):
from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
dp = [[INF for _ in range(30)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])
        dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j-1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Solution (Python):
from bisect import bisect_right
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


n, t = map(int, input().split())

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10

dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    
    N, T = map(int, input().split())
    a, b = [], []
    a0_b = []
    for i in range(N):
        a_in, b_in = map(int, input().split())
        if a_in == 0:
            a0_b.append(b_in)
        else:
            a.append(a_in)
            b.append(b_in)
    L = len(a)

    
    ab_ratio = [a[i] / (b[i] + 1) for i in range(L)]
    key = sorted(range(L), key=lambda x: -ab_ratio[x])
    a = [a[i] for i in key]
    b = [b[i] for i in key]
    a0_b.sort()

    
    
    
    J_MAX = min(L + 1, 29)
    dp = [[float('inf') for _ in range(J_MAX)] for _ in range(L + 1)]
    dp[0][0] = 0
    for i in range(L):
        for j in range(J_MAX):
            if j > 0:
                dt = 1 + a[i] * (dp[i][j - 1] + 1) + b[i]
                if dp[i][j - 1] + dt <= T:
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - 1] + dt)
                else:
                    dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]

    
    ans = 0
    for i in range(J_MAX):
        if dp[L][i] == float('inf'):
            break
        else:
            time_cnt = dp[L][i]
            shop_cnt = i
            for t_b in a0_b:
                if time_cnt + 1 + t_b <= T:
                    time_cnt += 1 + t_b
                    shop_cnt += 1
            if ans < shop_cnt:
                ans = shop_cnt

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Store:
    def __init__(self,a,b):
        self.a=a
        self.b=b

    def __eq__(self, other):
        return (self.b+1)*other.a==self.a*(other.b+1)

    def __lt__(self, other):
        return (self.b+1)*other.a<self.a*(other.b+1)

    def __le__(self, other):
        return (self.b+1)*other.a<=self.a*(other.b+1)

    def __gt__(self, other):
        return (self.b+1)*other.a>self.a*(other.b+1)

    def __ge__(self, other):
        return (self.b+1)*other.a>=self.a*(other.b+1)

from itertools import accumulate
from bisect import bisect
def main():
    inf=10**9+7
    n,t=MI()
    ab=LLI(n)
    ss=[]
    a0=[]
    for a,b in ab:
        if a==0:a0.append(b+1)
        else:ss.append(Store(a,b))
    n=len(ss)
    ss.sort()
    dp=[[inf]*31 for _ in range(n+1)]
    dp[0][0]=0
    for i,s in enumerate(ss):
        a,b=s.a,s.b
        for j in range(30):
            pre=dp[i][j]
            if pre==inf:continue
            nt=a*(pre+1)+b+pre+1
            if nt<=t:dp[i+1][j+1]=min(dp[i+1][j+1],nt)
            dp[i+1][j]=min(dp[i+1][j],pre)
    a0.sort()
    a0=[b for b in accumulate(a0)]
    ans=0
    for j in range(30):
        val=dp[n][j]
        if val==inf:continue
        ans=max(ans,bisect(a0,t-dp[n][j])+j)
    print(ans)

main()

Solution (Python):
import sys
from bisect import bisect
from itertools import accumulate

n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
    a, b = map(int, line.split())
    if a == 0:
        constant.append(b + 1)
    else:
        variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1

dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
    for j in range(t2 - 1, -1, -1):
        if dp[j] == INF:
            continue
        tmp = (a + 1) * dp[j] + b + 1
        if tmp > t:
            continue
        if dp[j + 1] > tmp:
            dp[j + 1] = tmp

const_acc = list(accumulate(constant))
ans = 0

for i, c in enumerate(dp):
    if c == INF:
        break
    remaining = t - c
    k = bisect(const_acc, remaining)
    ans = max(ans, i + k)

print(ans)

Solution (Python):


import sys
import math
import itertools
import bisect

INF = int(1e18)

n, t = map(int, sys.stdin.readline().split())

nzshops = []
zshops = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    (zshops if a == 0 else nzshops).append((a, b))

nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
zshops.sort()

dp = [0]
for i in range(len(nzshops)):
    a, b = nzshops[i]
    dp.append(INF)
    for c in range(len(dp) - 1, 0, -1):
        x = dp[c - 1] + 1
        dp[c] = min(dp[c], x + x * a + b)
    dp = [x for x in dp if x <= t]

rs = list(itertools.accumulate(1 + b for _, b in zshops))
ans = max(c + bisect.bisect(rs, t - dp[c])
        for c in range(len(dp)) if dp[c] <= t)

print(ans)

Solution (Python):


import sys
import math
import itertools
import bisect

INF = int(1e18)

def main():
    n, t = map(int, sys.stdin.readline().split())

    nzshops = []
    zshops = []
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        (zshops if a == 0 else nzshops).append((a, b))

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [0]
    for i in range(len(nzshops)):
        dp_ = dp + [INF]
        for c in range(1, len(dp_)):
            a, b = nzshops[i]
            x = dp[c - 1] + 1
            dp_[c] = min(dp_[c], x + x * a + b)
        dp = [x for x in dp_ if x <= t]

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, t - dp[c])
            for c in range(len(dp)) if dp[c] <= t)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()