308314: CF1498D. Bananas in a Microwave
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Bananas in a Microwave
题意翻译
你有一个变量 $k$ ,最开始 $k=0$ ,有 $n$ 个操作,操作有三个参数 $t,x,y$,每个操作是以下二者之一: 对于 $t=1$ ,$x_0=x/10^5$,选择一个 $a\leq y$,执行 $a$ 次如下变换:$k=ceil(k+x_0)$ 对于 $t=2$ ,$x_0=x/10^5$,选择一个 $a\leq y$,执行 $a$ 次如下变换:$k=ceil(k * x_0)$ 其中 $ceil(x)$ 表示对 $x$ 向上取整。 还有 $m$ 个询问,每个询问相互独立,其中第 $i$ 个询问请回答 $k=i$ 最早在哪个操作后出现。 保证 $n\leq200,m\leq10^5,x_0\leq m$题目描述
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 $ .输入输出格式
输入格式
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 $ .
输出格式
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).
输入输出样例
输入样例 #1
3 20
1 300000 2
2 400000 2
1 1000000 3
输出样例 #1
-1 -1 1 -1 -1 1 -1 -1 -1 3 -1 2 3 -1 -1 3 -1 -1 -1 3
输入样例 #2
3 20
1 399999 2
2 412345 2
1 1000001 3
输出样例 #2
-1 -1 -1 1 -1 -1 -1 1 -1 -1 3 -1 -1 -1 3 -1 2 -1 3 -1