/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
すぬけ君は、渋谷の丸太やさんに丸太を買いに来ました。 すぬけ君は長さ 1 から n までの n 種類の丸太が 1 本ずつほしいです。 丸太やさんには、長さ 1 から n+1 までの n+1 種類の丸太がそれぞれ 1 円で売られています。どの丸太の在庫も 1 本ずつしかありません。
すぬけ君は買った丸太を切る作業を好きなだけ行えます。つまり、L = L_1 + \dots + L_k であるとき、長さ L の丸太 1 本から、長さ L_1, \dots, L_k の k 本の丸太を作る作業を何度でもできます。また、不要な丸太を捨てることができます。
すぬけ君はできるだけ安く丸太を手に入れたいです。 長さ 1 から n までの n 種類の丸太を 1 本ずつ手に入れるために必要な最小の金額を求めてください。
制約
- 1 \leq n \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
n
出力
長さ 1 から n までの n 種類の丸太を 1 本ずつ手に入れるための最小金額を出力せよ。
入力例 1
4
出力例 1
3
例えば次のようにすると 3 円でほしい丸太がすべて手に入ります。
- 長さ 2,4,5 の丸太を買う
- 長さ 5 の丸太を切って 長さ 1 の丸太 2 本と長さ 3 の丸太を作る
- 長さ 1 の丸太を 1 本捨てる
入力例 2
109109109109109109
出力例 2
109109108641970782
Score : 400 points
Problem Statement
Snuke is visiting a shop in Tokyo called 109 to buy some logs. He wants n logs: one of length 1, one of length 2, ..., and one of length n. The shop has n+1 logs in stock: one of length 1, one of length 2, \dots, and one of length n+1. Each of these logs is sold for 1 yen (the currency of Japan).
He can cut these logs as many times as he wants after buying them. That is, he can get k logs of length L_1, \dots, L_k from a log of length L, where L = L_1 + \dots + L_k. He can also throw away unwanted logs.
Snuke wants to spend as little money as possible to get the logs he wants. Find the minimum amount of money needed to get n logs of length 1 to n.
Constraints
- 1 \leq n \leq 10^{18}
Input
Input is given from Standard Input in the following format:
n
Output
Print the minimum amount of money needed to get n logs of length 1 to n.
Sample Input 1
4
Sample Output 1
3
One way to get the logs he wants with 3 yen is:
- Buy logs of length 2, 4, and 5.
- Cut the log of length 5 into two logs of length 1 each and a log of length 3.
- Throw away one of the logs of length 1.
Sample Input 2
109109109109109109
Sample Output 2
109109108641970782