codeforces-scrape

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

2132C1.md (2396B)


      1 Source: https://codeforces.com/problemset/problem/2132/C1
      2 
      3 C1. The Cunning Seller (easy 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 easy 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 critically little time. Because of this, he wants to buy exactly $n$ watermelons, making the least possible number of deals.
     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, considering that he will make the least possible number of deals.
     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 is one integer $n$ $(1 \le n \le 10^9)$ — how many watermelons need to be bought.
     34 
     35 Output
     36 
     37 For each test case, output a single integer — the minimum cost of the watermelons.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 7
     45 
     46 1
     47 
     48 3
     49 
     50 8
     51 
     52 2
     53 
     54 10
     55 
     56 20
     57 
     58 260010000
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 3
     65 10
     66 26
     67 6
     68 36
     69 72
     70 2250964728
     71 ```
     72 
     73 Note
     74 
     75 Note that there is no point in buying more watermelons than needed, so we won't consider deals where there are more watermelons than necessary.
     76 
     77 Let's consider the costs of the first two deal options:
     78 
     79 Deal A: $1$ watermelon — $3$ coins.
     80 
     81 Deal B: $3$ watermelons — $10$ coins.
     82 
     83 In the first sample, the only way to buy $1$ watermelon is to use Deal A, so the answer is $3$.
     84 
     85 In the second sample, you can buy $3$ watermelons with a single Deal B for $10$ coins.
     86 
     87 In the third sample, you can make $2$ Deals A and $2$ Deals B, which will cost a total of $26$ coins. If we make $3$ deals, we can get $3$, $5$, $7$, or $9$ watermelons. If we make fewer than $3$ deals, we will get no more than $6$ watermelons, which means it is impossible to buy $8$ watermelons for less than $4$ deals.