CF1498D Bananas in a Microwave

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 $ .

N/A

N/A

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.