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:
import numpy as np

def main():
    N,T = map(int,input().split())
    C = [[0,0,0] for _ in range(N)]
    ans = 0
    for i in range(N):
        a,b = map(int,input().split(" "))
        c = a/(b+1)
        C[i] = [c,a,b]
    C.sort()
    C = np.array(C)
    t1 = 0
    t2 = float('inf')
    for _ in range(28):
        for i in range(N):
            if C[i][1] == 0:
                continue
            else:
                t2 = min(t2,(a+1)*(t1+1)+b)
        if t2 <= T+0.5:
            ans += 1
            t1 = int(t2)
            t2 = float('inf')
        else:break
    tmp = 0
    a = 0
    for i in range(N):
        if C[i][1] != 0:
            break
        else:
            tmp += (C[i][2]+1)
            if tmp <= T+0.5:
                a += 1
    print(max(ans,a))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

#D
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())
# print("a",a,"b",b)

shop=0
time=1
x=list(range(n))
while time<T+0.5:
    # print(x)
    #時間を取得(残り店n-1)最小時間を求める
    mint=a[x[0]]*time+b[x[0]]
    popi=0
    # print(time)
    for i in range(len(x)):
        t=a[x[i]]*time+b[x[i]]
        # print(x[i],t,mint)
        if mint>t:
            # print("t",i)
            popi=i
            mint=t
    time+=mint+1
    x.pop(popi)
    shop+=1
    # print("a",a,"b",b)
    if not x:
        break
    n-=1

print(shop)

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
if N > 28:
    N = 28
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 sys


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

    n, t = map(int, input().split())
    maplist = [list(map(int, input().split())) for _ in range(n)]

    _time = 0
    count = 0
    heiten = t + 0.5
    while _time < heiten:
        _time += 1
        tmp = _time
        min_time = maplist[0][0] * _time + maplist[0][1]
        del_list = 0
        for i, m in enumerate(maplist):
            _t = m[0] * _time + m[1]
            if min_time > _t:
                min_time = _t
                del_list = i
        maplist.pop(del_list)
        _time += min_time
        count += 1
        
        if count == n:
          break
        
    if heiten < _time:
        print(count - 1)
    else:
        print(count)

if __name__ == '__main__':
    main()

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, i, idx) for (idx, (i, j, v)) in enumerate(zip(a, b, visited)) if v == False]
  minCost, _, minIdx = sorted(costs)[0]
  t += minCost
  if not t < T + 0.5:
    break
  visited[minIdx] = True
  #print(minCost, minIdx, visited)
  count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n,t = (int(x) for x in input().split())
a_list,b_list = [],[]
for _ in range(n):
  a,b = (int(x) for x in input().split())
  a_list.append(a)
  b_list.append(b)

def next(time,visited):
  if time > t:
    return len(visited) - 1
  
  max_num = 0 
  for i in range(n):
    if i in visited:
      continue
    else:
      visited.append(i)
      time += 1
      v = (a_list[i])*(time) + b_list[i]
      time += (a_list[i])*(time) + b_list[i]
      num = next(time,visited)
      if num > max_num:
        max_num = num
      time += -1 - v
      visited.remove(i)
  return max_num
  
res = 0 
for i in range(n):
  time = 0
  visited = []
  visited.append(i)
  time += 1
  time += (a_list[i])*(time) + b_list[i]
  num = next(time,visited)
  if num > res:
    res = num
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, T = map(int, input().split())
AB = np.array([input().split() for _ in range(N)], dtype=np.int64)
A, B = AB.T
A += 1


seen = []


def C(t):
    tmp = (t - B) // A
    x = np.argmax(tmp)
    return max(0, tmp[x])


ans = 0
while True:
    T = C(T)
    if T > 0:
        ans += 1
        continue
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n,t = (int(x) for x in input().split())
a_list,b_list = [],[]
for _ in range(n):
  a,b = (int(x) for x in input().split())
  a_list.append(a)
  b_list.append(b)

def next(time,visited):
  if time > t:
    return len(visited) - 1
  
  max_num = 0 
  for i in range(n):
    if i in visited:
      continue
    else:
      visited.append(i)
      v = (a_list[i])*(time) + b_list[i]
      time += 1
      time += (a_list[i])*(time) + b_list[i]
      num = next(time,visited)
      if num > max_num:
        max_num = num
      time += -1 - v
      visited.remove(i)
  return max_num
  
res = 0 
for i in range(n):
  time = 0
  visited = []
  visited.append(i)
  time += 1
  time += (a_list[i])*(time) + b_list[i]
  num = next(time,visited)
  if num > res:
    res = num
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)

def chkonly(tm, T, N, a, b):
    cnt=0
    i=0
    mise=0
    while i<N:
        if tm+a[i]*tm+b[i]<=T:
            if cnt==0:
                cnt=1
                mise=i
            else:
                break
        i+=1
    return (mise,True) if cnt==1 else (mise,False)

def getmise(T, N, a, b):
    ok=0
    ng=T
    while ng-ok>1:
        mid=(ok+ng)//2
        mise,flag=chkonly(mid, T, N, a, b)
        if flag:
            ok=mid
        else:
            ng=mid
    return ok,mise

def solve(N, T, a, b):
    ans=0
    limit=T
    while limit>0:
        ok,mise=getmise(T, N, a, b)
        if limit==ok:
            break
        if ok>=1:
            ans+=1
            limit=ok
            a[mise]=2**31-1
            b[mise]=2**31-1
            #print(ans,limit,mise,a,b)
        else:
            break
    print(ans-1)



# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, T, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
n,T=map(int,input().split())
ab=[]
a0=[-1]
for _ in range(n):
    a,b=map(int,input().split())
    if a==0:
        a0.append(b)
    else:
        ab.append([a,b])
a0.sort()
a0_l=len(a0)
for i in range(a0_l-1):
    a0[i+1]+=a0[i]+1
ab.sort()
ab_l=len(ab)
ab_used=[0]*ab_l
ab_memo=[1]
t=1
while t<=T+2:
    w=-1
    m=float("INF")
    for i in range(ab_l):
        if ab_used[i]==0 and (w==-1 or ab[i][0]*t+ab[i][1]<=m):
            w=i
            m=ab[i][0]*t+ab[i][1]
    if w==-1:
        break
    else:
        t+=m+1
        ab_memo.append(t)
        ab_used[w]=1
ans=0
for i in range(a0_l):
    ans_=i+bisect.bisect_right(ab_memo,T-a0[i])-1
    ans=max(ans,ans_)
print(ans)

Submission status: Wrong Answer

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

def main():
    n,t=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(n)]
    L.sort()
    ans=0
    T=t+0.5
    while T>=0:
        chk=0
        dn=-1
        for i,a in enumerate(L):
            if chk>(T-a[1])/(1+a[0]):
                continue
            else:
                chk=(T-a[1])/(1+a[0])
                dn=i
        if dn==-1:
            break
        else:
            del L[dn]
            T=T-chk-1
            ans+=1
    if T<0:
        print(ans-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, T = map(int, input().split())
A = []
for i in range(n):
    a, b = map(int, input().split())
    mi = max(0, int((T-b)/max(a, 1) - 1))
    A.append([a, b, mi, a*mi+b])
A = sorted(A)
cnt = 0
ans = 0
for i in range(n):
    cnt += 1
    minx = 10**20
    for j in range(n):
        if A[j][0]*cnt + A[j][1] < minx:
            minx = A[j][0]*cnt + A[j][1]
        else:
            break
    if cnt + minx <= T + 0.5:
        ans += 1
        cnt += minx
    else:
        break
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 = float('inf')
    loop = set([i for i in range(N)])
    ans = 0
    while loop:
        for v in loop:
            a,b = C[v]
            if t2 > (a+1)*(t1+1)+b:
                use = {v}
                t2 = (a+1)*(t1+1)+b
        if t2 > T+0.5:
            break
        ans += 1
        t1 = int(t2)
        t2 = float('inf')
        loop -= use
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ある店から最短で買えるもの
def min_store(t, s_i, ab, N):  # 現在の時刻, お店, お店リスト, お店数
    if N == 1:
        min_t = ab[0][0] * t + ab[0][1] + 1
        buy_j = 1
    elif s_i + 1 == N:
        min_t = ab[s_i - 1][0] * t + ab[s_i - 1][1] + 1  # s_iから一つ移動したお店での購入時間
        buy_j = s_i-1
    else:
        min_t = ab[s_i+1][0] * t + ab[s_i+1][1] + 1  # s_iから一つ移動したお店での購入時間
        buy_j = s_i+1
    t += 1
    for j in range(1, N):
        if t != 0:
            if ab[j][0] * t + ab[j][1] + 1 < min_t:
                min_t = ab[j][0] * t + ab[j][1] + t
                buy_j = j
        else:
            pass
    next_t = min_t
    return next_t, buy_j  # 購入後の時間, 買えたお店


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

# print(ab[1])
# print(ab[0][0])
buy = 0
t = 0
s_i = 0

# 最初の最小値
# min_t = ab[0][0] * 1 + ab[0][1] + 1
#print(min_store(0, 0, ab, N))

while t < T+0.5:
    next_t, buy_j = min_store(t, s_i, ab, N)
    print(next_t, buy_j)
    t += next_t
    s_i = buy_j
    buy += 1
    #print(t, s_i)
buy -= 1
print(buy)
#t += min_t
# if t <= T:
#    buy += 1
# else:
#    print(buy)

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:
    t -= int((t-ab[1])) - 1
  else:
    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:
import sys
sys.setrecursionlimit(50001)
def getint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
def merge(a):
    numb = len(a)
    if numb > 1:
        le = merge(a[:int(numb/2)])
        ri = merge(a[int(numb/2):])
        ar = []
        while len(le) > 0 and len(ri) > 0:
            if le[0] < ri[0]:
                ar.append(le.pop(0))
            else:
                ar.append(ri.pop(0))
        if len(le) != 0:
            ar.extend(le)
        else:
            ar.extend(ri)
        return ar
    else:
        return a
    
def main(needa,needb,shops,remain,now,serch):
    ans = len(serch)
    if len(serch) != 0:
        for i in range(shops-serch[-1]-1):
            nex = i+1+serch[-1]
            ext = now*needa[nex]+needb[nex]+1
            remain_nx = remain-ext
            now_nx = now+ext
            p = []
            p.extend(serch)
            p.append(nex)
            
            q = 0
            if remain_nx > 0:
                q = main(needa,needb,shops,remain_nx,now_nx,p)
            if q > ans:
                ans = q
    else:
        for i in range(shops):
            nex = i
            ext = now*needa[nex]+needb[nex]+1
            remain_nx = remain-ext
            now_nx = now+ext
            p = []
            p.extend(serch)
            p.append(nex)
            if remain_nx < 0:
                q = len(serch)-1
            else:
                q = main(needa,needb,shops,remain_nx,now_nx,p)
            if q > ans:
                ans = q
    return ans
        


def output():
    shops,close = getint()
    close = close + 0.5
    needa = []
    needb = []
    for i in range(shops):
        l = getint()
        needa.append(l[0])
        needb.append(l[1])
    needa = merge(needa)
    ans = main(needa,needb,shops,close,0,[])
    return ans
print(output())

Submission status: Wrong Answer

Solution code:
n,t = (int(x) for x in input().split())
a_list,b_list = [],[]
for _ in range(n):
  a,b = (int(x) for x in input().split())
  a_list.append(a)
  b_list.append(b)

def next(time,visited):
  if time > t:
    return len(visited) - 1
  
  max_num = 0 
  for i in range(n):
    if i in visited:
      continue
    else:
      visited.append(i)
      time += 1
      time += (a_list[i])*(time) + b_list[i]
      num = next(time,visited)
      if num > max_num:
        max_num = num
      visited.remove(i)
  return max_num
  
res = 0 
for i in range(n):
  time = 0
  visited = []
  visited.append(i)
  time += 1
  time += (a_list[i])*(time) + b_list[i]
  num = next(time,visited)
  if num > res:
    res = num
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ti=0
count=0

while ti+1<T+0.5 and len(a)>0:
    ti=ti+1
    ind=np.argmin(a*ti+b)
    mins=a[ind]*ti+b[ind]
    if ti+mins<T+0.5:
        count=count+1
        ti=ti+mins
    else:
        ti=ti-1

    if len(a)>0:
        a=np.delete(a,ind)
        b=np.delete(b,ind)
    else:
        ti=T+0.5
print(count)

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,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 c[j][2] in arrived_store:
                j += 1

        t+=c[j][0]

        if t > T:
                break

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

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

print(len(arrived_store))

Submission status: Wrong Answer

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

def main():
    n,t=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(n)]
    L.sort()
    ans=0
    T=t+0.5
    while T>=0:
        chk=0
        dn=-1
        for i,a in enumerate(L):
            if chk>(T-a[1])/(1+a[0]):
                continue
            else:
                chk=(T-a[1])/(1+a[0])
                dn=i
        if dn==-1:
            break
        else:
            del L[dn]
            T=T-chk-1
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
n,T=map(int,input().split())
ab=[]
a0=[-1]
for _ in range(n):
    a,b=map(int,input().split())
    if a==0:
        a0.append(b)
    else:
        ab.append([a,b])
a0.sort()
a0_l=len(a0)
for i in range(a0_l-1):
    a0[i+1]+=a0[i]+1
ab.sort()
ab_l=len(ab)
ab_used=[0]*ab_l
ab_memo=[1]
t=1
while t<=T:
    w=-1
    m=float("INF")
    for i in range(ab_l):
        if ab_used[i]==0 and (w==-1 or ab[i][0]*t+ab[i][1]<=m):
            w=i
            m=ab[i][0]*t+ab[i][1]
    if w==-1:
        break
    else:
        t+=m+1
        ab_memo.append(t)
        ab_used[w]=1
ans=0
for i in range(a0_l):
    ans_=i+bisect.bisect_right(ab_memo,T-a0[i])-1
    ans=max(ans,ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

def get_limit_time(a, b, t):
    return (t - b) // (a + 1)

N, T = map(int, input().split())
shop_list = []
max_limit = -1 * 10 ** 10
max_index = 10 * 10
max_a = 10 * 10
for i in range(N):
    a, b = map(int, input().split())
    limit_time = get_limit_time(a, b, T)
    if max_limit < limit_time and a < max_a:
        max_limit = limit_time
        max_index = i
    shop_list.append([a, b, limit_time])

ans = 0
shop_num = N
for i in range(N):
    T = max_limit - 1
    shop_list.pop(max_index)
    shop_num -= 1
    if T < 1:
        if T == 0:
            ans += 1
        break
    ans += 1
    max_limit = -1 * 10 ** 10
    for j in range(shop_num):
        shop = shop_list[j]
        limit_time = get_limit_time(shop[0], shop[1], T)
        if max_limit < limit_time and shop[0] < max_a:
            max_limit = limit_time
            max_index = j

print(ans)

Submission status: Wrong Answer

Solution code:
a, T  = map(int,input().split(" "))
ai = [0] * a 
bi = [0] * a 
time = 0
count = 0
for i in range(a):
    x, y = map(int,input().split(" "))

    ai[i] = x
    bi[i] = y

while time < T+0.5 and count < a:
    time += 1
    lowest = 99999999999
    for i in range(len(ai)):
        if lowest > ai[i] * time +bi[i]:
            lowest = ai[i] * time +bi[i]
            index = i
    ai.pop(index)
    bi.pop(index)
    time = time + lowest
    if time <= T+0.5:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n, t = list(map(int, input().split()))
max_time = float(t) + 0.5
shops = {}
for i in range(1, n+1):
  shops[i] = list(map(int, input().split()))
times = []
for i in shops:
  times.append(i * shops[i][0] + shops[i][1])
times = sorted(times)
count = 0
total = 0
for i in times:
  total += 1 + i
  if max_time < total:
    break
  else:
    count += 1
print(count)

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 = 1

while (time <= T):
    timeList = [(time * 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:
        nextStore = nextStoreList[0]
    else:
        maxA = -1
        maxAItem = -1
        for item in nextStoreList:
            if aList[item] > maxA:
                maxA = aList[item]
                maxAItem = item
        
        nextStore = maxAItem
    
    time += timeList[nextStore]
    count += 1
    aList.pop(nextStore)
    bList.pop(nextStore)

    time += 1
    
    if len(aList) == 0:
        break


if time > T:
    count -= 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
from operator import itemgetter
N,T = map(int, input().split())

ab = []
for i in range(N):
    l = list(map(int,input().split()))
    l.append(sum(l))
    ab.append(l)
# ab=[list(map(int,input().split())) for i in range(N)]
# ab = np.array(ab)
# absort = ab[np.argsort(ab[:, 0])[::-1]]
# absort = ab[np.argsort(ab[:, 2])]
ab.sort(key=itemgetter(2,0))

t = 0
n = 0

# print(ab)
for i in range(N):
    t += 1
    t += ab[i][0]*t + ab[i][1]
    if t <= T+0.5:
        n += 1

print (n)

Submission status: Wrong Answer

Solution code:
n,t = (int(x) for x in input().split())
a_list,b_list = [],[]
for _ in range(n):
  a,b = (int(x) for x in input().split())
  a_list.append(a)
  b_list.append(b)

def next(time,visited):
  if time > t:
    return len(visited) - 1
  
  max_num = 0 
  for i in range(n):
    if i in visited:
      continue
    else:
      visited.append(i)
      time += a_list[i] + b_list[i] + 1
      num = next(time,visited)
      if num > max_num:
        max_num = num
      visited.remove(i)
  return max_num
  
res = 0 
for i in range(n):
  time = 0
  visited = []
  visited.append(i)
  time += a_list[i] + b_list[i]
  num = next(time,visited)
  if num > res:
    res = num
print(res)

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):
    time += 1
    
    timeList = [(time * 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:
        nextStore = nextStoreList[0]
    else:
        maxA = -1
        maxAItem = -1
        for item in nextStoreList:
            if aList[item] > maxA:
                maxA = aList[item]
                maxAItem = item
        
        nextStore = maxAItem
    
    time += timeList[nextStore]
    count += 1
    aList.pop(nextStore)
    bList.pop(nextStore)

    if len(aList) == 0:
        break


if time > T:
    count -= 1

print(count)

Submission status: Wrong Answer

Solution code:
a, T  = map(int,input().split(" "))
ai = [0] * a 
bi = [0] * a 
time = 1
count = 0
for i in range(a):
    x, y = map(int,input().split(" "))

    ai[i] = x
    bi[i] = y

while time < T+0.5 and count < a:
    lowest = 9999999999
    for i in range(len(ai)):
        if lowest > ai[i] * time +bi[i]:
            lowest = ai[i] * time +bi[i]
            index = i
    c = ai.pop(index)
    cc = bi.pop(index)
    time = time + lowest
    if time <= T+0.5:
        count += 1
    time += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ti=0
count=0

while ti+1<T+0.5 and len(a)>0:
    ti=ti+1
    #print('here')
    #print(a*ti+b)
    #print(a)
    #ind=(a*ti+b).index(min(a*ti+b))
    ind=np.argmin(a*ti+b)
    mins=np.min(a*ti+b)
    #print(ind)
    if ti+mins<T+0.5:
        count=count+1
        ti=ti+mins
    else:
        ti=ti-1

    if len(a)>0:
        #print("this")
        #print(np.delete(a,ind))
        a=np.delete(a,ind)
        b=np.delete(b,ind)
    else:
        ti=T+0.5

    #print(ti, ind[0][0], mins, count, b)

print(count)

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
    res = max(res, ptr)
    tick += tt + 1
    #print tick, t, a, b, ptr, n
print res

Submission status: Wrong Answer

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

ab = sorted(
  [list(map(int, input().split())) for _ in range(n)], 
  key=lambda abi: abi[0] / (1 + abi[0] + abi[1])
)

now = 0
a_sum = 0
num = 0
for i, (ai, bi) in enumerate(ab):
  prev_now = now
  now += (1 + a_sum) * (1 + ai + bi)
  if now <= t:
    num += 1
  else:
    hoge = sorted((1 + a_sum) * (1 + a + b) for a, b in ab[i:])[0]
    if prev_now + hoge <= t:
      num += 1
    break
  a_sum += ai

print(num)

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:
from itertools import permutations
N,T=map(int,input().split())
AB=[]
def f(a,b,t):
    return a*t+b

for _ in range(N):
    i,j=map(int,input().split())
    AB.append((i,j))

l=0
r=N+1

def calc(n,debug):
    for ab in permutations(AB,n):
        t = 1
        for ij in ab:
            t += f(ij[0],ij[1],t)
            if t>T:

                break
        else:
            if debug:
                print(ab,t)
            return True
    return False
def solve(l,r):
    while abs(r-l) >1:
        m = (l+r)//2
        #print(l,m,r)
        if calc(m,debug=False):
            l=m
        else:
            r=m
    return l

print(solve(l,r))

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
n=N
yet_arrived_store = list(range(N))
while t <= T:
        t+=1

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

        c.sort()

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

        t+=c[j][0]

        if t > T:
                break

        next_arrived_store = c[j][2]
        yet_arrived_store.remove(next_arrived_store)
        n-=1

        if (n == 0):
                break

print(N-len(yet_arrived_store))

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:
def sel(Ti):
    global num
    ans = 1
    index = -1
    for k in range(len(a)):
        T = Ti -a[k][1]
        t = T/(a[k][0]+1)
        if  t >= ans:
            ans = t
            index = k
            

    if index == -1:
        return -1
    else:
        del a[index]
        num +=1
        return ans -1

N, T = map(int,input().split())
a = [list(map(int, input().split())) for k in range(N)]
T = T + 0.5
num =0

while(T != -1):
    T = sel(T)
    
print(num)

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())
A = []
B = []
for i in range(N):
  ai,bi = map(int,input().split())
  A.append(ai)
  B.append(bi)
t = 0
ans = 0
while(t<(T+0.5)):
  t += 1
  wait = 10**13
  trim = -1
  for i in range(N):
    if wait > A[i]*t + B[i]:
      wait = A[i]*t + B[i]
      trim = i
  t += wait
  if t<(T+0.5):
    ans += 1
  if trim != -1:
    del A[trim]
    del B[trim]
    N -= 1
print(ans)

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
  if not t < T + 0.5:
    break
  visited[minIdx] = True
  #print(minCost, minIdx, visited)
  count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ti=0
count=0

while ti+1<T+0.5 and len(a)>0:
    ti=ti+1
    #print('here')
    #print(a*ti+b)
    #print(a)
    #ind=(a*ti+b).index(min(a*ti+b))
    ind=np.argmin(a*ti+b)
    mins=min(a*ti+b)
    #print(ind)
    if ti+mins<T+0.5:
        count=count+1
        ti=ti+mins
    else:
        ti=T+0.5

    if len(a)>0:
        #print("this")
        #print(np.delete(a,ind))
        a=np.delete(a,ind)
        b=np.delete(b,ind)
    else:
        ti=T+0.5

    #print(ti, ind[0][0], mins, count, b)

print(count)

Submission status: Wrong Answer

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

t = 1
store = 0

while t<T+0.5:
    a=[]
    for i in range(N):
        a.append(tmp[i][0]*t+tmp[i][1])
    if t+min(a)<T+0.5 and store<N:
        t+=min(a)
        store+=1
        t+=1
    else:
        break

print(store)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

t = 0
cnt = 0
i = 0
while t <= T and i < N:
    # 店へ向かう
    t += 1
    # 最小時間の店を見つける
    ind = 0
    min_t = AB[0][0] * t + AB[0][1]
    for j in range(1, len(AB)):
        cost = AB[j][0]*t + AB[j][1]
        if min_t > cost:
            ind = j
            min_t = cost
    # 同じ店にはいかない
    AB.remove(AB[ind])
    t += min_t
    if t <= T:
        cnt += 1
    i += 1
print(cnt)