planes.cpp

#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;
}