codeforces-scrape

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

1985F.md (2485B)


      1 Source: https://codeforces.com/problemset/problem/1985/F
      2 
      3 F. Final Boss
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 You are facing the final boss in your favorite video game. The boss enemy has $h$ health. Your character has $n$ attacks. The $i$'th attack deals $a_i$ damage to the boss but has a cooldown of $c_i$ turns, meaning the next time you can use this attack is turn $x + c_i$ if your current turn is $x$. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn.
     22 
     23 Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is $0$ or less.
     24 
     25 Input
     26 
     27 The first line contains $t$ ($1 \leq t \leq 10^4$)  – the number of test cases.
     28 
     29 The first line of each test case contains two integers $h$ and $n$ ($1 \leq h, n \leq 2 \cdot 10^5$) – the health of the boss and the number of attacks you have.
     30 
     31 The following line of each test case contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq 2 \cdot 10^5$) – the damage of your attacks.
     32 
     33 The following line of each test case contains $n$ integers $c_1, c_2, ..., c_n$ ($1 \leq c_i \leq 2 \cdot 10^5$) – the cooldown of your attacks.
     34 
     35 It is guaranteed that the sum of $h$ and $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output an integer, the minimum number of turns required to beat the boss.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 8
     47 
     48 3 2
     49 
     50 2 1
     51 
     52 2 1
     53 
     54 5 2
     55 
     56 2 1
     57 
     58 2 1
     59 
     60 50 3
     61 
     62 5 6 7
     63 
     64 5 6 7
     65 
     66 50 3
     67 
     68 2 2 2
     69 
     70 3 3 3
     71 
     72 90000 2
     73 
     74 200000 200000
     75 
     76 1 1
     77 
     78 100000 1
     79 
     80 1
     81 
     82 200000
     83 
     84 6 7
     85 
     86 3 2 3 2 3 1 2
     87 
     88 6 5 9 5 10 7 7
     89 
     90 21 6
     91 
     92 1 1 1 1 1 1
     93 
     94 5 5 8 10 7 6
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 1
    101 3
    102 15
    103 25
    104 1
    105 19999800001
    106 1
    107 21
    108 ```
    109 
    110 Note
    111 
    112 For the first test case, you can use attacks $1$ and $2$ on the first turn, dealing $3$ damage in total, and slaying the boss.
    113 
    114 For the second case, you can beat the boss in $3$ turns by using the following attacks:
    115 
    116 Turn $1$: Use attacks $1$ and $2$, dealing $3$ damage to the boss. The boss now has $2$ health left.
    117 
    118 Turn $2$: Use attack $2$, dealing $1$ damage to the boss. The boss now has $1$ health left.
    119 
    120 Turn $3$: Use attack $1$, dealing $2$ damage to the boss. The boss now has $-1$ health left. Since its health is less than or equal to $0$, you beat the boss.
    121 
    122 For the sixth test case: remember to use 64-bit integers as the answer can get large.