codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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