codeforces-scrape

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

1860B.md (2111B)


      1 Source: https://codeforces.com/problemset/problem/1860/B
      2 
      3 B. Fancy Coins
      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 Monocarp is going to make a purchase with cost of exactly $m$ burles.
     22 
     23 He has two types of coins, in the following quantities:
     24 
     25 * coins worth $1$ burle: $a_1$ regular coins and infinitely many fancy coins;
     26 * coins worth $k$ burles: $a_k$ regular coins and infinitely many fancy coins.
     27 
     28 Monocarp wants to make his purchase in such a way that there's no change — the total worth of provided coins is exactly $m$. He can use both regular and fancy coins. However, he wants to spend as little fancy coins as possible.
     29 
     30 What's the smallest total number of fancy coins he can use to make a purchase?
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of testcases.
     35 
     36 The only line of each testcase contains four integers $m, k, a_1$ and $a_k$ ($1 \le m \le 10^8$; $2 \le k \le 10^8$; $0 \le a_1, a_k \le 10^8$) — the cost of the purchase, the worth of the second type of coin and the amounts of regular coins of both types, respectively.
     37 
     38 Output
     39 
     40 For each testcase, print a single integer — the smallest total number of fancy coins Monocarp can use to make a purchase.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 4
     48 
     49 11 3 0 0
     50 
     51 11 3 20 20
     52 
     53 11 3 6 1
     54 
     55 100000000 2 0 0
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 5
     62 0
     63 1
     64 50000000
     65 ```
     66 
     67 Note
     68 
     69 In the first testcase, there are no regular coins of either type. Monocarp can use $2$ fancy coins worth $1$ burle and $3$ fancy coins worth $3$ (since $k=3$) burles to get $11$ total burles with $5$ total fancy coins.
     70 
     71 In the second testcase, Monocarp has a lot of regular coins of both types. He can use $11$ regular coins worth $1$ burle, for example. Notice that Monocarp doesn't have to minimize the total number of used coins. That way he uses $0$ fancy coins.
     72 
     73 In the third testcase, Monocarp can use $5$ regular coins worth $1$ burle and $1$ regular coin worth $3$ burles. That will get him to $8$ total burles when he needs $11$. So, $1$ fancy coin worth $3$ burles is enough.