The Cunning Seller (hard version)

We need buy exactly $n$ watermelons using deals whose sizes are

$1, 3, 9, 27, \dots$

A deal of size $3^x$ costs

$3^{x+1} + x \cdot 3^{x-1}.$

For $x=0$, that is just $3$ coins.

The annoying part is the limit: at most $k$ deals. The key is to stop thinking about “choosing deals” from scratch and instead start from the most compressed representation of $n$.

Minimum possible number of deals

Write $n$ in base $3$:

$n = a_0 3^0 + a_1 3^1 + a_2 3^2 + \cdots$

where each $a_i \in \{0,1,2\}$.

This means we can buy exactly $n$ watermelons using $a_i$ deals of size $3^i$. The total number of deals is

$a_0 + a_1 + a_2 + \cdots.$

This is actually the minimum possible number of deals. Why? Because three deals of size $3^i$ can always be compressed into one deal of size $3^{i+1}$, reducing the deal count. The normal ternary representation is what you get after all possible compression is done.

So if

$\text{sumTernaryDigits}(n) > k,$

then the answer is $-1$. No magic trick exists; the seller has successfully scammed time itself.

Why splitting helps

The ternary representation uses the fewest deals, but not necessarily the minimum cost under the limit.

Smaller deals are cheaper per watermelon:

$\frac{3^{x+1} + x \cdot 3^{x-1}}{3^x} = 3 + \frac{x}{3}.$

So, if we are allowed to use more deals, we want to split large deals into smaller ones.

Splitting one deal of size $3^x$ into three deals of size $3^{x-1}$ preserves the number of watermelons:

$3^x = 3 \cdot 3^{x-1}.$

The deal count increases by $2$.

Now compute how much money this saves.

Original cost:

$3^{x+1} + x \cdot 3^{x-1}.$

New cost:

= 3^{x+1} + (x-1)3^{x-1}.$$ Savings: $$\left(3^{x+1} + x3^{x-1}\right) - \left(3^{x+1} + (x-1)3^{x-1}\right) = 3^{x-1}.$$ So splitting a larger deal saves more. A split at level $x$ saves $3^{x-1}$, which is bigger than every split at a smaller level. That gives the greedy rule: **Always split the largest available deal first, as long as we still have room for two extra deals.** **Algorithm** For each test case: 1. Convert $n$ to ternary digits $cnt[i]$. 2. Let $deals = \sum cnt[i]$. 3. If $deals > k$, print $-1$. 4. Compute the cost of this ternary representation. 5. From large powers down to $1$, split as many deals as possible: - splitting one deal at level $i$ needs $2$ extra deals; - it decreases cost by $3^{i-1}$; - it creates $3$ deals at level $i-1$. 6. Print the final cost. One subtle point: if $k - deals$ is odd, that last extra deal is useless. Every split increases the deal count by exactly $2$, so reachable deal counts have the same parity. Since the condition is “at most $k$”, we simply use the largest reachable count not exceeding $k$. **Complexity** Since $n \le 10^9$, there are only about $20$ ternary digits. Each test case is $O(\log_3 n)$, which is tiny. Like, aggressively tiny.