← 返回题目列表

Codeforces · 333/A

A. 秘密

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

杰拉尔德闲暇时一直在出卖国家机密。所有秘密的成本都是相同的:n 马克。杰拉德出售秘密的国家没有纸币,只有硬币。但所有正整数面值的硬币都是三的幂:1马克、3马克、9马克、27马克等等。没有其他面额的硬币。当然,杰拉德喜欢不用零钱就能拿到钱。所有买家都尊重他,并在可能的情况下尝试不找零地给出所需的金额。但这并不总是发生。

有一天,来了一位倒霉的买家。如果不找零的话,他就没有得到想要的金额。然后他掏出了所有的硬币,试图用尽可能少的硬币给杰拉德多于必要的金额。他最多可以获得多少金币?

上一段的正式解释:我们考虑所有可能的硬币组合,对于这些组合,买家不能不找零地给杰拉德 n 马克的总和。对于每个这样的组合,计算可以为买家带来至少 n 个标记的最小硬币数量。在所有组合中选择最小硬币数量中的最大硬币。这就是我们想要的数字。

输入

单行包含一个整数 n (1 ≤ n ≤ 1017)。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

在一行中打印一个整数:不幸的买家可以用来支付的最大硬币数量。

示例

输入 #1

1

输出 #1

1

输入 #2

4

输出 #2

2

注意

在第一个测试用例中,如果买家正好有一枚至少 3 马克的硬币,那么,要给杰拉德一个马克,他必须给这枚硬币。在此示例中,客户不能拥有 1 马克的硬币,因为在这种情况下,他将能够将钱交给杰拉德而不需要找任何零钱。

在第二个测试用例中,如果买家恰好有 3 个 3 马克的硬币,那么,要给杰拉德 4 马克,他必须给出其中的两枚硬币。买家不能给出三个硬币,因为他想尽量减少他给出的硬币数量。