The Cunning Seller (easy version)

We need buy exactly $n$ watermelons. One deal can buy $3^x$ watermelons, and its cost is

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

For $x=0$, this is just the special-looking but obvious deal from the statement: $1$ watermelon costs $3$ coins.

The Main Constraint Is Not Cost First

The buyer must use the least possible number of deals. Only after that do we compute what he pays. This matters: we are not free to use more smaller deals just because they might look cheaper. The hurry-up constraint comes first.

So first ask: what is the minimum number of powers of $3$ needed to sum to $n$?

A deal is one power of $3$:

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

Suppose some representation uses three deals of size $3^x$. Then those three deals buy

$$3\cdot 3^x = 3^{x+1}$$

watermelons total. But that is exactly one bigger deal. Replacing those three deals by one deal buys the same number of watermelons and reduces the deal count from $3$ to $1$.

So any least-deal solution cannot use a power $3$ or more times. If it did, it was leaving an easy compression on the table. Rookie mistake. Seller would love that nonsense.

Therefore, each power $3^x$ is used only $0$, $1$, or $2$ times.

That is exactly the ternary representation of $n$.

If

$$n = d_0\cdot 3^0 + d_1\cdot 3^1 + d_2\cdot 3^2 + \cdots$$

where each $d_i \in \{0,1,2\}$, then the least possible number of deals is

$$d_0 + d_1 + d_2 + \cdots.$$

And the actual deals are forced: use $d_x$ deals of size $3^x$.

Why This Is Optimal

Take any way to buy exactly $n$ watermelons using powers of $3$. If some size $3^x$ appears at least three times, combine three of them into one $3^{x+1}$ deal. This preserves the total number of watermelons and decreases the number of deals.

Repeat this until every count is $0$, $1$, or $2$. Now the counts form a valid base-$3$ representation of $n$. Base representation is unique, so these counts must be the ternary digits of $n$.

That means no representation can beat the ternary digit sum, and the ternary representation achieves it. Done.

Computing The Cost

For each ternary digit $d_x$, we pay for $d_x$ deals of size $3^x$.

The cost of one such deal is:

$$\text{cost}(x)= \begin{cases} 3, & x=0,\\ 3^{x+1}+x\cdot 3^{x-1}, & x\ge 1. \end{cases}$$

So the answer is

$$\sum_x d_x\cdot \text{cost}(x).$$

Since $n\le 10^9$, we only need powers up to around $3^{19}$, and the answer fits safely in long long.

Algorithm

1. Precompute powers of $3$.
2. For each test case:
   • Read $n$.
   • Extract ternary digits by repeatedly taking n % 3.
   • For digit position $x$, add digit * cost(x).
   • Divide n by $3$.
3. Print the answer.

Complexity

Each test case processes $O(\log_3 n)$ digits.

So the total complexity is

$$O(t\log n),$$

which is tiny for the constraints.