Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
You are the owner of a bakery and you have mm employees who serve the customers.
When a customer enters the bakery, he waits in line behind other customers who are waiting (or he is the first of the line if there are no other customers waiting).
Whenever there is an employee who is not serving anybody and there is at least one customer waiting in line, one employee immediately starts serving the first person in the line (who, therefore, leaves the line). Serving a customer requires exactly dd seconds.
The waiting time of a customer is the number of seconds elapsed between his entrance in the bakery and the moment someone starts serving him.
You have just opened the bakery today, and you know that, for each i=0,1,…,n−1i=0,1,…,n−1, with probability pp a customer will enter the bakery exactly ii seconds after the opening (these nn events are independent and the probability pp is the same for all of them).
What is the expected value of the total waiting time of all the customers (that is, the sum of the waiting times of all the customers)?
Print a single real number, the expected value of the total waiting time of all the customers. Your answer is considered correct if its relative or absolute error does not exceed 10−610−6.
2 1 5 0.4000
0.6400000000
There is only one employee, it requires 55 seconds to serve a customer and the probability that a customer enters at a given second is 0.40.4.
The total waiting time is 00 unless a customer enters at second 00 (and is immediately served) and another customer enters after one second and has to wait for 5−1=45−1=4 seconds before being served. The probability of this series of events is 0.420.42; hence the expected total waiting times is 0.42⋅4=0.640.42⋅4=0.64.
3 2 1000 0.5000
124.7500000000
If there are in total at most 22 customers, then noone waits since there are two employees. Hence, the total waiting time is 00 unless there are 33 customers, which happens with probability 0.530.53. In such case, the last customer waits for 1000−2=9981000−2=998 seconds. Hence the answer is 0.53⋅998=124.750.53⋅998=124.75.
5 3 9 0.5891
2.1875381171
40 10 30 0.4567
86.7734103628
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
// Actual solution is at the bottom
#undef NDEBUG
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
// AtCoder library from https://github.com/atcoder/ac-library
// #include "../atcoder/all"
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef int64_t int64;
typedef pair<int, int> ii;
const double BUBEN = 1e-13;
class QueueAtTheBakery {
public:
void solveOne() {
int n, m, d;
cin >> n >> m >> d;
double p;
cin >> p;
double q = 1 - p;
/*vector<vector<double>> pJump(m + 1, vector<double>(n + 1));
pJump[0][0] = 1.0;
vector<double> pr(m);
pr[0] = 1;
for (int time = 1; time <= n; ++time) {
vector<double> npr(m);
for (int old = 0; old < m; ++old) {
npr[old] += q * pr[old];
pJump[old + 1][time] = p * pr[old];
if (old + 1 < m) {
npr[old + 1] += p * pr[old];
}
}
pr = npr;
}*/
vector<vector<double>> prd(d + 1);
vector<vector<double>> bonus(d + 1, vector<double>(m));
prd[0] = {1.0};
for (int i = 0; i < d; ++i) {
prd[i + 1].resize(prd[i].size() + 1);
for (int w = 0; w < m; ++w) bonus[i + 1][w] = bonus[i][w];
for (int j = 0; j < prd[i].size(); ++j) {
prd[i + 1][j + 1] += prd[i][j] * p;
int w = (m - j - 1) % m;
if (w < 0) w += m;
bonus[i + 1][w] += (d - 1 - i) * prd[i][j] * p;
prd[i + 1][j] += prd[i][j] * q;
}
}
vector<vector<int>> iprd(d + 1);
for (int i = 0; i <= d; ++i) {
for (int j = 0; j < prd[i].size(); ++j) {
if (prd[i][j] > BUBEN) iprd[i].push_back(j);
}
sort(all(iprd[i]), [&](int a, int b) {
return prd[i][a] > prd[i][b];
});
}
double ans = 0;
vector<vector<double>> prob(d + 1, vector<double>(n + m + 1));
vector<vector<uint16_t>> pgen(d + 1, vector<uint16_t>(n + m + 1));
vector<vector<int>> interesting(d + 1);
vector<uint16_t> interestingGen(d + 1);
auto getBucket = [&](int at) {
int bucket = at % (d + 1);
if (interestingGen[bucket] != at) {
interestingGen[bucket] = at;
interesting[bucket].clear();
}
return bucket;
};
auto reach = [&](int at, int bucket, int s, double pr) {
if (pgen[bucket][s] != at) {
pgen[bucket][s] = at;
prob[bucket][s] = 0;
}
bool already = prob[bucket][s] > BUBEN;
prob[bucket][s] += pr;
if (!already && prob[bucket][s] > BUBEN) {
interesting[bucket].push_back(s);
}
};
auto b0 = getBucket(0);
for (int who = 0; who < m; ++who) {
reach(0, b0, who, 1.0);
}
for (int time = 0; time < n; ++time) {
auto tbucket = getBucket(time);
auto bd = getBucket(time + d);
auto b1 = getBucket(time + 1);
for (int s : interesting[tbucket]) {
for (int comes = 0; comes < 2; ++comes) {
double cp = prob[tbucket][s];
if (comes == 0) cp *= q; else cp *= p;
int ns = s + comes;
if (ns >= m) {
ns -= m;
int arrivals = min(d - 1, n - 1 - time);
for (int extra : iprd[arrivals]) {
double got = cp * prd[arrivals][extra];
if (got < BUBEN) break;
reach(time + d, bd, ns + extra, got);
}
int waiting = ns / m;
ans += cp * bonus[arrivals][ns % m];
ans += cp * waiting * d;
} else {
reach(time + 1, b1, ns, cp);
}
}
}
}
double totalp = 0;
for (int time = n; time < n + d; ++time) {
int tbucket = getBucket(time);
for (int s : interesting[tbucket]) {
double cp = prob[tbucket][s];
int todo = s / m;
ans += cp * todo * (todo - 1) / 2 * d;
totalp += cp;
}
}
cerr << m - totalp << endl;
cout << ans / totalp * m << "\n";
}
void solve() {
cout.precision(20);
int nt = 1;
for (int it = 0; it < nt; ++it) {
// cout << "Case #" << (it + 1) << ": ";
solveOne();
}
}
};
// #define st_mtimespec st_mtim
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
QueueAtTheBakery solver;
solver.solve();
return 0;
}
In our experience, we suggest you solve this Queue at the Bakery CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
Queue at the Bakery Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Queue at the Bakery CodeChef Solution.
I hope this Queue at the Bakery CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More CodeChef Solutions >>
Olympics Ranking CodeChef Solution
Problem Difficulties CodeChef Solution
Chef and Bulb Invention CodeChef Solution