目录

SGU 105 - Div 3

Description

There is sequence 1, 12, 123, 1234, …, 12345678910, … . Given first $N$ elements of that sequence. You must determine amount of numbers in it that are divisible by 3.

Input

Input contains $N$ ($1\leq N\leq 2^{31} - 1$).

Output

Write answer in output file.

Sample Input

1
4

Sample Output

1
2

Analysis

由于一个数对 $3$ 取模恒等于这个数各个位上数字之和对 $3$ 取模。因此,非常容易想到的方法是找规律:

项数 $N$数列除以 $3$ 的余数答案 $ans$
1110
21201
312302
4123412
51234503
612345604
7123456714
81234567805
912345678906

由上述表格,我们可以大致的看出规律,即:$$\mathrm{ans} = \begin{cases} \mathrm{ans}, & N \mod 3 = 1\\ \mathrm{ans} + 1, & N \mod 3 = 0, 2\end{cases}$$

有了上述的讨论,我们可以很容易的写出一个暴力算法,但是考虑到 $N$ 的数据范围比较大,这并不是一个非常好的选择。

我们可以推导出数学公式来求解这个问题。观察上表(下面的除法为 C++ 意义中的整除):$$ \mathrm{ans}=\begin{cases}2N / 3, & N \mod 3 = 0\\ 2N / 3, & N \mod 3 = 1 \\ 2N / 3 + 1, & N \mod 3 = 2\end{cases}$$

把上述公式归纳成一个公式,即为 ans = 2 * N / 3 + (N % 3 == 2),此处 N % 3 == 2 的返回值为真、假,分别对应着 1 和 0。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <iostream>
 
using namespace std;
 
int main()
{
    int N;
    cin >> N;
    cout << N / 3 * 2 + (N % 3 == 2) << endl << endl;
    return 0;
}