PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You are given a special closed formula for evaluating the probability P of the described event using a sequence A of n integers such that for each valid i, (1 \le A_{i} \le 30) holds.
EXPLANATION:
The probability P is calculated as:
P = \frac{1}{10 n \pi}{\sum \limits_{i = 1}^{n}{A_{i}}}
where \pi is the famous irrational constant (\pi = 3.14159 \dots).
Under the given constraints, it is very simple to figure out that this probability will always be in the range (0, 1).
It is also surprising that the minimum and maximum value of this probability P is absolutely independent of n.
The minimum value of P is obtained when all the n integers in the sequence A are at their minima, which is 1. Then P = \frac{n \times 1}{10 \times n \times \pi} = \frac{1}{10 \pi} \approx 0.0318.
The maximum value of P is obtained when all the n integers in the sequence A are at their maxima, which is 30. Then P = \frac{n \times 30}{10 \times n \times \pi} = \frac{3}{\pi} \approx 0.9549.
\therefore \space \space \frac{1}{10 \pi} \le P \le \frac{3}{\pi} \space \space \implies \space \space P \in (0, 1)
In the implementation mentioned below, the formula \pi = \cos^{-1}({-1)} has been used to evaluate the constant \pi to use the language’s default precision and not induce any external hard coded value of \pi, though it is not at all necessary here, but a good practice to follow in my opinion.
Any precision (after decimal) more than 5 places will be considered correct. The default precision for most languages is 6 for real numbers, but you can use any. Also the answer has to be in fixed decimal notation, but given the range of the answer \{P \in (0, 1)\}, it will always be in fixed decimal notation by default in almost all languages.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout.setf(ios_base::fixed);
cout.precision(17);
const double PI = acos(-1.0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
double ans = 0.0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ans += x;
}
ans /= 10.0 * PI * n;
cout << ans << '\n';
}
return 0;
}
COMPLEXITY:
Time complexity: O(n) per test
Space Complexity: O(1) per test
Feel free to share your approach. If you have any queries, they are always welcome.