2189B.md (3141B)
1 Source: https://codeforces.com/problemset/problem/2189/B 2 3 B. The Curse of the Frog 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 On an infinite number line, at point $0$, sits a frog. After many years of meditation, the frog has mastered $n$ unique types of magical jumps. The $i$-th type of jump allows it to jump forward by no more than $a_i$ units. In other words, if it was at integer point $k$, after the jump it can land at any integer point from $k$ to $k+a_i$. 22 23 But magic always comes with a price; it has been cursed. Before each $b_i$-th attempt (before $b_i$-th, $2b_i$-th, $3b_i$-th etc. attempt among the jumps of type $i$) to use the $i$-th type of jump, the frog rolls back $c_i$ units! In other words, if it was at point $k$, it will first find itself at point $k-c_i$, and after the jump, it can land at any integer point from $k-c_i$ to $k-c_i+a_i$. 24 25 The frog's goal is to reach the point with the number $x$, using jumps while minimizing the number of rollbacks. Help the frog — find the minimum number of rollbacks it will have to endure on its way to the goal, or determine that it cannot reach point $x$. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 In the first line of each test case, there are $2$ integers $n$ and $x$ ($1 \leq n \leq 10^5$, $1 \leq x \leq 10^{18}$) — the number of types of jumps the frog can make and its final target. 32 33 In the following $n$ lines, the description of the jump types is provided; the $i$-th line contains $3$ integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i, b_i, c_i \leq 10^6$). 34 35 It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, if the frog can reach point $x$, find the smallest number of rollbacks it must endure to do so. If it cannot reach point $x$, output $-1$. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 48 1 1 49 50 3 3 3 51 52 1 7 53 54 4 2 5 55 56 2 4 57 58 1 2 3 59 60 2 2 4 61 62 5 8 63 64 12 1 11 65 66 10 1 4 67 68 1 1 3 69 70 1 2 5 71 72 2 1 7 73 74 1 1000000000000000000 75 76 1000000 4 654321 77 78 1 10 79 80 2 2 1 81 ``` 82 83 Output 84 85 ``` 86 0 87 88 1 89 90 -1 91 92 2 93 94 298892990032 95 96 3 97 ``` 98 99 Note 100 101 In the first test case, the frog can jump forward by $1$ unit and will end up at point $1$. Thus, the answer is $0$. 102 103 In the third test case, it can be shown that the frog cannot reach point $4$. 104 105 In the fourth test case, the frog can reach point $8$, for example, as follows: jump using the $1$-st type by $12$, jump using the $4$-th type by $1$, and jump using the $2$-nd type by $10$. Then it will sequentially be at the following points $0 \rightarrow \text{(rollback)} -11 \rightarrow 1 \rightarrow 2 \rightarrow \text{(rollback)} -2 \rightarrow 8$. 106 107 In the sixth test case, the frog can reach point $10$, for example, as follows: jump $6$ times by $2$ and $1$ time by $1$. Then it will sequentially be at the following points $0 \rightarrow 2 \rightarrow \text{(rollback)} 1 \rightarrow 3 \rightarrow 5 \rightarrow \text{(rollback)} 4 \rightarrow 6 \rightarrow 8 \rightarrow \text{(rollback)} 7 \rightarrow 9 \rightarrow 10$.