CodeForces 48C D - The Race （Fraction，数学）

每个加油的站可以确定一个alpha的上下界，比如，第i次加油站a[i]，前面加了i次油，a[i]*10≤ alpha*i <(a[i]+1)*10。

取最大的下界，取最小的上界，看看两者之间的满足条件的下一个加油站是否唯一。

因为可以用分数，所有就没用double了

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }

struct Fra

{

    ll p,q;

    Fra(ll x = ,ll y = ):p(x),q(y){ normal(p,q); }

    void normal(ll &p,ll &q) { ll g = gcd(p,q); p/=g; q/=g; }

    Fra operator = (int x) {  p = x; q = ; return *this; }

    Fra operator = (ll x) { p = x; q = ; return *this; }

    Fra operator - () { return {-p,q}; }

    Fra operator + (Fra &r) {

        ll m,n;

        m = p*r.q+r.p*q;

        n = q*r.q;

        normal(m,n);

        return {m,n};

    }

    Fra operator += (Fra& r) { return *this = *this+r; }

    Fra operator - (Fra &r) { return (-r) + *this; }

    Fra operator -= (Fra &r) { return *this = *this-r; }

    Fra operator * (Fra &r) {

        ll m,n;

        m = p*r.p;

        n = q*r.q;

        normal(m,n);

        return {m,n};

    }

    Fra operator *= (Fra &r) { return (*this) = (*this)*r; }

    Fra operator /(Fra &r) { return Fra(r.q,r.p) * (*this); }

    Fra operator /=(Fra &r) { return (*this) = (*this)/r; }

    bool operator == (const Fra& r) const { return p*r.q == r.p*q; }

    bool operator < (const Fra& r) const { return  p*r.q < r.p*q; }

    void print() { normal(p,q); if(q<)q = -q,p = -p; printf("%lld/%lld\n",p,q); }

};

const int maxn = 1e3+;

const ll INF = 1e16;

int main()

{

    //freopen("in.txt","r",stdin);

    int n; scanf("%d",&n);

    Fra Low(),High(INF);

    for(int i = ; i <= n; i++){

        int t; scanf("%d",&t);

        Low = max(Fra(t*,i),Low);

        High = min(Fra(t*+,i),High);

    }

    Low = Fra(n+)*Low;

    High = Fra(n+)*High;

    int u = (High.p-)/High.q;

    int d = (Low.p)/Low.q;

    if(u/ != d/) {

        puts("not unique");

    }else {

        printf("unique\n%d",d/);

    }

    return ;

}