codeforces-scrape

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

2132C2.md (2614B)


      1 Source: https://codeforces.com/problemset/problem/2132/C2
      2 
      3 C2. The Cunning Seller (hard version)
      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 This is the hard version of the problem. The easy version differs from the hard one in that it requires determining the minimum cost with the least number of deals, while the hard version requires determining the minimum cost with a limited number of deals.
     22 
     23 After the cunning seller sold three watermelons instead of one, he decided to increase his profit — namely, he bought even more watermelons. Now he can sell $3^x$ watermelons for $3^{x+1} + x \cdot 3^{x-1}$ coins, where $x$ is a non-negative integer. Such a sale is called a deal.
     24 
     25 A calculating buyer came to him, but he has little time, so the buyer can make no more than $k$ deals and plans to buy exactly $n$ watermelons.
     26 
     27 The buyer is in a hurry and has therefore turned to you to determine the minimum number of coins he must pay the seller for $n$ watermelons if he makes no more than $k$ deals. If it is impossible to buy exactly $n$ watermelons while making no more than $k$ deals, output $-1$.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. The description of each test case follows.
     32 
     33 In a single line of each test case, there are two integers $n$ and $k$ $(1 \le n, k \le 10^9)$ — how many watermelons need to be bought and how many deals can be made.
     34 
     35 Output
     36 
     37 For each test case, output a single integer — the minimum cost of the watermelons or $-1$ if it is impossible to buy the watermelons while meeting all the conditions.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 8
     45 
     46 1 1
     47 
     48 3 3
     49 
     50 8 3
     51 
     52 2 4
     53 
     54 10 10
     55 
     56 20 14
     57 
     58 3 2
     59 
     60 9 1
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 3
     67 9
     68 -1
     69 6
     70 30
     71 63
     72 10
     73 33
     74 ```
     75 
     76 Note
     77 
     78 Note that there is no point in buying more watermelons than needed, so we will not consider deals where there are more watermelons than necessary.
     79 
     80 Let's consider the costs of the first two deal options:
     81 
     82 Deal A: $1$ watermelon — $3$ coins.
     83 
     84 Deal B: $3$ watermelons — $10$ coins.
     85 
     86 In the first sample, the only way to buy $1$ watermelon is to use Deal A, so the answer is $3$.
     87 
     88 In the second sample, you can buy $3$ watermelons either with Deal B for $10$ coins or with three Deal A for $9$ coins, so the answer is $9$.
     89 
     90 In the third sample, there are the following options for $3$ deals:
     91 
     92 $3$ Deals A — $3$ watermelons.
     93 
     94 $2$ Deals A and $1$ Deal B — $5$ watermelons.
     95 
     96 $1$ Deal A and $2$ Deals B — $7$ watermelons.
     97 
     98 $3$ Deals B — $9$ watermelons.
     99 
    100 It can be seen that it is impossible to buy exactly 8 watermelons.