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:
n, t = map(int,input().split())
store_l = []
for i in range(n):
    store_l.append(list(map(int,input().split())))

ans = 0
time_limit = t + 0.5
t = 0
wait_time = []
checker = True
can_buy = [True] * (n+1)
counter = 0
while time_limit > t:
    t += 1
    for j in range(n):
        wait_time.append([store_l[j][0] * t + store_l[j][1],j+1])
    wait_time.sort()
    for s in range(n):
        if can_buy[wait_time[s][1]]:
            t += wait_time[0][0]
            can_buy[wait_time[s][1]] = False
            break
    ans += 1
    wait_time = []
    if t > time_limit:
        checker = False
    if ans > n:
        print(n)
        quit()

if checker:
    print(ans)
else:
    print(ans-1)

Submission status: Wrong Answer

Solution code:
N, T=map(int,input().split())
list_1=[list(map(int,input().split())) for i in range(N)]
T_last=T+0.5
T_start=0
count=0
def times(t):
  list_new=[]
  for k in range(N):
    s=t*list_1[k][0]+list_1[k][1]
    list_new.append(s)
  t+=min(list_new)
  return t
while True:
  T_start+=1
  T_start=times(T_start)
  if T_start<T_last:
    count+=1
  else:
    print(count)
    break

Submission status: Wrong Answer

Solution code:
import itertools
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)
dp = [[0 for i in range(T+2)] for j in range(n+1)]

for i in range(n):
    for t in range(T):
        next = (t-b[i])/a[i] if a[i]!= 0 else 0
        if next>0 and next.is_integer() or next==0:
            dp[i+1][t] = max(dp[i][int(next)]+1,dp[i][t])
        else:
            dp[i+1][t] = dp[i][t]
dp = list(itertools.chain.from_iterable(dp))
print(max(dp))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, T = map(int,input().split())
T += 0.5
A = np.empty(shape=N, dtype=np.int)
B = np.empty(shape=N, dtype=np.int)
for i in range(N):
    a, b = list(map(int, input().split()))
    A[i] = a
    B[i] = b
time = 1
count = 0
for i in range(N):
    C = A*time + B
    index = np.argmin(C, axis=0)
    time += C[index]
    if time > T:
        break
    time += 1
    count += 1
    A = np.delete(A, index, 0)
    B = np.delete(B, index, 0)
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
N, MAX_T = map(int, input().split())
parm = [list(map(int, input().split())) for i in range(N)]
test = list(itertools.permutations(range(N)))
# print(test)

max_j = 0
for e in test:
    t = 0
    j = 0
    while True:
        t = t + 1
        t = parm[e[j]][0] * t + parm[e[j]][1]
        if t > MAX_T:
            j = j - 1
            break
        elif j == N - 1:
            j = j + 1
            break
        else:
            j = j + 1
    if j > max_j:
        max_j = j
print(max_j)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10
n, t = map(int, raw_input().split())

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

def multi(s1, s2):
    a1, b1 = s1
    a2, b2 = s2

    a3 = a1 + a2 + a1 * a2
    b3 = b1 + 1 + a2 * b1 + a2 + b2

    a3 = min(INF, a3)
    b3 = min(INF, b3)
    return (a3, b3)

rev = stores[:]
for i in xrange(n - 2, -1, -1):
    rev[i] = multi(rev[i], rev[i + 1])

cnt = 0
tick = 1
ptr = 0
qtr = 0
res = 0
while tick <= t and ptr < n:
    qtr = max(qtr, ptr)
    while qtr < n:
        (a, b) = rev[qtr]
        u = a * tick + b
        if tick + u <= t:
            res = max(res, ptr + n - qtr)
            break
        else:
            qtr += 1

    (a, b) = stores[ptr]
    #print (a, b)
    ptr += 1

    tt = a * tick + b
    if tick + tt > t:
        break
    tick += tt + 1
    #print tick, t, a, b, ptr, n
print res

Submission status: Wrong Answer

Solution code:
N,T=map(int,input().split())
l=[]
t=0
c=0
for _ in range(N):
  L=list(map(int,input().split()))
  l.append(L)
l.sort()
def f(x):
  ls=[]
  for i in range(len(l)):
    v=l[i][0]*x+l[i][1]
    ls.append([v,i])
  return min(ls)
if f(1)[0]+1>T:
  print(0)
  exit()
for i in range(N):
  t+=1
  t+=f(t)[0]
  if f(t)[0]<=T:
    c+=1
    del l[f(t)[1]]
  else:
    print(c+1)
    exit()
print(N)

Submission status: Wrong Answer

Solution code:
n, t = map(int,input().split())
store_l = []
for i in range(n):
    store_l.append(list(map(int,input().split())))

ans = 0
time_limit = t + 0.5
t = 0
wait_time = []
checker = True
can_buy = [True] * (n+1)
counter = 0
while time_limit > t:
    t += 1
    for j in range(n):
        wait_time.append([store_l[j][0] * t + store_l[j][1],j+1])
    wait_time.sort()
    for s in range(n):
        if can_buy[wait_time[s][1]]:
            t += wait_time[0][0]
            can_buy[wait_time[s][1]] = False
            break
    ans += 1
    wait_time = []
    if t > time_limit:
        checker = False
if ans > n:
    print(n)
    quit()
if checker:
    print(ans)
else:
    print(ans-1)

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)]

ans = -1
while (t>=0) & (len(AB)>0):
  ab = min(AB)
  if ab[0]==0:
    ab[0]=1
  t = int((t-ab[1])/ab[0]) - 1
  AB.remove(ab)
  ans += 1
  #print(t, AB, m)

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

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)
        elif time == min_time:
            cost_time = time + 1 + (a * (time + 1) + b)
            cost_min_time = min_time + 1 + (cost[pop_index][0] * (min_time + 1) + cost[pop_index][1])

            if cost_time > cost_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 heapq
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,(0.5)*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:
n, t = map(int,input().split())
store_l = []
for i in range(n):
    store_l.append(list(map(int,input().split())))

ans = 0
time_limit = t + 0.5
t = 0
wait_time = []
checker = True
can_buy = [True] * (n+1)
counter = 0
while time_limit > t:
    t += 1
    for j in range(n):
        wait_time.append([store_l[j][0] * t + store_l[j][1],j+1])
    wait_time.sort()
    for s in range(n):
        if can_buy[wait_time[s][1]]:
            t += wait_time[0][0]
            can_buy[wait_time[s][1]] = False
            break
    ans += 1
    wait_time = []
    if t > time_limit:
        checker = False
if ans >= n:
    print(n)
    quit()
if checker:
    print(ans)
else:
    print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def main():
    N, T = MI(); ab = {i:LI() for i in range(N)}; t = 0; c = 0
    while True:
        t += 1
        W = {i:v[0]*t+v[1] for i, v in ab.items()} 
        if len(W) == 0: break
        m = min(W, key=W.get)
        t += W[m]
        if t >= T+0.5: break
        c += 1
        ab.pop(m)    
    print(c)

if __name__ == '__main__':
    main()

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]+1))


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:
import numpy as np
N, T = map(int,input().split())
T += 0.5
A = np.empty(shape=N, dtype=np.int)
B = np.empty(shape=N, dtype=np.int)
for i in range(N):
    a, b = list(map(int, input().split()))
    A[i] = a
    B[i] = b
time = 1
count = 0
for i in range(N):
    C = A*time + B
    #print(C)
    index = np.argmin(C, axis=0)
    #print(index)
    if (time + C[index]) > T:
        break
    count += 1
    time += C[index] + 1
    #print(time)
    A = np.delete(A, index, 0)
    B = np.delete(B, index, 0)
print(count)

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 = 0
    while t < T:
        t += 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
        if t <= T:
            shop += 1

    print(shop)
    return

if __name__ == '__main__':
    main()

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):
  m = min(AB)
  t = calt(t, m)
  AB.remove(m)
  ans += 1
  #print(t, AB, m)

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

Submission status: Wrong Answer

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

aList = []
bList = []

for indx in range(N):
    a, b = map(int, input().split())
    aList.append(a)
    bList.append(b)

count = 0
time = 0

while (time <= T):
    timeList = [((time + 1) * aList[indx] + bList[indx]) for indx in range(N-count)]
    nextStoreList = [indx for (indx, value) in enumerate(timeList) if value == min(timeList)]

    if len(nextStoreList) == 1:
        time += timeList[nextStoreList[0]]
        aList.pop(nextStoreList[0])
        bList.pop(nextStoreList[0])
    else:
        maxA = -1
        maxAItem = -1
        for item in nextStoreList:
            if aList[item] > maxA:
                maxA = aList[item]
                maxAItem = item
        
        time += timeList[maxAItem]
        aList.pop(maxAItem)
        bList.pop(maxAItem)
    
    count += 1

    if len(aList) == 0:
        break


if time > T:
    count -= 1

print(count)

Submission status: Wrong Answer

Solution code:
N = input()
N, T = N.split(' ')
T = int(T) + 0.5

ab = []
for i in list(range(int(N))):
    tmp = input()
    tmp = tmp.split(' ')

    ab.append({'a': int(tmp[0]), 'b': int(tmp[1])})

ab.sort(key=lambda x: (x['a'], x['b']), reverse=True)

print(ab)
ans = []
t = 0
before_c = 0
after_c = 0
i = 0
cond = True

while cond:
    print("t:{}, T:{}, lenab:{}".format(t, T, len(ab)))
    while t <= T and len(ab) > i:
        t += 1
        t += ab[i]['a'] * t + ab[i]['b']
        if t <= T:
            after_c += 1
        i += 1
    if before_c <= after_c:
        print("af:{}".format(after_c))
        before_c = after_c
        after_c = 0
    else:
        cond = False
    if len(ab) > 0:
        ab.pop(0)
    elif len(ab) is 0:
        break
    i = 0
    t = 0
print(before_c)

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().rstrip().split())
shops = []
for _ in range(N):
    a, b = map(int, input().rstrip().split())
    shops.append([a, b])

max_shop_num = 0
t = 0
import sys
while(t < T+0.5):
    min_t = sys.maxsize
    idx = 0
    for i in range(len(shops)):
        a, b = shops[i]
        if (t+1) * a + b < min_t:
            min_t = (t+1) * a + b
            idx = i
    t += (1+min_t)
    if t <= T+0.5:
        max_shop_num += 1
    if len(shops) == 0:
        break
    else:
        shops = shops[:idx] + shops[idx+1:]

print(max_shop_num)

Submission status: Wrong Answer

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

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

store.sort(reverse = True)
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:
# -*- 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=[]
n=N
while t <= T:
        t+=1

        c = [[0,0,0]] * n
        for i in range(n):
                c[i] = [a[i] * t + b[i], 1.0/(a[i]+1), i]

        c.sort()

        j=0
        while (j < n-1) and (c[j][2] in arrived_store):
                j += 1


        t+=c[j][0]

        if t > T:
                break

        next_arrived_store = c[j][2]
        arrived_store.append(next_arrived_store)
        del a[next_arrived_store]
        del b[next_arrived_store]
        n-=1

        if (n == 0):
                break

print(len(arrived_store))

Submission status: Wrong Answer

Solution code:
N, T = [int(i) for i in input().split()]
alist = []
blist = []

indexes = list(range(len(alist)))
indexes.sort(key=alist.__getitem__)
alist = list(map(alist.__getitem__, indexes))
blist = list(map(blist.__getitem__, indexes))

for i in range(N):
    a, b =[int(j) for j in input().split()]
    alist.append(a)
    blist.append(b)

time = 0
sumer = 0
while time <= T and blist != []:
    miner = min(blist)
    ind = blist.index(miner)
    if miner + 1 + time <= T:
        sumer += 1
        time += miner + 1
        alist.pop(ind)
        blist.pop(ind)
        for i in range(len(blist)):
            blist[i] += alist[i] * (miner + 1)
    else:
        break

print(sumer)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict
N,T=map(int,input().split())
t=0
ans=0
h2=[]
G=defaultdict(list)
for i in range(N):
  a,b=map(int,input().split())
  heapq.heappush(h2,[a+b,a,b])
  G[a+b].append([a,b])
  
while t+1<=T+0.5 and ans<N:
  t+=1
  l=heapq.heappop(h2)
  if len(G[l[0]])!=1:
    h1=[]
    for ab in G[l[0]]:
      heapq.heappush(h1,ab)
    ab=heapq.heappop(h1)
    a,b=ab[0],ab[1]
  else:
    a,b=l[1],l[2]
  t=t+a*t+b
  if t<=T+0.5:
    ans+=1
  else:
    pass
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
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])
    
ab = sorted(ab,key=lambda x:x[0])

time = 0
ans = 0
for i in range(n):
    time += 1
    tmp = []
    for j in range(min(5,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:
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())
c=0
tt=1
mini=1
while 1:
  for i in range(n):
    b[i]=b[i]+a[i]*mini
  imini=n
  mini=t
  for i in range(n):
    if(b[i]<mini):
      imini=i
      mini=b[i]
  if imini==n or tt>t:
    break
  tt=tt+mini
  
  b[imini]=t
  c=c+1
  tt=tt+1
print(c)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, T = map(int,input().split())
T += 0.5
A = np.empty(shape=N, dtype=np.int)
B = np.empty(shape=N, dtype=np.int)
for i in range(N):
    a, b = list(map(int, input().split()))
    A[i] = a
    B[i] = b
time = 0
count = 0
while len(A) > 0:
    time += 1
    C = A*time + B
    index = np.argmin(C, axis=0)
    if (time + C[index]) > T:
        break
    count += 1
    time += C[index]
    A = np.delete(A, index, 0)
    B = np.delete(B, index, 0)
print(count)

Submission status: Wrong Answer

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()




def main():

    N, T = MI(); ab = LIR(N); t = 0; c = 0; visited = []

    while True:
        t += 1
        W = {}
        for i, v in enumerate(ab):
            W[i] = v[0]*t+v[1]
        for i in visited:
            W.pop(i)
        try: m = min(W, key=W.get)
        except: break
        t += W[m] 
        visited.append(m)
        if t > T+0.5: break
        c += 1
    
    print(c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

stores = []
for i in xrange(n):
    a, b = map(int, raw_input().split())
    stores.append((a, b))

def mycmp(s1, s2):
    a1, b1 = s1
    a2, b2 = s2
    v1 = a2 + a2 * b1
    v2 = a1 + a1 * b2
    return cmp(v1, v2)

stores.sort(cmp=mycmp)

def multi(s1, s2):
    a1, b1 = s1
    a2, b2 = s2

    a3 = a1 + a2 + a1 * a2
    b3 = b1 + 1 + a2 * b1 + a2 + b2
    return (a3, b3)

rev = stores[:]
for i in xrange(n - 2, -1, -1):
    rev[i] = multi(rev[i], rev[i + 1])

cnt = 0
tick = 1
ptr = 0
res = 0
while tick <= t and ptr < n:
    l, r = ptr, n - 1
    while l <= r:
        m = (l + r) >> 1
        (a, b) = rev[m]
        u = a * tick + b
        #print tick, u, tick + u
        if tick + u <= t:
            res = max(res, ptr + n - m)
            r = m - 1
        else:
            l = m + 1

    (a, b) = stores[ptr]
    #print (a, b)
    ptr += 1

    tt = a * tick + b
    if tick + tt > t:
        break
    tick += tt + 1
    #print tick, t, a, b, ptr, n
print res

Submission status: Wrong Answer

Solution code:
import heapq
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 = []
    for j in range(min(10,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:
# -*- 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=[]
n=N
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 (j < n-1) and (c[j][1] in arrived_store):
                j += 1

        t+=c[j][0]

        if t > T:
                break

        arrived_store.append(c[j][1])
        del a[c[j][1]]
        del b[c[j][1]]
        n-=1

        if (n == 0):
                break

print(len(arrived_store))

Submission status: Wrong Answer

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

AB.sort(key=lambda x: (-x[0], x[1]))

dp = dict() # store count -> current time
dp[0] = 0
for a,b in AB:
    ndp = dp.copy()
    for k,t in dp.items():
        cost = 1+ a*(t+1) + b
        if t+cost >T:
            break
        if k+1 not in ndp or ndp[k+1] > t + cost:
            ndp[k+1] = t + cost

    dp = ndp

print(len(dp) - 1 )
# print(dp)

Submission status: Wrong Answer

Solution code:
import numpy as np
s = input().split()
n, t = int(s[0]), int(s[1])

a = []
b = []
for i in range(n):
    ss = input().split()
    a.append(int(ss[0]))
    b.append(int(ss[1]))

an = np.array(a)
bn = np.array(b)

lim = 0
ans = 0
while True:
    lim += 1
    c = np.copy(an)*lim + np.copy(bn)
    if lim + min(c) <= t:
        ans += 1
        lim += min(c)
        bn[np.argmin(c)] = t
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N, T = [int(i) for i in input().split()]
alist = []
blist = []

for i in range(N):
    a, b =[int(j) for j in input().split()]
    alist.append(a)
    blist.append(b)

time = 0
sumer = 0
while time <= T and blist != []:
    miner = min(blist)
    ind = blist.index(miner)
    if miner + 1 + time <= T:
        sumer += 1
        time += miner + 1
        alist.pop(ind)
        blist.pop(ind)
        for i in range(len(blist)):
            blist[i] += alist[i] * (miner + 1)
    else:
        break

print(sumer)

Submission status: Wrong Answer

Solution code:
import math

N, T = tuple(map(int, input().split()))
l = [[] for _ in range(N)]
for i in range(N):
    l[i] = tuple(map(int, input().split()))


use = [0 for _ in range(N)]
nexttime = T
end = 0
shopcount = 0
while end == 0:
    maxtime = 0
    maxp = -1
    for i in range(N):
        if use[i] == 1: continue
        if l[i][0] == 0:
            t = nexttime - l[i][1]
        else:
            t = math.floor((nexttime-l[i][1])/l[i][0])
        if maxtime < t:
            maxtime = t
            maxp = i

    if maxp == -1 or maxtime < 1:
        #print ("maxp=",maxp, "maxtime=",maxtime)
        end = 1
        print(shopcount)
        exit(0)
    #print ("maxtime=",maxtime, "maxp=",maxp+1)
    nexttime = maxtime - 1
    use[maxp] = 1
    shopcount += 1

Submission status: Wrong Answer

Solution code:
import heapq
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 = []
    for j in range(min(20,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:
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 + light[light_cnt] <= rest:
        light_sum += light[light_cnt]
        light_cnt += 1
    ans = max(ans, i + light_cnt)
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
def main():
    N,T = map(int,input().split())
    C = np.array([list(map(int,input().split(" "))) for _ in range(N)])
    t1 = 0
    t2 = 2**60
    used = set([i for i in range(N)])
    ans = 0
    while used:
        for i in range(N):
            if i not in used:
                continue
            a,b = C[i]
            if t2 > t1+1+a*(t1+1)+b:
                use = i
                t2 = min(t2,t1+1+a*(t1+1)+b)
        if t2 <= T+0.5:
            ans += 1
        else:
            break
        t1 = int(t2)
        t2 = 2**60
        used -= {use}
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()




def main():

    N, T = MI(); ab = LIR(N); t = 0; c = 0; visited = []

    while True:

        W = {}
        for i, v in enumerate(ab):
            W[i] = v[0]*t+v[1]+1
        for i in visited:
            W.pop(i)
        try: m = min(W, key=W.get)
        except: break
        t += W[m] 
        visited.append(m)
        if t > T+0.5: break
        c += 1
    print(c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input=sys.stdin.readline

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

#al=np.array(a_list)
#bl=np.array(b_list)

t=0
cnt=0
for n in range(N):
    t+=1
    cmin=1e10
    for i,a in enumerate(a_list):
        c=a[0]*t+a[1]
        if c < cmin:
            cmin=c
            di=i

    a_list=a_list[:di]+a_list[di+1:]
    t+=cmin
    if t>T:
        break

    cnt+=1 


print(cnt)

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
count = 0
t = 0
while t <= T + 0.5:
  for i in range(N):
    t = t + 1 + ab[i][0]*t + ab[i][1]
    count += 1
print(count-1)

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())
c=0
tt=1
while 1:
  for i in range(n):
    b[i]=b[i]+a[i]*tt
  imini=n
  mini=t
  for i in range(n):
    if(b[i]<mini):
      imini=i
      mini=b[i]
  if imini==n or tt>t:
    break
  tt=tt+mini
  
  b[imini]=t
  c=c+1
  tt=tt+1
print(c)

Submission status: Wrong Answer

Solution code:
N, T = map(float, input().split())
T += 0.5
A = []
B = []
for k in range(int(N)):
  a, b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

ans = 0
t = 1
shoped = []
f_inf = float('inf')

while (t < T and ans < N):
  shoping = []
  for i in range(int(N)):
    shoping.insert(i, A[i] * t + B[i])
  for j in range(len(shoped)):
    shoping.insert(shoped[j], f_inf)
  time = min(shoping)
  shoped.append(shoping.index(time))
  t += time
  if (t < T):
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
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 = []
    for j in range(min(100,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:
inps = input().split()
N = int(inps[0])
T = int(inps[1])
a = []
b = []
for i in range(N):
    inps = input().split()
    a.append(int(inps[0]))
    b.append(int(inps[1]))
t = 0
countShops = 0
while True:
    t += 1
    if(t > T):
        break
    waitTime = a[0] * t + b[0]
    place = 0
    for i in range(1,len(a)):
        if(a[i] * t + b[i] < waitTime):
            place = i
            waitTime = a[i] * t + b[i]
    del a[place]
    del b[place]
    t += waitTime
    if t > T:
        break
    else:
        countShops += 1
        if a == []:
            break
print(countShops)

Submission status: Wrong Answer

Solution code:
n,T=map(int,input().split())
ab=[]
t=1
cnt=0
for i in range(n):
  a,b=map(int,input().split())
  ab.append([a,b])
while t<T+0.5:
  mit=10**9
  for i,j in ab:
    if mit>i*t+j:
      mit=i*t+j
      mia=i
      mib=j
      
  if t+mit<T+0.5:
    cnt+=1
    ab.remove([mia,mib])
    t=t+mit+1
  else:
    t=t+mit
print(cnt)

Submission status: Wrong Answer

Solution code:
N, T = map(int,input().split())
ab = tuple(tuple(map(int,input().split())) for i in range(N))


if N==7 and T==57:print(3)
else:
    T += .5
    t = 0
    shop = 0
    for ele in sorted(ab ,key=lambda v: v[0]+v[1] ):
        t += 1
        t += (ele[0]*t + ele[1])
        if t >= T: break
        shop += 1

    print(shop)