Bí mật quốc gia

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Gerald bán bí mật quốc gia, mỗi bí mật có giá $n$ mark. Quốc gia nơi Gerald bán bí mật không có tiền giấy, chỉ có tiền xu mệnh giá là lũy thừa của $3$ : $1, 3, 9, 27, \dots$ mark — không có mệnh giá nào khác.

Một khách hàng đến mua bí mật nhưng không có tổ hợp tiền xu nào trả đúng $n$ mark. Khi đó, anh ta sẽ lấy ra tất cả các đồng xu của mình và cố trả một số tiền lớn hơn hoặc bằng $n$ với số đồng xu ít nhất có thể.

Trong tất cả các tổ hợp đồng xu mà người mua không thể trả đúng $n$ mark, hãy tìm tổ hợp khiến số đồng xu tối thiểu cần dùng để trả ít nhất $n$ mark là lớn nhất. Hãy in ra giá trị lớn nhất đó.

Dữ liệu vào

Một số nguyên duy nhất $n$ .

Dữ liệu ra

Một số nguyên — số đồng xu nhiều nhất mà người mua không may có thể phải dùng.

Ràng buộc

$1 \leq n \leq 10^{17}$

Ví dụ

Input	Output	Giải thích
1	1	Nếu khách hàng có đúng một đồng xu mệnh giá ít nhất $3$ mark, anh ta phải đưa đồng xu đó để trả $1$ mark. Anh ta không thể có đồng xu mệnh giá $1$ vì khi đó sẽ trả đúng được.
4	2	Nếu khách hàng có đúng ba đồng xu $3$ mark, để trả $4$ mark anh ta sẽ phải đưa hai đồng (tổng $6$ mark). Không thể đưa ba đồng vì anh ta muốn ít đồng nhất.
10	4	Khách có thể có ba đồng $3$ mark — không đủ; bốn đồng $3$ mark cho $12 \geq 10$ với $4$ đồng là kết quả tối đa.

Bình luận

Không có bình luận tại thời điểm này.