codeforces-scrape

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

940B.md (1668B)


      1 Source: https://codeforces.com/problemset/problem/940/B
      2 
      3 B. Our Tanya is Crying Out Loud
      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 Right now she actually isn't. But she will be, if you don't solve this problem.
     22 
     23 You are given integers *n*, *k*, *A* and *B*. There is a number *x*, which is initially equal to *n*. You are allowed to perform two types of operations:
     24 
     25 1. Subtract 1 from *x*. This operation costs you *A* coins.
     26 2. Divide *x* by *k*. Can be performed only if *x* is divisible by *k*. This operation costs you *B* coins.
     27 
     28 What is the minimum amount of coins you have to pay to make *x* equal to 1?
     29 
     30 Input
     31 
     32 The first line contains a single integer *n* (1 ≤ *n* ≤ 2·109).
     33 
     34 The second line contains a single integer *k* (1 ≤ *k* ≤ 2·109).
     35 
     36 The third line contains a single integer *A* (1 ≤ *A* ≤ 2·109).
     37 
     38 The fourth line contains a single integer *B* (1 ≤ *B* ≤ 2·109).
     39 
     40 Output
     41 
     42 Output a single integer — the minimum amount of coins you have to pay to make *x* equal to 1.
     43 
     44 Examples
     45 
     46 Input
     47 
     48 ```
     49 9  
     50 2  
     51 3  
     52 1
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 6
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 5  
     65 5  
     66 2  
     67 20
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 8
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 19  
     80 3  
     81 4  
     82 2
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 12
     89 ```
     90 
     91 Note
     92 
     93 In the first testcase, the optimal strategy is as follows:
     94 
     95 * Subtract 1 from *x* (9 → 8) paying 3 coins.
     96 * Divide *x* by 2 (8 → 4) paying 1 coin.
     97 * Divide *x* by 2 (4 → 2) paying 1 coin.
     98 * Divide *x* by 2 (2 → 1) paying 1 coin.
     99 
    100 The total cost is 6 coins.
    101 
    102 In the second test case the optimal strategy is to subtract 1 from *x* 4 times paying 8 coins in total.