Aaron is struggling with trigonometric functions, so his teacher gave him extra homework. Given an integer, $n$, he must answer the following question:

What is the maximum value of $sin(x)+sin(y)+sin(z)$, where $x}$, $y$, and $z$ are positive integers and $x+y+z=n$?

Help Aaron by finding this maximal value and printing it correct to ${9}$ decimal places.

Input Format

A single positive integer denoting $n$.

Constraints

$3\leq n\leq3\times10^{6}$

Output Format

Print a single real number rounded to a scale of exactly ${9}$ decimal places (e.g., $0.123456789$) denoting the maximum possible value.

Sample Input 0
3

Sample Output 0
2.524412954

Explanation 0

The only possible variant is $x=1$, $y=1$, and $z=1$, which gives us $sin(1)+sin(1)+sin(1)=2.524412954$

Difficulty: HARD
Tags: Geometry

Starter code:

Solutions:
from math import sin, pi
from itertools import product
from random import shuffle
n = int(input())
a = list(range(1, n - 1))
a.sort(key=lambda v: v % (pi * 2))
lena = len(a)
offsets = list(product(range(-500, 501), range(-500, 501)))
shuffle(offsets)
last_offset = offsets[len(offsets) - 1]
i = 0
j = lena // 2
sm = -4
while True:
	for (di, dj) in offsets:
		x = a[(i + lena + di) % lena]
		y = a[(j + lena + dj) % lena]
		z = n - x - y
		sm2 = sin(x) + sin(y) + sin(z)
		if sm2 > sm and z > 0:
			i = (i + lena + di) % lena
			j = (j + lena + dj) % lena
			sm = sm2
			break
	if (di, dj) == last_offset:
		break
print('%.9f' % sm)


from math import *

def fast(n):
	cosEvenIncr = list(sorted([(cos(i / 2.0), i) for i in range(2, n, 2)]))
	cosEvenDecr = list(reversed(cosEvenIncr))
	cosOddIncr = list(sorted([(cos(i / 2.0), i) for i in range(1, n, 2)]))
	cosOddDecr = list(reversed(cosOddIncr))
	maxV = -3
	for x in range(1, n - 1):
		sinX = sin(x)
		if sinX + 2 < maxV:
			continue
		yz = n - x
		k = 2 * sin(yz / 2.0)
		if k < 0:
			if yz % 2 == 0:
				while cosEvenDecr[-1][1] > yz - 2:
					cosEvenDecr.pop()
				(c, d) = cosEvenDecr[-1]
			else:
				while cosOddDecr[-1][1] > yz - 2:
					cosOddDecr.pop()
				(c, d) = cosOddDecr[-1]
		elif yz % 2 == 0:
			(c, d) = (1, 0)
		else:
			while cosOddIncr[-1][1] > yz - 2:
				cosOddIncr.pop()
			(c, d) = cosOddIncr[-1]
		maxV = max(maxV, sinX + k * c)
	return maxV
print('{:1.9f}'.format(fast(int(input()))))


from math import sin, cos
n = int(input())
maxc = [False, False, 1, max(cos(-1 / 2), cos(1 / 2)), 1]
for i in range(5, n):
	maxc.append(max(cos(i / 2 - 1), cos(1 - i / 2), maxc[-2]))
res = -3
for i in range(1, n - 1):
	res = max(res, sin(i) + 2 * sin((n - i) / 2) * maxc[n - i])
print('{:.9f}'.format(res))


import math
n = int(input())
p = []
for x in range(1, n // 3 + 1):
	a = math.sin(n - x)
	b = 1 - math.cos(n - x)
	c = math.sin(x) + math.sqrt(a * a + b * b)
	p.append((c, x))
p.sort(reverse=True)
best = -3
for (c, x) in p:
	if c <= best:
		break
	nx = n - x
	sx = math.sin(x)
	for y in range(1, nx // 2 + 1):
		s = sx + math.sin(y) + math.sin(nx - y)
		if best < s:
			best = s
print('{:.9f}'.format(best))


from math import sin
n = int(input())
(s, x, y, z) = max(((2 * sin(x) + sin(n - 2 * x), x, x, n - 2 * x) for x in range(1, n // 3 + 1)))
(s, x, y, z) = max(((sin(x) + sin(y) + sin(n - x - y), x, y, n - x - y) for y in range(1, (n - x) // 2 + 1)))
(s, x, y, z) = max(((sin(x) + sin(y) + sin(n - x - y), x, y, n - x - y) for x in range(1, (n - y) // 2 + 1)))
(s, x, y, z) = max(((sin(x) + sin(n - x - z) + sin(z), x, n - x - z, z) for x in range(1, (n - z) // 2 + 1)))
print('%.9f' % (sin(x) + sin(y) + sin(z)))


from math import *
N = int(input())
CosMin = [cos(i / 2.0) for i in range(N + 1)]
CosMax = CosMin[:]
for i in range(2, N + 1):
	CosMin[i] = min(CosMin[i], CosMin[i - 2])
	CosMax[i] = max(CosMax[i], CosMax[i - 2])
res = float('-inf')
for z in range(1, N - 1):
	n = N - z
	sn = 2.0 * sin(n / 2.0)
	if sn > 0:
		x = sn * CosMax[n - 2] + sin(z)
	else:
		x = sn * CosMin[n - 2] + sin(z)
	res = max(res, x)
print('{:.9f}'.format(round(res, 9)))


from math import sin, cos
n = int(input())
(temp, max_sin) = (-100, -100)
for xpy in range(2, n, 2):
	temp = max(temp, cos(xpy / 2 - 1))
	max_sin = max(max_sin, 2 * sin(xpy / 2) * temp + sin(n - xpy))
temp = -100
for xpy in range(3, n, 2):
	temp = max(temp, cos(xpy / 2 - 1))
	max_sin = max(max_sin, 2 * sin(xpy / 2) * temp + sin(n - xpy))
print(round(max_sin, 9))


from math import sin
n = int(input())
l = []
(x, y, z, l1) = (0, 0, 0, 0)
for i in range(1, n // 2 + 1):
	t = 2 * sin(i) + sin(n - 2 * i)
	l.append(t)
	if t > l1:
		l1 = t
		x = i
		y = i
		z = n - 2 * x
for j in range(1, (n - x) // 2 + 1):
	t = sin(x) + sin(j) + sin(n - x - j)
	l.append(t)
	if t > l1:
		l1 = t
		y = j
		z = n - x - j
for k in range(1, (n - y) // 2 + 1):
	t = sin(k) + sin(y) + sin(n - k - y)
	l.append(t)
for m in range(1, (n - z) // 2 + 1):
	t = sin(m) + sin(n - m - z) + sin(z)
	l.append(t)
print('%.9f' % max(l))


import math
sin = [math.sin(x) for x in range(3000000)]
cos = [math.cos(x) for x in range(3000000)]

def direct_solution(n):
	(rx, ry, rz) = (1, 1, n - 2)
	result = sin[rx] + sin[ry] + sin[rz]
	for x in range(1, n // 3 + 1):
		for y in range(x, (n - x) // 2 + 1):
			z = n - x - y
			if z < 1:
				continue
			r = sin[x] + sin[y] + sin[z]
			if r > result:
				result = r
				(rx, ry, rz) = (x, y, z)
	return result

def fast_solution(n):
	result = sin[1] + sin[1] + sin[n - 2]
	minc = 1
	for c in range(1, n // 2 + 1):
		minc = min(minc, cos[c - 1])
		z = n - c - c
		if z < 1:
			continue
		if sin[c] > 0:
			(x, y, z) = (c, c, n - c - c)
			r = sin[x] + sin[y] + sin[z]
			if r > result:
				result = r
		else:
			r = sin[z] + 2 * sin[c] * minc
			if r > result:
				result = r
	return result
n = int(input())
print(fast_solution(n))