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: Runtime Error

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

if not AB0:
    raise

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] * 40
    dp[0] = 0
    for a,b in AB1:
        for n in range(39, -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: Runtime Error

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

if N == 1:
    raise

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] * 40
    dp[0] = 0
    for a,b in AB1:
        for n in range(39, -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: Runtime Error

Solution code:
def lin(t,i):
    return As[i]*t+Bs[i]
f=input().split(" ")
n,t=int(f[0]),int(f[1])
As=[]
Bs=[]
for i in range(n):
  f=input().split(" ")
  As.append(int(f[0]))
  Bs.append(int(f[1]))
time=0
count=0
shop_list=list(range(n))
while True:
    test=min(enumerate([lin(time+1,i) for i in shop_list]), key = lambda x:x[1])
    next_time,shop=test[1],test[0]
    if time+1+next_time>t:
        break
    else:
        time=time+1+next_time
        shop_list.remove(shop)
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
using namespace std;
typedef long long ll;
int main() {
    string S;
    int Q;
    cin >> S >> Q;
    deque<char> l, r;
    bool flag = true;
    int T, F;
    char C;
    for (int i = 0; i < Q; i++) {
        cin >> T;
        if (T == 1) flag = !flag;
        else {
            cin >> F >> C;
            if (F == 1) {
                if (flag) l.push_front(C);
                else r.push_back(C);
            } else {
                if (flag) r.push_back(C);
                else l.push_front(C);
            }
        }
    }
    if (flag) {
        for (char c : l) cout << c;
        cout << S;
        for (char c : r) cout << c;
        cout << "\n";
    } else {
        while (!r.empty()) {
            cout << r.back();
            r.pop_back();
        }
        reverse(S.begin(), S.end());
        cout << S;
        while (!l.empty()) {
            cout << l.back();
            l.pop_back();
        }
        cout << "\n";
    }
    return 0;
}

Submission status: Runtime Error

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
    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: Runtime Error

Solution code:
from operator import itemgetter


def calc(item, t):
    reuslt = []
    # for i in item:
    reuslt = [[i[0], i[1], i[0] * t + i[1]] for i in  item]

    return sorted(reuslt, key=itemgetter(2))

N, T = map(int, input().strip().split())
p = []
for n in range(N):
   a, b = map(int, input().strip().split())
   p.append([a, b, a+b])

p_sort = sorted(p, key=itemgetter(2))

max_count = 0
t_count = 1

while True:
    item = p_sort.pop(0)
    if max_count == 0 and T <= item[2]:
        break

    t_count += item[0] * t_count + item[1]
    if T + 0.5 <= t_count:
        break

    max_count += 1
    t_count += 1
    p_sort = calc(p_sort, t_count)


print(max_count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
NT = [int(i) for i in input().split()]
N = NT[0]
N1 = N
N2 = N
t = 0
count = 0
a = []
b = []
T = NT[1]
endtime = T + 0.5
while N > 0:
    t = t + 1
    ab = [int(j) for j in input().split()]
    a.insert(1,ab[0] * t)
    b.insert(1,ab[1])
    N = N -1
while t < T:
    s1indx = a.index(min(a)) 
    short1 = min(a) + b[s1indx]
    s2indx = b.index(min(b))
    short2 = min(b) + a[s2indx]
    if short1 <= short2:
        short = short1
        indx = s1indx
    else:
        short = short2
        indx = s2indx
    t = t + short
    a.pop(indx)
    b.pop(indx)
    count = count + 1

print(count)

Submission status: Runtime Error

Solution code:
def min_shop(time, shops):
    min_time = 1000000000
    for i, shop in enumerate(shops):
        t = shop[0] * time + shop[1]
        if t < min_time:
            min_time = t
            min_index = i
        elif t == min_time:
            if shop[0] > shops[min_index][0]:
                min_time = t
                min_index = i            
    if min_index or min_index == 0:
        shops.pop(min_index)
    return min_time


val = input().split(' ')
n = int(val[0])
t = int(val[1])
limit = t + 0.5

shops = []
for i in range(n):
    shops.append([int(shop) for shop in input().split(' ')])

time = 0
counter = 0
shopping = 0

while(time < limit):
    counter += 1
    if counter % 2 == 1:
        if counter != 1:
            shopping += 1
        if len(shops) == 0:
            break
        time += 1
    else:
        min_time = min_shop(time, shops)
        time += min_time
        
print(shopping)

Submission status: Runtime Error

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

i=0
while i<N:
  s=input().split()
  a.append(s[0])
  b.append(s[1])
  i=i+1

t=0
x=0
while t<T+0.5:
  n=0
  while n<N:
    y=int(a[n]*t+b[n])
    Y=int(a[n]*t+b[n])
    if y<=Y:
      Y=y
    n=n+1
  t=t+1+Y
  x=x+1
print(x)

Submission status: Runtime Error

Solution code:
N,T = map(int, input().split())
a = [-1 for i in range(N)]
b = [-1 for i in range(N)]
dplist ={}


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

a,b = zip(*c)

def dynamic(n,t):
    global a
    global b
    global N
    global T 
    global dplist
    remained = T+0.5-t

    if (n,t)in dplist:
        return dplist[(n,t)]

    if n == N :
        res =0
    elif remained < a[n]*t+b[n]+1:
        res = dynamic(n+1,t)
    else:
        res = max(dynamic(n+1,t),dynamic(n+1,t+a[n]*t+b[n])+1)

    dplist[(n,t)] = res
    return res
    
print(dynamic(0,0))

Submission status: Runtime Error

Solution code:
def min_shop(time, shops):
    min_time = 1000000000
    for i, shop in enumerate(shops):
        t = shop[0] * time + shop[1]
        if t <= min_time:
            min_time = t
            min_index = i
    if min_index or min_index == 0:
        shops.pop(min_index)
    return min_time


val = input().split(' ')
n = int(val[0])
t = int(val[1])
limit = t + 0.5

shops = []
for i in range(n):
    shops.append([int(shop) for shop in input().split(' ')])

time = 0
counter = 0
shopping = 0

while(time < limit):
    counter += 1
    if counter % 2 == 1:
        if counter != 1:
            shopping += 1
        if len(shops) == 0:
            break
        time += 1
    else:
        min_time = min_shop(time, shops)
        time += min_time
        
print(shopping)

Submission status: Runtime Error

Solution code:
N,T  =int(input().split())
a = []
b = []
c = []
for i in range(N):
    a[i] , b[i] = int(input().split())
    c[i] = a[i] + b[i]
min_time  = []

min_time[0] = 0

for t in range(1,T+1):

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

    min_time[t] = min_time[t-1] + min(c)

    
print(min_time[T])

Submission status: Runtime Error

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

#print(n,t,sl)

mc = 0
s = 0
for i in range(n):
  sn = n -i
  ds =0
  mc +=1
  for f in range(len(sl)):
    tmp = sl[f][0]*sn +sl[f][1]
    if tmp > ds:
      ds = tmp
      sfn = f
  mc = mc +sl[f][0]*(i+1) + sl[f][1]
  if mc >= t +0.5:
    break
  else:
    s +=1
    sl.pop(sfn)
  #print(sl)

#print(mc,t +0.5,s)
print(s)

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, T = LI()
ab = []
for i in range(N):
    ab.append(LI())
ans = 0
time = 1
shops = [i for i in range(N)]
while T + 0.5 > time:
    cost = mod
    for i in shops:
        a,b = ab[i]
        if cost > a * time + b:
            r_shop = i
            cost = a * time + b
    if len(shops) > 0:
        shops.remove(r_shop)
    time += cost
    if T + 0.5 > time:
        ans += 1
    # move 
    time += 1

print(ans)

Submission status: Runtime Error

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:
  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: Runtime Error

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,ab[j][0]])
    tmp = sorted(tmp)
    if tmp[0][0] == tmp[1][0]:
        if tmp[0][2] < tmp[1][2]:
            time += tmp[1][2]
    else:
        time += tmp[0][0]
    ab.remove(ab[tmp[0][1]])
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Runtime Error

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

import sys

time = 0
mintime = 10**9

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

Submission status: Runtime Error

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(n):
        tmp.append([ab[j][0]*time+ab[j][1],j])
    tmp = sorted(tmp)
    time += tmp[0][0]
    ab.remove(ab[j])
    if time > t:
        break
    ans += 1
    if ans == n:
        break

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())

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

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
Ans=[0]*n
Ans[0]=1
ct1,ct2,ct3=1,0,0
for i in range(1,n):
  if depth[i]%2==0:
    if 3*ct1+1<=n:
      Ans[i]=3*ct1+1
      ct1+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
  else:
    if 3*ct2+2<=n:
      Ans[i]=3*ct2+2
      ct2+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)