分数: 400 点
问题陈述
Snuke 正在东京一家名为 109 的商店购买一些原木。 他想要 n 日志:长度之一 1,长度之一 2, ...,以及长度之一 n。 店里有 n+1 库存原木:长度之一 1,长度之一 2, \dots,以及长度之一 n+1。这些原木的每一个售价 1 日元(日本的货币)。
购买这些原木后,他可以多次切割这些原木。也就是说,他可以获得 k 长度日志 L_1, \dots, L_k 来自长度的日志 L,其中 L = L_1 + \dots + L_k。他还可以扔掉不需要的原木。
Snuke想要花尽可能少的钱来获得他想要的日志。 找出获得所需的最低金额 n 长度日志 1 to n.
约束
- 1 \leq n \leq 10^{18}
输入
输入由标准输入按以下格式给出:
n
输出
打印获得所需的最低金额 n 长度日志 1 to n.
示例输入 1
4
示例输出 1
3
获取他想要的日志的一种方法 3 日元是:
- 购买长度的原木 2, 4,和 5.
- 切割长度的日志 5 分成两个长度的对数 1 每个长度的对数 3.
- 扔掉一根长度为 1 的原木 1.
示例输入 2
109109109109109109
示例输出 2
109109108641970782