Queue at the Bakery CodeChef Solution – Queslers

Problem: Queue at the Bakery CodeChef Solution

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)?

Input Format

• The only line of the input contains the three integers nn, mm, dd and the real number pp – the number of seconds at which a customer may enter, the number of employees, the amount of seconds necessary to serve a customer, the probability that a customer enters at any given second.

Output Format

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.

Constraints

• 1≤n≤500001≤n≤50000
• 1≤m≤101≤m≤10
• 1≤d≤10001≤d≤1000
• 0.4≤p≤0.60.4≤p≤0.6
• The number pp is given with exactly 44 digits after the decimal point.

Sample Input 1 

2 1 5 0.4000

Sample Output 1 

0.6400000000

Explanation

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.

Sample Input 2 

3 2 1000 0.5000

Sample Output 2 

124.7500000000

Explanation

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.

Sample Input 3 

5 3 9 0.5891

Sample Output 3 

2.1875381171

Sample Input 4 

40 10 30 0.4567

Sample Output 4 

86.7734103628

Queue at the Bakery CodeChef Solution in C++

/**
 * 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;
}

Queue at the Bakery CodeChef Solution Review:

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.

Conclusion:

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

Array Filling CodeChef Solution

Special Triplets CodeChef Solution