← 返回题目列表

AtCoder · arc109_b

B. 日志

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

分数: 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