Created
February 4, 2019 07:11
-
-
Save Noobgam/b6ca5e59939a8518dee653bff6959f7e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <stdio.h> | |
#include <vector> | |
#include <algorithm> | |
#include <set> | |
#include <map> | |
#include <cmath> | |
#include <string> | |
#include <cstring> | |
#include <ctime> | |
#include <cassert> | |
#include <queue> | |
#include <stack> | |
#include <bitset> | |
using namespace std; | |
long long gcd(long long a, long long b) | |
{ | |
if (a < 0) | |
a = -a; | |
if (b < 0) | |
b = -b; | |
while (a && b) | |
{ | |
if (a > b) | |
a %= b; | |
else | |
b %= a; | |
} | |
return a ? a : b; | |
} | |
struct fraction | |
{ | |
long long a, b; | |
fraction() | |
{ | |
a = 0; | |
b = 1; | |
} | |
fraction(long long _a, long long _b) | |
{ | |
a = _a; | |
b = _b; | |
} | |
void relax() | |
{ | |
long long g = gcd(a, b); | |
a /= g; | |
b /= g; | |
} | |
}; | |
fraction operator +(const fraction a, const fraction b) | |
{ | |
fraction c(a.a * b.b + b.a * a.b, b.b * a.b ); | |
c.relax(); | |
return c; | |
} | |
fraction operator -(const fraction a, const fraction b) | |
{ | |
fraction c(a.a * b.b - b.a * a.b, b.b * a.b); | |
c.relax(); | |
return c; | |
} | |
fraction operator *(const fraction a, const fraction b) | |
{ | |
fraction c(a.a * b.a, b.b * a.b); | |
c.relax(); | |
return c; | |
} | |
struct polynomial | |
{ | |
vector <fraction> a; | |
polynomial() | |
{ | |
a = vector <fraction>(0); | |
} | |
polynomial(vector<fraction> &c) | |
{ | |
a = c; | |
} | |
fraction eval(fraction x) | |
{ | |
fraction temp(1, 1); | |
fraction ans; | |
for (int i = 0; i < a.size(); ++i, temp = temp * x) | |
ans = ans + temp * a[i]; | |
return ans; | |
} | |
}; | |
polynomial antiderivative(polynomial &a) | |
{ | |
vector <fraction> b; | |
b.push_back(fraction()); | |
for (int i = 0; i < a.a.size(); ++i) | |
b.push_back(a.a[i] * fraction(1, i + 1)); | |
return polynomial(b); | |
} | |
polynomial derivative(polynomial &a) | |
{ | |
vector <fraction> b; | |
for (int i = 1; i < a.a.size(); ++i) | |
b.push_back(a.a[i] * fraction(i, 1)); | |
return polynomial(b); | |
} | |
polynomial operator *(polynomial &a, polynomial &b) | |
{ | |
polynomial c; | |
c.a.resize(a.a.size() + b.a.size() - 1); | |
for (int i = 0; i < a.a.size(); ++i) | |
for (int j = 0; j < b.a.size(); ++j) | |
c.a[i + j] = c.a[i + j] + a.a[i] * b.a[j]; | |
return c; | |
} | |
polynomial operator +(polynomial &a, polynomial &b) | |
{ | |
polynomial c; | |
c.a.resize(max(a.a.size(), b.a.size())); | |
for (int i = 0; i < a.a.size(); ++i) | |
c.a[i] = c.a[i] + a.a[i]; | |
for (int j = 0; j < b.a.size(); ++j) | |
c.a[j] = c.a[j] + b.a[j]; | |
return c; | |
} | |
fraction solver(int n, vector <int> t) | |
{ | |
sort(t.begin(), t.end()); | |
fraction answer; | |
for (int i = 0; i < 1; ++i) | |
{ | |
polynomial v; | |
v.a.resize(1); | |
v.a[0] = fraction(1, 1); | |
for (int j = i; j < n; ++j) //only these things can happen on this interval, interval is [t[i - 1]..t[i]) | |
{ | |
polynomial temp; | |
temp.a.resize(2); | |
temp.a[0] = fraction({ 1, 1 }); | |
temp.a[1] = fraction({ -1, t[j] }); | |
v = v * temp; | |
} | |
v = derivative(v); | |
polynomial temp; | |
temp.a.resize(2); | |
temp.a[0] = fraction(0, 1); | |
temp.a[1] = fraction(1, 1); | |
v = v * temp; | |
v = antiderivative(v); | |
answer = answer + v.eval(fraction(t[i], 1)); | |
if (i != 0) | |
answer = answer - v.eval(fraction(t[i - 1], 1)); | |
} | |
return fraction(-answer.a, answer.b); | |
} | |
const int iterations = 1e7; | |
long double solver2(int n, vector <int> t) | |
{ | |
long double answer = 0; | |
for (int i = 0; i < iterations; ++i) | |
{ | |
long double time = t.back(); | |
for (int j = 0; j < n; ++j) | |
{ | |
long double x = rand(); | |
x /= RAND_MAX; | |
if (x * t[j] < time) | |
time = x * t[j]; | |
} | |
answer += time; | |
} | |
answer /= iterations; | |
return answer; | |
} | |
int main() | |
{ | |
ios_base::sync_with_stdio(0); | |
cin.tie(0); | |
cout.tie(0); | |
int n; | |
cin >> n; | |
vector <int> t(n); | |
for (int i = 0; i < n; ++i) | |
cin >> t[i]; | |
fraction ans = solver(n, t); | |
cout << ans.a << "/" << ans.b << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment