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



Sample input:
3 7
2 0
3 2
0 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
# hitachi2020 D

n, t = map(int, input().split())
cost = []
for i in range(n):
    a, b = map(int, input().split())
    cost.append([a, b])

start_time = 0
shop_count = 0

while True:
    min_time = 10**10

    for pair in cost:
        a, b = pair[0], pair[1]
        time = start_time + 1
        time = time + (a * time) + b
        #print(time)
        if time < min_time:
            min_time = time
            pop_index = cost.index(pair)
    
    start_time = min_time
    cost.pop(pop_index)
    #print("    " + str(start_time))

    if min_time <= t + 0.5:
        shop_count += 1
        if len(cost) == 0:
            break
    else:
        break

print(shop_count)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import cmp_to_key
import itertools

N, T = map(int, readline().split())
m = map(int, read().split())
AB0 = []
AB1 = []
for a,b in zip(m,m):
    if a == 0:
        AB0.append(b)
    else:
        AB1.append((a,b))

def sort_func(ab0, ab1):
    a0, b0 = ab0
    a1, b1 = ab1
    return a1*b0 - a0*b1

AB0.sort()
AB1.sort(key=cmp_to_key(sort_func))
AB0, AB1

def compute_0():
    INF = T + 1
    dp = [INF] * 35
    dp[0] = 0
    for a,b in AB1:
        for n in range(33, -1, -1):
            if dp[n] > T:
                continue
            x = (dp[n] + 1) * (a + 1) + b
            if x < dp[n+1]:
                dp[n+1] = x
    return dp

def compute_1():
    return [0] + list(itertools.accumulate(x + 1 for x in AB0))

dp0 = compute_0()
dp1 = compute_1()

R = len(dp1) - 1
answer = 0
for i,x in enumerate(dp0):
    if x > T:
        break
    while x + dp1[R] > T:
        R -= 1
    value = i + R
    if answer < value:
        answer = value

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline

INF = 10**18+3
N, T = map(int, readline().split())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
ABzero = [b for a, b in AB if a == 0]
ABnonzero = [(a, b) for a, b in AB if a]
ABnonzero.sort(key = lambda x: x[1]/x[0])


dp = [0]
for a, b in ABnonzero:
    dp2 = dp + [INF]
    for j in range(1, len(dp2)):
        dp2[j] = min(dp2[j], (dp[j-1]+1)*(a+1)+b)
    dp = [d for d in dp2 if d <= T]

ABzero.sort()
dpzero = [0] + [b+1 for b in ABzero]
for i in range(1, len(dpzero)):
    dpzero[i] += dpzero[i-1]

DP = [INF]*(N+1)
for i in range(len(dp)):
    for j in range(len(dpzero)):
        DP[i+j] = min(DP[i+j], dp[i] + dpzero[j])

DP = [d for d in DP if d <= T]
print(max(0, len(DP)-1))

Submission status: Wrong Answer

Solution code:
n, T = map(int, input().split())

shop = [tuple(map(int, input().split())) for i in range(n)]

heavy = [s for s in shop if s[0] != 0]
light = [s[1] + 1 for s in shop if s[0] == 0]

light.sort()

from functools import cmp_to_key

def cmp(p, q):
    (ap, bp) = p
    (aq, bq) = q
    ap += 1
    aq += 1
    return aq * bp + aq + bq < ap * bq + ap + bp

heavy = sorted(heavy, key=cmp_to_key(cmp))

dp = [1<<40] * 33
dp[0] = 0
for (a, b) in heavy:
    for i in range(32, 0, -1):
        dp[i] = min(dp[i], (dp[i-1] + 1) *  (a+1) + b)

light_cnt = 0
light_sum = 0

ans = 0
for i in range(32, -1, -1):
    if dp[i] > T:continue
    rest = T - dp[i]
    while light_cnt < len(light) and light_sum <= rest:
        light_sum += light[light_cnt]
        light_cnt += 1
    ans = max(ans, i + max(0, light_cnt-1))
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
def mi():return map(int,input().split())
n,maxt=mi()
import numpy as np
a=[]
b=[]
used=[]
INF=10**10
for _ in range(n):
    at,bt=mi()
    a+=at,;b+=bt,
a=np.array(a,dtype=np.int64)
b=np.array(b,dtype=np.int64)

def f(jikan):
    ret=a*jikan+b
    return ret

ans=0
t=0
while t<maxt:
    t+=1
    tmp=f(t)
    mintmp=min(tmp)
    basho=np.where(tmp==mintmp)
    a[basho[0]]=INF
    b[basho[0]]=INF
    t+=mintmp
    ans+=1
    
print(min(ans,n))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

line1 = [int(x) for x in input().rstrip().split(" ")]
num_stores, limit_time = line1[0], line1[1] + 0.5

ls_stores = []
for _ in range(num_stores):
    linen = [int(x) for x in input().rstrip().split(" ")]
    ls_stores.append(linen)
    
total_time = 1
time_min = ls_stores[0][0] + ls_stores[0][1] + 1
position = 0
for i in range(num_stores):
    for x in ls_stores:
        time_temp = (x[0] * (total_time)) + x[1]
        if ls_stores[0] == x:
            time_min = time_temp
            position = 0
        elif time_temp < time_min:
            time_min = time_temp
            position = ls_stores.index(x)
    total_time += time_min
    if total_time > limit_time:
        print(i)
        break
    elif i == num_stores - 1:
        print(num_stores)
    total_time += 1
    ls_stores.pop(position)

Submission status: Wrong Answer

Solution code:
n, T = map(int, input().split())

shop = [tuple(map(int, input().split())) for i in range(n)]

heavy = [s for s in shop if s[0] != 0]
light = [s[1] + 1 for s in shop if s[0] == 0]

light.sort()

from functools import cmp_to_key

def cmp(p, q):
    (ap, bp) = p
    (aq, bq) = q
    ap += 1
    aq += 1
    return aq * bp + aq + bq < ap * bq + ap + bp

heavy = sorted(heavy, key=cmp_to_key(cmp))

dp = [1<<40] * 33
dp[0] = 0
for (a, b) in heavy:
    for i in range(32, 0, -1):
        dp[i] = min(dp[i], (dp[i-1] + 1) *  a + b)

light_cnt = 0
light_sum = 0

ans = 0
for i in range(32, -1, -1):
    if dp[i] > T:continue
    rest = T - dp[i]
    while light_cnt < len(light) and light_sum <= rest:
        light_sum += light[light_cnt]
        light_cnt += 1
    ans = max(ans, i + max(0, light_cnt-1))
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, T = map(int,  input().split())

a = [0] * N
b = [0] * N
for i in range(N):
        a[i], b[i] = map(int,  input().split())

t=0
arrived_store=[]
while t <= T:
        t+=1

        c = [[0,0]] * N
        for i in range(N):
                c[i] = [a[i] * t + b[i], i]

        c.sort()

        j=0
        while c[j][1] in arrived_store:
                j += 1

        t+=c[j][0]

        if t > T:
                break

        arrived_store.append(c[j][1])

        if (len(arrived_store) == N):
                break

print(len(arrived_store))

Submission status: Wrong Answer

Solution code:
n, t = [int(i) for i in input().split(' ')]
AB = [[int(i) for i in input().split(' ')] for j in range(n)]

def calt(t, ab):
  if ab[0]==0:
    ab[0]=1
  return int((t-ab[1])/ab[0]) - 1

ans = -1
while (t>=0) & (len(AB)>0):
  tt = max([(calt(t, ab), i) for i, ab in enumerate(AB)])
  t = tt[0]
  AB.pop(tt[1])
  ans += 1
  #print(tt, AB)

if t>=0 & len(AB)==0:
  ans+=1
  
print(ans)

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
C=[]
S=[]
for i in range(N):
    k=list(map(int,input().split()))
    C.append(k)
    S.append(i)
ans=0
l=T+0.5
#S=range(N)
while(1):
    k=0
    h=0
    for i in S:
        if(C[i][0]!=0):
            sumt=(l-C[i][1])/C[i][0]
        else:
            sumt=l-C[i][1]
        #print(sumt)
        #print(k)
        if(sumt>k):
            #print("AAA")
            k=sumt
            h=i
    #print(sumt)
    if(k<1):
        break
    #print(h)
    S.remove(h)
    ans+=1
    l=k-1
    #print(l)
print(ans)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
time = 0
ans = 0

a = []
for i in range(n):
    a.append(list(map(int,input().split())))
    
if t >= 1:
    time += 1
    
while time < t:
    cost = 10** 18
    list_n = 0
    for i in range(len(a)):
        if (a[i][0] * time + a[i][1])< cost:
            cost = (a[i][0] * time + a[i][1])       
            list_n = i
    if a:
        a.pop(list_n)        
    if time + cost > t:
        break
    else:
        time += cost
        ans += 1
            
print(ans)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())

a = []
b = []

for i in range(N):
    j,k = map(int, input().split())
    a.append(j)
    b.append(k)
    

def wait_time(t):
    min_t = 10**9
    for i in range(N):
        wt = a[i]*t + b[i]
        if wt < min_t:
            min_t = wt            
    return min_t

t = 1
count = 0

while True:
    t += wait_time(t)
    if t > T:
        break
    else:
        t += 1
        count += 1

if count > N:
    count = N

        
print(count)

Submission status: Wrong Answer

Solution code:
N, T = list(map(int, input().split()))

a, b = [0] * N, [0] * N

for i in range(N):
  a[i], b[i] = list(map(int, input().split()))

# greedfy
visited = [False] * N
t = 0
count = 0

while t < T + 0.5 and not all(visited):
  t += 1  # move
  if not t < T + 0.5:
    break
  costs = [(i * t + j, idx) for (idx, (i, j, v)) in enumerate(zip(a, b, visited)) if v == False]
  minCost, minIdx = sorted(costs)[0]
  t += minCost
  visited[minIdx] = True
  #print(minCost, minIdx, visited)
  count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    N,T = map(int,input().split())
    dp = [2**60 for _ in range(N+1)]#i店舗訪れたときの時間
    dp[0] = 0
    C = [list(map(int,input().split(" "))) for _ in range(N)]
    C.sort()
    C = deque(C)
    use = []
    for k in range(1,N+1):
        S = deque()
        while C:
            tmp = int(dp[k])
            a,b = C.popleft()
            dp[k] = min(dp[k],a*(dp[k-1]+1)+b)
            if tmp == dp[k]:
                S.append([a,b])
            else:
                if use:
                    if len(S) != 0:
                        S.pop()
                    S.append(use)
                use = [a,b]
        C = deque(S)

    ans = 0
    for i,t in enumerate(dp):
        if t == 0:
            continue
        elif 0 < t <= T+0.5:
            ans = max(ans,i)
        else:
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, t = list(map(int,input().split()))
a, b = [], []
for i in range(n):
  a1, b1 = list(map(int,input().split()))
  a.append(a1)
  b.append(b1)
  
time = 0
count = 0

while time <= t + 0.5:
  j = b.index(min(b))
  time += 1
  time1 = time
  time += a[j] * time1 + b[j]
  if time > t + 0.5:
    time -= a[j] * time1 + b[j] + 1
    break
  b[j] = max(b)
  count += 1
  
print()

Submission status: Wrong Answer

Solution code:
n, t = list(map(int,input().split()))
a, b = [], []
for i in range(n):
  a1, b1 = list(map(int,input().split()))
  a.append(a1)
  b.append(b1)
  
time = 0
count = 0

while time <= t + 0.5:
  j = b.index(min(b))
  time += 1
  time1 = time
  time += a[j] * time1 + b[j]
  if time > t + 0.5:
    time -= a[j] * time1 + b[j] + 1
    break
  a[j] = max(a)
  count += 1
  
print()

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N)]
import numpy as np

a = [0]*N
b = [0]*N

for i in range(N):
    a[i] = ab[i][0]
    b[i] = ab[i][1]
    
a = np.array(a)
b = np.array(b)

import sys

time = 0
#mintime = 10**9

for shop in range(N):
    time += 1
    go = np.argmin(a*time+b)
    #for i in range(len(ab)):
    #    t = ab[i][0]*time + ab[i][1]
    #    if t < mintime:
    #        mintime = t
    #        go = i
    #mintime = 10**9
    time = time + min(a*time+b)
    
    if time > T+0.5:
        print(shop)
        sys.exit()
    
    #a.pop(go)
    #b.pop(go)
    np.delete(a,go)
    np.delete(b,go)
    
print(shop+1)

Submission status: Wrong Answer

Solution code:
import heapq
n,t = map(int,input().split())
ab = []

for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b,a+b])
    
ab = sorted(ab,key=lambda x:x[2])

time = 0
ans = 0
for i in range(n):
    time += 1
    tmp = []
    for j in range(len(ab)):
        tmp.append([ab[j][0]*time+ab[j][1],j,ab[j][0]])
    heapq.heapify(tmp) 
    minmin = heapq.heappop(tmp)
    time += minmin[0]
    ab.remove(ab[minmin[1]])
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
info = [int(i) for i in input().split()]
w = list()
for i in range(info[0]):
    w.append([int(i) for i in input().split()])
ans = 0
t = 0
while (t <= info[1]):
    ans += 1
    if len(w) == 0:
        break
    w = sorted(w, key=lambda x:x[0]*t+x[1])
    t += w[0][0]*t+w[0][1]+1
    del w[0]
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline

INF = 10**18+3
N, T = map(int, readline().split())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
ABzero = [b for a, b in AB if a == 0]
ABnonzero = [(a, b) for a, b in AB if a]
ABnonzero.sort(key = lambda x: x[1]/x[0])


dp = [0]
for a, b in ABnonzero:
    dp2 = dp + [INF]
    for j in range(1, len(dp2)):
        dp2[j] = min(dp2[j], (dp[j-1]+1)*(a+1)+b)
    dp = [d for d in dp2 if d <= T]

ABzero.sort()
dpzero = [0] + [b+1 for b in ABzero]
for i in range(1, len(dpzero)):
    dpzero[i] += dpzero[i-1]

DP = [INF]*(N+1)
for i in range(len(dp)):
    for j in range(len(dpzero)):
        DP[i+j] = min(DP[i+j], dp[i] + dpzero[j])

DP = [d for d in DP if d <= T]
print(len(DP)-1)

Submission status: Wrong Answer

Solution code:
N, T = input().split(" ")
N = int(N)
T = int(T)
T = T+0.5
shop_list = []
for i in range(N):
    temp = input().split(" ")
    temp = list(map(int, temp))
    shop_list.append(temp)
shop_list.sort(reverse=True)

shop_max = 0
for i in range(len(shop_list)):
    now_time = 1
    shop_count = 0
    for shop in shop_list[i:]:
        now_time += shop[0]*now_time+shop[1]
        if now_time > T:
            break
        else:
            shop_count += 1
            now_time += 1
            if shop_max < shop_count:
                shop_max = shop_count
print(shop_max)

Submission status: Wrong Answer

Solution code:
def resolve():
    N, T = map(int, input().split())  
    a_list = []
    b_list = []
    a_list.append(0)
    b_list.append(0)
    for i in range(N):
        a, b = map(int, input().split())
        a_list.append(a)
        b_list.append(b)

    time = 0
    count = 0

    while True:
        time += 1
        min_time = 10**(24)
        for i in range(1, len(a_list)):
            tmp_time = a_list[i] * time + b_list[i]
            if tmp_time < min_time:
                min_time = tmp_time
                min_index = i

        if (time + min_time) < (T + 0.5):
            count += 1
            time += min_time
            a_list.pop(min_index)
            b_list.pop(min_index)
            if len(a_list) == 1:
                print(count)
                break
        else:
            print(count)
            break


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n,t=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(n):
    a[i],b[i]=map(int,input().split())
time=1
ans=0
tmp=[]
while time <= t +0.5:
    for i in range(n):
        t1=int(a[i])*time+int(b[i])
        tmp.append(t1)
    time = time + min(tmp)
    a[tmp.index(min(tmp))]=10**11
    b[tmp.index(min(tmp))]=10**11
    if time <= t+0.5:
        ans+=1
    time = time+1
    tmp=[]
print(ans)

Submission status: Wrong Answer

Solution code:
n, T = map(int, input().split())
a = []
b = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
ans = 0
tmp = 0
while True:
    n = []
    tmp += 1
    for i in range(len(a)):
        n.append(a[i]*tmp + b[i])
    tmp += min(n)
    if tmp <= T:
        ans += 1
    else:
        break
    if len(a) == 1:break
    del(a[n.index(min(n))])
    del(b[n.index(min(n))])
print(ans)

Submission status: Wrong Answer

Solution code:
n,x= input().split(" ")
t = int(x)
a = []
b = []

for i in range(int(n)):
    ka , kb = input().split(" ")
    a.append(int(ka))
    b.append(int(kb))

p = 0
cou = 0

while True:
    p += 1
    for i in range(len(a)):
        b[i] += p * a[i]
    p += min(b)
    s = b.index(min(b))
    del b[s]
    del a[s]
    if p > t:
        break
    elif b == []:
        cou += 1
        break
    cou += 1
print(cou)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
A = []
B = []
time = []

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

cnt = 0
t = 0

while (t <= T and cnt < N):
    t += 1
    time = []
    
    for i in range(len(A)):
        t_time = A[i] * t + B[i]
        time.append(t_time)
    
    t_mini = min(time)
    t_index = time.index(t_mini)
    
    
    if (t + t_mini <= T):
        cnt += 1
        A.remove(A[t_index])
        B.remove(B[t_index])
    
    t += t_mini

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline

INF = 10**18+3
N, T = map(int, readline().split())

AB = [tuple(map(int, readline().split())) for _ in range(N)]
ABzero = [b for a, b in AB if a == 0]
ABnonzero = [(a, b) for a, b in AB if a]
ABnonzero.sort(key = lambda x: (x[1]-1)/x[0])


dp = [0]
for a, b in ABnonzero:
    dp2 = dp + [INF]
    for j in range(1, len(dp2)):
        dp2[j] = min(dp2[j], (dp[j-1]+1)*(a+1)+b)
    dp = [d for d in dp2 if d <= T]

ABzero.sort()
dpzero = [0] + [b+1 for b in ABzero]
for i in range(1, len(dpzero)):
    dpzero[i] += dpzero[i-1]

DP = [INF]*(N+1)
for i in range(len(dp)):
    for j in range(len(dpzero)):
        DP[i+j] = min(DP[i+j], dp[i] + dpzero[j])

DP = [d for d in DP if d <= T]
print(len(DP)-1)

Submission status: Wrong Answer

Solution code:
n, t = list(map(int,input().split()))
a, b = [], []
for i in range(n):
  a1, b1 = list(map(int,input().split()))
  a.append(a1)
  b.append(b1)
  
time = 0
count = 0

while time <= t + 0.5:
  j = a.index(min(a))
  time += 1
  time1 = time
  time += a[j] * time1 + b[j]
  if time > t + 0.5:
    time -= a[j] * time1 + b[j] + 1
    break
  a[j] = max(a)
  count += 1
  
print()

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())

store =[]
for i in range(n):
  store.append(list(map(int, input().split())))

time = 0
cnt = 0

for i in range(n):
  time += 1
  wait_list = [store[j][0]*time + store[j][1] for j in range(len(store))]
  wait = min(wait_list)
  if time + wait <= t + 0.5:
    time += wait
    store.pop(wait_list.index(wait))
    cnt += 1
  if time + wait >= t + 0.5:
    break

print(cnt)

Submission status: Wrong Answer

Solution code:
n,t=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(key=lambda x:x[0])

def countk(k):
    global ab,n,t
    ret=0
    ab_=ab[:k][::-1]
    for i in range(k):
        ret+=1
        ret=ret+ab_[i][0]*ret+ab_[i][1]
    return ret

l,r=0,n
while l+1<r:
    k=(l+r)//2
    if countk(k)<=t:
        l=k
    else:
        r=k
#print(r)
#print(countk(r))
if countk(r)<=t:
    print(r)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
def main():
    N,T=map(int, input().split())
    a=[]
    b=[]
    MAX_COST = 10**9 + (T + 2)
    for i in range(N):
        ai,bi=map(int, input().split())
        a.append(ai)
        b.append(bi)

    if T==0:
        print(0)
        return

    t = 0
    shop = -1
    while t <= T:
        t += 1
        shop += 1
        min_i = -1
        min_cost = MAX_COST
        for i in range(N):
            cost = a[i] * t + b[i]
            if cost < min_cost:
                min_i = i
                min_cost = cost
        if min_i >= 0:
            a[min_i] = MAX_COST
            b[min_i] = MAX_COST
        t += min_cost

    print(shop)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, t = list(map(int,input().split()))
a, b = [], []
for i in range(n):
  a1, b1 = list(map(int,input().split()))
  a.append(a1)
  b.append(b1)
  
time = 0
count = 0

while time <= t + 0.5:
  j = a.index(min(a))
  time += 1
  time1 = time
  time += a[j] * time1 + b[j]
  if time > t + 0.5:
    time -= a[j] * time1 + b[j]
    break
  a[j] = max(a)
  count += 1
  
print()

Submission status: Wrong Answer

Solution code:
N, T = list(map(int, input().split()))
t, cnt = 0, 0
store = [input().split() for i in range(N)]

#print(store)
while(1):
  mini = T
  t += 1
  for i in range(len(store)):
    if (int(store[i][0])*t+int(store[i][1]) < mini):
      mini = int(store[i][0])*t+int(store[i][1])
      pur = i
  if t+mini<=T:
    cnt += 1
    t += mini
    del(store[pur])
  else:
    break

print(cnt)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
a = []
b = []
for i in range(N):
  a_,b_ = map(int, input().split())
  a.append(a_)
  b.append(b_)

ans = 0
ex = []
t = T
while True:
  t_ = -1
  a_ = 0
  idx = None
  for i in range(N):
    if not i in ex:
      if a[i] == 0:
        if t-1-b[i]  > t_:
          t_ = t-1-b[i]
          a_ = a[i]
          idx = i
      elif (t-1-b[i])//a[i] > t_:
        t_ = (t-1-b[i])//a[i]
        a_ = a[i]
        idx = i
      elif (t-1-b[i])//a[i] == t_ and a[i] > a_:
        t_ = (t-1-b[i])//a[i]
        a_ = a[i]
        idx = i
  if t_ >= 0:
    ex.append(idx)
    ans += 1
    t = t_
  else:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
P = [list(map(int,input().split()))  for i in range(N)]
t = 0
x = 0
for a, b in P:
  t += 1
  if a*t + b < T + 0.5:
    x += 1
    t += a*t + b
  else:
    t += a*t + b
    
print(x)

Submission status: Wrong Answer

Solution code:
n, T = map(int, input().split())
a = []
b = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
ans = 0
tmp = 0
n = []
while True:
    tmp += 1
    for i in range(len(a)):
        n.append(a[i]*tmp + b[i])
    tmp += min(n)
    if tmp <= T:
        ans += 1
    else:
        break
    if len(a) == 1:break
    del(a[n.index(min(n))])
    del(b[n.index(min(n))])
    n.clear()
print(ans)

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())
s = []
ans = 0
t = 1
for _ in range(N):
    a,b = map(int,input().split())
    s.append([a,b,a+b])

def judge(s,T):
    for i in range(len(s)):
        s[i][2] = s[i][0]*T+s[i][1]
    s.sort(reverse=True, key = lambda x:x[2])
    if len(s)>0:
        ans = s.pop()
        return ans[2]
    else:
        return 0
while t< T+0.5:
    p = judge(s,t)
    t = t+p
    if t >=T+0.5 or ans ==N:
        break
    else:
        ans += 1
    t += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
A = []
B = []
time = []

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

cnt = 0
t = 0

while (t <= T and cnt < N):
    t += 1
    time = []
    
    for i in range(len(A)):
        t_time = A[i] * t + B[i]
        time.append(t_time)
    
    t_mini = min(time)
    t_index = time.index(t_mini)
    
    
    if (t + t_mini <= T):
        cnt += 1
        A.remove(A[t_index])
        B.remove(B[t_index])
    
    t += t_mini

print(cnt)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
P = [list(map(int,input().split()))  for i in range(N)]
t = 0
for a, b in P:
  if a*t + b < T + 0.5:
    t += 1
print(t)

Submission status: Wrong Answer

Solution code:
n, T = map(int, input().split())
a = []
b = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
ans = 0
tmp = 0
n = []
while True:
    n.clear()
    tmp += 1
    if len(a) == 0:break
    for i in range(len(a)):
        n.append(a[i]*tmp + b[i])
    tmp += min(n)
    del(a[n.index(min(n))])
    del(b[n.index(min(n))])
    if tmp <= T:
        ans += 1
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,T= map(int,input().split())
a_list = []
b_list = []
for _ in range(N):
    a,b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)

a_list = np.array(a_list)
b_list = np.array(b_list)

t=1
ans = 0
while True:
    store = np.argmin(a_list*t+b_list)
    end_time = t + a_list[store]*t+b_list[store]

    if end_time<T+1: #買い物が時間までに終わる
        ans+=1
        a_list = np.delete(a_list,store)
        b_list = np.delete(b_list,store)
        t = end_time+1
        if len(a_list) == 0: # 全店訪れた
            print(ans)
            exit()
    else:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
N,T = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

#a=b=t=0
#A=[[a*t+b,a,b]]

A=[]
for t in range(1, N+1):
	a,b = map(int, input().split())

	A.append([a*t+b,a,b])


B = sorted(A, key=lambda x:(x[0]))

#print(A)
#print(B)


sumT=1
ans=0
#for X in range(B):

for i in range(N):
	
	t = B[i][0]
	x = 1
	x+= t
	
	if (x+sumT>T): break;
	
	sumT+=x
	
	ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,t = map(int,input().split())
ab = []

for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b,a+b])
    
ab = sorted(ab,key=lambda x:x[2])

time = 0
ans = 0
for i in range(n):
    time += 1
    tmp = deque()
    for j in range(len(ab)):
        tmp.append([ab[j][0]*time+ab[j][1],j])
    tmp = sorted(tmp)
    time += tmp[0][0]
    ab.remove(ab[tmp[0][1]])
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = []

for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b,a+b])
    
ab = sorted(ab,key=lambda x:x[2])

time = 0
ans = 0
for i in range(n):
    time += 1
    tmp = []
    for j in range(n):
        tmp.append([ab[j][0]*time+ab[j][1],j])
    tmp = sorted(tmp)
    time += tmp[0][0]
    tmp.remove(tmp[j])
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = []

for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b,a+b])
    
ab = sorted(ab,key=lambda x:x[2])

time = 0
ans = 0
for i in range(n):
    time += 1
    tmp = 10**9
    for j in range(n):
        tmp = min(ab[j][0]*time+ab[j][1],tmp)
    time += tmp
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    n, t = map(int, input().split())
    t -= 0.5
    A = np.zeros((n))
    B = np.zeros((n))
    for i in range(n):
        A[i], B[i] = map(int, input().split())

    r = 0
    now = 0
    for _ in range(n):
        T = A*now+B
        tmp = np.min(T)
        i = np.argmin(T)
        if now+tmp>t:
            break
        else:
            now += tmp+1
            r += 1
            A[i] = t
            B[i] = t
    print(r)

main()

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = []

for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b,a+b])
    
ab = sorted(ab,key=lambda x:x[2])

time = 0
ans = 0
for i in range(n):
    time += 1
    time += ab[i][0]*time+ab[i][1]
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = []

for i in range(n):
    a,b = map(int,input().split())
    ab.append([a,b,a+b])
    
ab = sorted(ab,key=lambda x:x[2])

time = 0
ans = 0
for i in range(100):
    time += 1
    time += ab[i][0]*time+ab[i][1]
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)
INF = float("inf")
dp = [[INF 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)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/hitachi2020/submissions/10704509

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))  # namedtupleやめた,coef,const

    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  # start=x->0
        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  # le->lt,continue->break,restは狭義単調減少
        while cnt > 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        ans.add(visited + cnt)
    print(max(ans))


if __name__ == '__main__':
    main()