10145. Increasing sines

Find and print such n integers x₁, x₂, ..., x_n that the sequence of their sines is strictly increasing:

sin(x₁) < sin(x₂) < ... < sin(x_n)

Input. One positive integer n (n ≤ 10⁴).

Output. Print in one line a sequence of integers x₁, x₂, ..., x_n that satisfy the condition of the problem. The absolute value of each number must not exceed 2³¹ – 1 (|x_i| < 2³¹).

Explanation. For the provided example, the inequality sin(-8) < sin(0) < sin(9) < sin(1) is true because it is equivalent to -0.989 < 0 < 0.412 < 0.841.

Sample input	Sample output
4	-8 0 9 1

SOLUTION

mathematics

Algorithm analysis

Let’s construct the required sequence in a constructive manner. Since the sine function is periodic with a period of 2π, we will look for it in the form of sin(k(2π + ɛ)), where k = 0, 1, 2, … . We need to find such a positive integer A for which there exists an integer k such that A = 2πk + ɛ, where ɛ is as small as possible. For example, if we check values of A from 1 to 1000, the smallest ε is achieved when A = 710. In this case, 710 ≈ 2π * 113 + 0.00006028.

Let A = 710. Consider the sequence

sin(A), sin(2A), sin(3A), …, sin(nA)

The values of the elements in this sequence are

sin(2π * 113 + ɛ), sin(2*2π * 113 + 2*ɛ), sin(3*2π * 113 + 3*ɛ), …,

sin(n*2π * 113 + n*ɛ)

or, considering the periodicity, these values are equivalent to

sin(ɛ), sin(2*ɛ), sin(3*ɛ), …, sin(n*ɛ)

The function sin(x) is increasing on the interval x ∈ [0; π/2]. For the sequence of the above real numbers to be monotonically increasing, it is sufficient to satisfy the inequality: n * ɛ ≤ π / 2. Substituting n = 10000 and ɛ = 0.00006028, we get: 10000 * 0.00006028 ≤ π/2 or 0.6028 ≤ 1.57, which is true. Therefore, by this method, it is possible to find 10⁴ required integers.

Algorithm realization

Read the input value of n.

scanf("%d", &n);

On the interval [1..1000], we find such a positive integer A for which, when represented as A = 2πk + ɛ, the value of ε will be the smallest.

bestA = 0;

bestE = 2 * PI;

for (a = 1; a < 1000; a++)

{

e = fmod(a, 2.0 * PI);

if (e < bestE)

{

bestE = e;

bestA = a;

}

}

The value of x = bestA will be 710.

x = bestA;

Print the desired sequence: 0 * 710, 1 * 710, 2 * 710, …, (n – 1) * 710.

for (i = 0; i < n; i++)

printf("%d ", x*i);

printf("\n");