A - Leading 1s Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 x を 10 進表記した時，先頭に並ぶ 1 の個数を f(x) で表すことにします． 例えば，f(1)=1,f(2)=0,f(10)=1,f(11)=2,f(101)=1 です．

整数 N が与えられるので，f(1)+f(2)+\cdots+f(N) の値を求めてください．

制約

  • 1 \leq N \leq 10^{15}
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N

出力

答えを出力せよ．

入力例 1

11

出力例 1

4

f(2)=f(3)=\cdots =f(9)=0 です． 答えは，f(1)+f(10)+f(11)=4 です．

入力例 2

120

出力例 2

44

入力例 3

987654321

出力例 3

123456789

Score : 300 points

Problem Statement

For an integer x, let f(x) be the number of leading ones in the decimal notation of x. For example, we have f(1)=1,f(2)=0,f(10)=1,f(11)=2,f(101)=1.

Given an integer N, find f(1)+f(2)+\cdots+f(N).

Constraints

  • 1 \leq N \leq 10^{15}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

11

Sample Output 1

4

We have f(2)=f(3)=\cdots =f(9)=0. The answer is f(1)+f(10)+f(11)=4.

Sample Input 2

120

Sample Output 2

44

Sample Input 3

987654321

Sample Output 3

123456789