← 返回题目列表

Codeforces · 2132/C1

C1. 狡猾的卖家(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。简单版本与困难版本的不同之处在于,它需要用最少的交易次数确定最小成本,而困难版本则需要用有限的交易次数确定最小成本。

狡猾的卖家卖掉了三个西瓜而不是一个后,他决定增加利润——也就是说,他买了更多的西瓜。现在他可以以 $$$3^{x+1} + x \cdot 3^{x-1}$$$ 的价格出售 $$$3^x$$$ 西瓜,其中 $$$x$$$ 是一个非负整数。这样的销售称为交易。

一位精明的买家来找他,但他的时间非常少。因此,他想买 $$$n$$$ 西瓜,使得 最少 可能的交易数量。

买家很着急,因此请您确定他必须向卖家支付 $$$n$$$ 西瓜的最低硬币数量,考虑到他将在 最少 可能的交易数量。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。每个测试用例的描述如下。

每个测试用例的一行中,有一个整数 $$$n$$$ $$$(1 \le n \le 10^9)$$$ — 需要购买多少个西瓜。

输出

对于每个测试用例,输出一个整数——西瓜的最小成本。

示例

输入
复制

7
1
3
8
2
10
20
260010000

输出
复制

3
10
26
6
36
72
2250964728

注意

请注意,购买超出需要的西瓜是没有意义的,因此我们不会考虑西瓜数量超出需要的交易。

让我们考虑一下前两个交易选项的成本:

交易 A:$$$1$$$ 西瓜 — $$$3$$$ 硬币。

交易 B:$$$3$$$ 西瓜 — $$$10$$$ 硬币。

在第一个示例中,购买 $$$1$$$ 西瓜的唯一方法是使用交易 A,因此答案是 $$$3$$$。

在第二个示例中,您可以使用单个交易 B 以 $$$10$$$ 硬币购买 $$$3$$$ 西瓜。

在第三个示例中,您可以进行 $$$2$$$ 交易 A 和 $$$2$$$ 交易 B,总共花费 $$$26$$$ 硬币。如果我们进行 $$$3$$$ 交易,我们可以获得 $$$3$$$、$$$5$$$、$$$7$$$ 或 $$$9$$$ 西瓜。如果我们的交易少于 $$$3$$$,我们将获得不超过 $$$6$$$ 西瓜,这意味着不可能以低于 $$$4$$$ 的交易购买 $$$8$$$ 西瓜。