HackerRank Geometry – Hard Homework

Challenge: Hard Homework

Scor cont: 75.0 / 75

Submission status: Accepted

Submission score: 1.0

Submission ID: 464761214

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/hard-homework/problem

Cerinta

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$.

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.

Constraints

* $3 \leq n \leq 3 \times 10^6$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    int maxInt = (n - 2) / 2;      // for even a: m = (a-2)/2
    int maxHalf = (n - 1) / 2;     // for odd a=2p+1: p in [1..(n-1)/2]

    vector<long double> intMax(maxInt + 1), intMin(maxInt + 1);
    if (maxInt >= 0) {
        long double v0 = cosl(0.0L);
        intMax[0] = intMin[0] = v0;
        for (int i = 1; i <= maxInt; ++i) {
            long double v = cosl((long double)i);
            intMax[i] = max(intMax[i - 1], v);
            intMin[i] = min(intMin[i - 1], v);
        }
    }

    vector<long double> halfMax(maxHalf + 1), halfMin(maxHalf + 1);
    if (maxHalf >= 1) {
        long double v1 = cosl(0.5L);
        halfMax[1] = halfMin[1] = v1;
        for (int p = 2; p <= maxHalf; ++p) {
            long double v = cosl((long double)p - 0.5L);
            halfMax[p] = max(halfMax[p - 1], v);
            halfMin[p] = min(halfMin[p - 1], v);
        }
    }

    long double ans = -1e100L;

    for (int a = 2; a <= n - 1; ++a) {
        long double s = sinl((long double)a * 0.5L);
        long double c;

        if ((a & 1) == 0) {
            int p = a / 2;
            int m = p - 1; // >=0
            c = (s >= 0 ? intMax[m] : intMin[m]);
        } else {
            int p = a / 2; // a=2p+1, p>=1
            c = (s >= 0 ? halfMax[p] : halfMin[p]);
        }

        long double bestPair = 2.0L * s * c;
        long double cur = bestPair + sinl((long double)(n - a));
        if (cur > ans) ans = cur;
    }

    cout.setf(std::ios::fixed);
    cout << setprecision(9) << (double)ans << '\n';
    return 0;
}