176 lines
4.1 KiB
C++
176 lines
4.1 KiB
C++
#include <bits/stdc++.h>
|
|
|
|
#define FOR(i, n) for(lli i = 0; i < (lli)(n); ++i)
|
|
#define FORU(i, a, b) for(lli i = (lli)(a); i < (lli)(b); ++i)
|
|
#define FORD(i, a, b) for(lli i = (lli)(b)-1; i >= (lli)(a); --i)
|
|
#define ALL(x) (x).begin(), (x).end()
|
|
|
|
#define X(A) get<0>(A)
|
|
#define Y(A) get<1>(A)
|
|
#define Z(A) get<2>(A)
|
|
#define W(A) get<3>(A)
|
|
|
|
#define mt make_tuple
|
|
#define pb push_back
|
|
|
|
|
|
|
|
using namespace std;
|
|
using lli = long long int;
|
|
|
|
using pii = tuple<lli, lli>;
|
|
using piii = tuple<lli, lli, lli>;
|
|
using vi = vector<lli>;
|
|
using vii = vector<pii>;
|
|
using viii = vector<piii>;
|
|
using vvi = vector<vi>;
|
|
using vvii = vector<vii>;
|
|
using vviii = vector<viii>;
|
|
using vb = vector<bool>;
|
|
using vvb = vector<vb>;
|
|
|
|
const lli INFTY = ((1ll << 60) - 1) * 2;
|
|
|
|
// =====
|
|
|
|
struct Evt {
|
|
enum {
|
|
JACKPOT, ENTRY
|
|
} type;
|
|
|
|
lli date;
|
|
lli nbPers;
|
|
|
|
bool operator<(const Evt& e) const {
|
|
if(date == e.date)
|
|
return type == Evt::ENTRY;
|
|
return date < e.date;
|
|
}
|
|
};
|
|
|
|
lli gcd(lli a, lli b) {
|
|
if(b == 0)
|
|
return a;
|
|
return gcd(b, a % b);
|
|
}
|
|
|
|
struct Frac {
|
|
Frac() : num(0), den(1) {}
|
|
Frac(lli n, lli d): num(n), den(d) { simpl(); }
|
|
lli num, den;
|
|
|
|
void simpl() {
|
|
lli g = gcd(num, den);
|
|
num /= g;
|
|
den /= g;
|
|
}
|
|
|
|
/*
|
|
Frac operator+(const Frac& b) {
|
|
return Frac(b.den * num + den * b.num, den * b.den);
|
|
}
|
|
*/
|
|
|
|
double val() const {
|
|
return ((double)num / (double)den);
|
|
}
|
|
|
|
Frac& operator*=(const Frac& b) {
|
|
num *= b.num;
|
|
den *= b.den;
|
|
simpl();
|
|
return *this;
|
|
}
|
|
|
|
double operator*(double b) const {
|
|
return b * val();
|
|
}
|
|
};
|
|
|
|
vector<lli> joinTimes;
|
|
vector<Evt> jackpots;
|
|
lli ticketPrice, jackpotVal;
|
|
map<lli, double> expec;
|
|
|
|
void getJackpots() {
|
|
lli slope = 0, cMoney = 0;
|
|
vector<lli> orderedJoins(joinTimes);
|
|
sort(orderedJoins.begin(), orderedJoins.end());
|
|
orderedJoins.push_back(INFTY);
|
|
|
|
lli pEvent = 0;
|
|
|
|
for(size_t j = 0; j < orderedJoins.size() - 1; ++j) {
|
|
lli join = orderedJoins[j];
|
|
lli nEvent = orderedJoins[j+1];
|
|
cMoney += (join - pEvent) * slope;
|
|
slope += ticketPrice;
|
|
pEvent = join;
|
|
while(cMoney + (nEvent - pEvent - 1) * slope >= jackpotVal) {
|
|
jackpots.push_back(Evt({Evt::JACKPOT,
|
|
(jackpotVal - cMoney + slope - 1) / slope + pEvent,
|
|
0}));
|
|
pEvent = jackpots.back().date;
|
|
slope -= ticketPrice;
|
|
cMoney = 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
void fillExpec() {
|
|
vector<Evt> events(jackpots);
|
|
for(lli join: joinTimes)
|
|
events.push_back(Evt({Evt::ENTRY, join, 0}));
|
|
sort(events.begin(), events.end());
|
|
int cPers = 0;
|
|
for(Evt& evt: events) {
|
|
cPers += (evt.type == Evt::ENTRY) ? 1 : -1;
|
|
evt.nbPers = cPers + ((evt.type == Evt::JACKPOT)?1:0);
|
|
}
|
|
|
|
double cExpec = 0;
|
|
Frac cProd;
|
|
for(auto evtIt = events.begin(); evtIt != events.end(); ++evtIt) {
|
|
const Evt& evt = *evtIt;
|
|
if(evt.nbPers == 1 && evt.type == Evt::ENTRY) {
|
|
cProd = Frac(1, 1);
|
|
cExpec = 0;
|
|
for(auto cJack = evtIt; cJack != events.end(); ++cJack) {
|
|
if(cJack->type != Evt::JACKPOT)
|
|
continue;
|
|
|
|
cExpec +=
|
|
cProd * ((double)cJack->date) / ((double)cJack->nbPers);
|
|
cProd *= Frac(cJack->nbPers - 1, cJack->nbPers);
|
|
|
|
if(cJack->nbPers == 1)
|
|
break;
|
|
}
|
|
}
|
|
|
|
if(evt.type == Evt::JACKPOT) {
|
|
cExpec -= ((double)evt.date) / ((double)evt.nbPers);
|
|
cExpec *= ((double)evt.nbPers) / ((double)evt.nbPers - 1.);
|
|
}
|
|
else {
|
|
expec.insert({evt.date, ticketPrice * (cExpec - evt.date)});
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
int nbPlayers;
|
|
scanf("%d%lld%lld", &nbPlayers, &ticketPrice, &jackpotVal);
|
|
ticketPrice /= 2;
|
|
joinTimes.resize(nbPlayers);
|
|
FOR(i, nbPlayers)
|
|
scanf("%lld", &(joinTimes[i]));
|
|
getJackpots();
|
|
fillExpec();
|
|
|
|
for(const lli& joinTime: joinTimes) {
|
|
printf("%.15lf\n", expec[joinTime]);
|
|
}
|
|
}
|
|
|