Bananas in a Microwave (Codeforces 1498D)
Tags: DP, dfs and similar

You have a malfunctioning microwave in which you want to put some bananas. You have $$$n$$$ time-steps before the microwave stops working completely. At each time-step, it displays a new operation.Let $$$k$$$ be the number of bananas in the microwave currently. Initially, $$$k = 0$$$. In the $$$i$$$-th operation, you are given three parameters $$$t_i$$$, $$$x_i$$$, $$$y_i$$$ in the input. Based on the value of $$$t_i$$$, you must do one of the following:Type 1: ($$$t_i=1$$$, $$$x_i$$$, $$$y_i$$$) — pick an $$$a_i$$$, such that $$$0 \le a_i \le y_i$$$, and perform the following update $$$a_i$$$ times: $$$k:=\lceil (k + x_i) \rceil$$$.Type 2: ($$$t_i=2$$$, $$$x_i$$$, $$$y_i$$$) — pick an $$$a_i$$$, such that $$$0 \le a_i \le y_i$$$, and perform the following update $$$a_i$$$ times: $$$k:=\lceil (k \cdot x_i) \rceil$$$.Note that $$$x_i$$$ can be a fractional value. See input format for more details. Also, $$$\lceil x \rceil$$$ is the smallest integer $$$\ge x$$$.At the $$$i$$$-th time-step, you must apply the $$$i$$$-th operation exactly once.For each $$$j$$$ such that $$$1 \le j \le m$$$, output the earliest time-step at which you can create exactly $$$j$$$ bananas. If you cannot create exactly $$$j$$$ bananas, output $$$-1$$$.

Input: The first line contains two space-separated integers $$$n$$$ $$$(1 \le n \le 200)$$$ and $$$m$$$ $$$(2 \le m \le 10^5)$$$.Then, $$$n$$$ lines follow, where the $$$i$$$-th line denotes the operation for the $$$i$$$-th timestep. Each such line contains three space-separated integers $$$t_i$$$, $$$x'_i$$$ and $$$y_i$$$ ($$$1 \le t_i \le 2$$$, $$$1\le y_i\le m$$$).Note that you are given $$$x'_i$$$, which is $$$10^5 \cdot x_i$$$. Thus, to obtain $$$x_i$$$, use the formula $$$x_i= \dfrac{x'_i} {10^5}$$$.For type 1 operations, $$$1 \le x'_i \le 10^5 \cdot m$$$, and for type 2 operations, $$$10^5 < x'_i \le 10^5 \cdot m$$$.

Output: Print $$$m$$$ integers, where the $$$i$$$-th integer is the earliest time-step when you can obtain exactly $$$i$$$ bananas (or $$$-1$$$ if it is impossible).

Note: In the first sample input, let us see how to create $$$16$$$ number of bananas in three timesteps. Initially, $$$k=0$$$.  In timestep 1, we choose $$$a_1=2$$$, so we apply the type 1 update — $$$k := \lceil(k+3)\rceil$$$ — two times. Hence, $$$k$$$ is now 6.  In timestep 2, we choose $$$a_2=0$$$, hence value of $$$k$$$ remains unchanged.  In timestep 3, we choose $$$a_3=1$$$, so we are applying the type 1 update $$$k:= \lceil(k+10)\rceil$$$ once. Hence, $$$k$$$ is now 16. It can be shown that $$$k=16$$$ cannot be reached in fewer than three timesteps with the given operations.In the second sample input, let us see how to create $$$17$$$ number of bananas in two timesteps. Initially, $$$k=0$$$.  In timestep 1, we choose $$$a_1=1$$$, so we apply the type 1 update — $$$k := \lceil(k+3.99999)\rceil$$$ — once. Hence, $$$k$$$ is now 4.  In timestep 2, we choose $$$a_2=1$$$, so we apply the type 2 update — $$$k := \lceil(k\cdot 4.12345)\rceil$$$ — once. Hence, $$$k$$$ is now 17. It can be shown that $$$k=17$$$ cannot be reached in fewer than two timesteps with the given operations.

Sample Inputs:
3 20
1 300000 2
2 400000 2
1 1000000 3

3 20
1 399999 2
2 412345 2
1 1000001 3

Sample Outputs:
-1 -1 1 -1 -1 1 -1 -1 -1 3 -1 2 3 -1 -1 3 -1 -1 -1 3

-1 -1 -1 1 -1 -1 -1 1 -1 -1 3 -1 -1 -1 3 -1 2 -1 3 -1

Solution (Python):
import os, sys
from io import BytesIO, IOBase
import math
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
    return int(input())

def getStrs():
    return input().split()

def getInts():
    return list(map(int, input().split()))

def getStr():
    return input()

def listStr():
    return list(input())

def getMat(n):
    return [getInts() for _ in range(n)]

def getBin():
    return list(map(int, list(input())))

def isInt(s):
    return '0' <= s[0] <= '9'

def ceil_(a, b):
    return a // b + (a % b > 0)

def ceil2(a, b):
    return math.floor((a + b - 1) / b)
''
TT = pow(10, 5)
(N, M) = getInts()
ans = [-1] * (M + 1)
done = set([0])
LIM = float(M * TT)
for i in range(1, N + 1):
    (t, x, y) = getInts()
    if t == 1:
        x = ceil2(x, TT)
        for j in list(done):
            for k in range(y):
                j += x
                if j > M or j in done:
                    break
                done.add(j)
                ans[j] = i
    else:
        x = float(x)
        for j in list(done):
            for k in range(y):
                if j * x > LIM:
                    break
                j = ceil2(j * x, TT)
                if j > M or j in done:
                    break
                done.add(j)
                ans[j] = i
print(*ans[1:])

Solution (Python):
import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
    return int(input())

def getStrs():
    return input().split()

def getInts():
    return list(map(int, input().split()))

def getStr():
    return input()

def listStr():
    return list(input())

def getMat(n):
    return [getInts() for _ in range(n)]

def getBin():
    return list(map(int, list(input())))

def isInt(s):
    return '0' <= s[0] <= '9'

def ceil_(a, b):
    return a // b + (a % b > 0)
MOD = 10 ** 9 + 7
''
TT = pow(10, 5)

def solve():

    def ceil2(a, b):
        return math.floor((a + b - 1) / b)
    (N, M) = getInts()
    ans = [-1] * (M + 1)
    ans[0] = 0
    done = set([0])
    LIM = float(M * 10 ** 5)
    for i in range(1, N + 1):
        (t, x, y) = getInts()
        if t == 1:
            x = ceil2(x, TT)
            for j in list(done):
                for k in range(y):
                    j += x
                    if j > M or j in done:
                        break
                    done.add(j)
                    ans[j] = i
        else:
            x = float(x)
            for j in list(done):
                for k in range(y):
                    if j * x > LIM:
                        break
                    j = ceil2(j * x, TT)
                    if j > M or j in done:
                        break
                    done.add(j)
                    ans[j] = i
    print(*ans[1:])
    return
solve()

Solution (Python):
import io
import os
from collections import Counter, defaultdict, deque
from math import ceil, floor

def solve(N, M, TXY):

    def ceildiv(x, y):
        return floor((x + y - 1) / y)
    big = float(M * 10 ** 5)
    possible = {0}
    inf = float('inf')
    earliest = [inf] * (M + 1)
    for (ts, (t, x, y)) in enumerate(TXY, start=1):
        if t == 1:
            assert 1 <= x <= M * 10 ** 5
            x = ceildiv(x, 10 ** 5)
            for k in list(possible):
                for i in range(y):
                    k = k + x
                    if k > M or k in possible:
                        break
                    possible.add(k)
                    earliest[k] = min(earliest[k], ts)
        else:
            assert t == 2
            assert 10 ** 5 < x <= M * 10 ** 5
            x = float(x)
            for k in list(possible):
                for i in range(y):
                    if k * x > big:
                        break
                    k = ceildiv(k * x, 10 ** 5)
                    if k > M or k in possible:
                        break
                    possible.add(k)
                    earliest[k] = min(earliest[k], ts)
    return ' '.join((str(x) if x != inf else '-1' for x in earliest[1:]))
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    TC = 1
    for tc in range(1, TC + 1):
        (N, M) = [int(x) for x in input().split()]
        TXY = [[int(x) for x in input().split()] for i in range(N)]
        ans = solve(N, M, TXY)
        print(ans)