Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds
Remi likes recording the number of times the 3 digit occurs in integers. For example, the integer 3032 has two 3 digits.
While counting from 1 up to some integer N inclusive, Remi records the total number of 3s encountered. Your task is to write a program that takes an integer N as input and prints the total number of 3s recorded by Remi for all integers together between 1 to N inclusive. The term
inclusive means that Remi includes the integers 1 and N when counting.
There will be a single line containing the integer N.
You should print a single integer which is the total number of 3s recorded by Remi while counting from 1 to N inclusive.
- Subtask 1 (+30%): 1 \le N \le 20.
- Subtask 2 (+30%): 1 \le N \le 20\,000.
- Subtask 3 (+20%): 1 \le N \le 2\,000\,000\,000.
- Subtask 4 (+20%): 1 \le N \le 2\,000\,000\,000\,000\,000.
In the sequence 1, 2, 3, 4, where N=4, there is only one number that contains a digit 3, which is 3 itself. The total number of recorded 3s is 1.
In the sequence 1, ..., 13 there are two integers 3 and 13 that each contain one 3, giving 2 in total.
In the sequence 1, ..., 72 there are 16 integers that contain 3s. One of these integers contains two 3s (this number is 33), the rest have only a single 3. The total is then 17. Note that Sample 3 is not part of the first subtask.
If you are using a type sensitive language such as C, C++, C#, or Java then be sure to use variables, functions, and methods that support 64-bit precision. The answer does not exceed the maximum value of a signed 64-bit integer in any test case.
Haskell programmers are ineligible for free advice.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3