<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

450. Ramen Shop
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Ron is a master of a ramen shop.

Recently, he has noticed some customers wait for a long time. This has been caused by lack of seats during lunch time. Customers loses their satisfaction if they wait for a long time, and some of them will even give up waiting and go away. For this reason, he has decided to increase seats in his shop. To determine how many seats are appropriate, he has asked you, an excellent programmer, to write a simulator of customer behavior.

Customers come to his shop in groups, each of which is associated with the following four parameters:
Ti: when the group comes to the shop
Pi: number of customers
Wi: how long the group can wait for their seats
Ei: how long the group takes for eating


The i-th group comes to the shop with Pi customers together at the time Ti. If Pi successive seats are available at that time, the group takes their seats immediately. Otherwise, they wait for such seats being available. When the group fails to take their seats within the time Wi (inclusive) from their coming and strictly before the closing time, they give up waiting and go away. In addition, if there are other groups waiting, the new group cannot take their seats until the earlier groups are taking seats or going away.

The shop has N counters numbered uniquely from 1 to N. The i-th counter has Ci seats. A group cannot spread over multiple counters. The group prefers "seats with a greater distance to the nearest group." Precisely, the group takes their seats according to the criteria listed below. For each block of seats of appropriate size within each counter, values SL and SR are calculated. Here, SL denotes the number of successive empty seats on the left side of the group after their seating, and SR the number on the right side. SL and SR are considered to be infinity if there are no other customers on the left side and on the right side respectively. Note that these numbers don't take into account people in other counters.
Prefers seats maximizing min { SL, SR }.
If there are multiple alternatives meeting the first criterion, prefers seats maximizing max { SL, SR }.
If there are still multiple alternatives, prefers the counter of the smallest number.
If there are still multiple alternatives, prefers the leftmost seats.

When multiple groups are leaving the shop at the same time and some other group is waiting for available seats, seat assignment for the waiting group should be made after all the finished groups leave the shop. If a customer starts eating, he is allowed to finish even after the shop closes.

Your task is to calculate the average satisfaction over customers. The satisfaction of a customer in the i-th group is given as follows:
If the group goes away without eating, -1.
Otherwise, (Wi - ti) / Wi where ti is the actual waiting time for the i-th group (the value ranges between 0 to 1 inclusive).


Input
The input has the following format:

N M T

C1 C2... CN

T1 P1 W1 E1

T2 P2 W2 E2

...

TM PM WM EM

N indicates the number of counters, M indicates the number of groups and T indicates the closing time. The shop always opens at the time 0. All input values are integers.

You can assume that 1 ≤ N ≤ 100, 1 ≤ M ≤ 10000, 1 ≤ T ≤ 109, 1 ≤ Ci ≤ 100, 0 ≤ T1 < T2 <... < TM < T, 1 ≤ Pi ≤ max{Ci}, 1 ≤ Wi ≤ 109 and 1 ≤ Ei ≤ 109.

Output
Output the average satisfaction over all customers in a line. The output value may be printed with an arbitrary number of fractional digits, but may not contain an absolute error greater than 10-9.

Example(s)
sample input
sample output
1 4 100
7
10 1 50 50
15 2 50 50
25 1 50 50
35 3 50 50
0.7428571428571429

sample input
sample output
1 2 100
5
30 3 20 50
40 4 40 50
0.4285714285714285

sample input
sample output
1 2 100
5
49 3 20 50
60 4 50 30
0.5542857142857143

sample input
sample output
1 2 100
5
50 3 20 50
60 4 50 30
-0.1428571428571428

sample input
sample output
2 3 100
4 2
10 4 20 20
30 2 20 20
40 4 20 20
0.8000000000000000

<|response|>
1. Abridged Problem Statement

A ramen shop has N counters; counter c has C[c] seats in a line. There are M customer groups arriving in increasing time order. Group i arrives at time Ti, has Pi people (must sit in Pi consecutive seats within a single counter), will wait up to Wi time units (inclusive) for seats, and then eats for Ei time units once seated. The shop closes at time T: groups can only start eating strictly before T, but if they start, they may finish after T.

Groups form a FIFO queue: if earlier groups are waiting, a newly arrived group cannot be seated before them (even if seats are available), until earlier groups either get seated or give up.

When a group is to be seated, it chooses among all possible contiguous empty blocks of length Pi using these tie-breakers:

1. Maximize min(SL, SR)
2. Then maximize max(SL, SR)
3. Then smallest counter index
4. Then leftmost position

Here SL/SR are the numbers of consecutive empty seats directly to the left/right after seating within that counter; if there is no occupied seat on that side, it is treated as infinity.

Satisfaction per customer in group i:
- If the group leaves without eating: -1
- Else: (Wi - wait_time) / Wi (in [0,1])

Output the average satisfaction over all customers (weighted by group sizes).

2. Key Observations

1. Seat layout is small: N ≤ 100, each Ci ≤ 100 ⇒ at most 10,000 seats total. This allows scanning all counters/positions when trying to seat a group.

2. Time is huge, but only changes at discrete events: group arrivals Ti, group departures seat_time + Ei, and group "patience deadline" times Ti + Wi (important due to FIFO).

3. FIFO waiting rule is crucial: only the front group of the waiting queue may be considered for seating. If it cannot be seated now and hasn't expired, nobody behind it can be seated.

4. Need to respect ordering at equal times: if multiple groups leave at the same time, free all seats first, then attempt seating waiting groups.

5. A "dummy event" at Ti + Wi is a neat trick: it "wakes up" the simulator exactly when the front group may expire even if no arrival/departure happens at that time.

3. Full Solution Approach

We simulate using an event priority queue (min-heap by time) and a FIFO queue for waiting groups.

Events store (time, id):
- id in [0, M-1]: arrival of group id
- id < 0: departure of group g = -id-1 (free its seats)
- id == M: dummy "deadline tick" (does nothing except trigger processing)

Initially, for each group i push arrival (Ti, i) and dummy (Ti + Wi, M). When a group gets seated at time cur, push departure (cur + Ei, -(i+1)).

Simulation loop:
While heap not empty:
1. Let cur = earliest event time. If cur >= T, stop.
2. Pop all events with time cur and apply: departure (free seats), arrival (enqueue), dummy (ignore).
3. After processing all events at cur, repeatedly handle the front of waiting:
   - let g = waiting.front()
   - if cur > Ti+Wi: group leaves (satisfaction stays -1), pop it, continue
   - else try to seat it now:
     - if seating succeeds: schedule departure, set satisfaction = (Ti + Wi - cur) / Wi, pop it, continue
     - if cannot seat: stop (FIFO blocks everyone behind)

Seat selection (can_seat(g)):
Given P = Pi, find the best empty block across all counters. For each counter c, for each start position pos where pos..pos+P-1 fits: if block is empty, compute SL (empty seats left until nearest occupied, INF if none) and SR (empty seats right until nearest occupied, INF if none). Apply tie-breaks as stated. Use a sliding window to test block emptiness efficiently.

Final answer: sum over i of sat[i] * Pi, divided by sum of Pi.

4. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int inf = (int)2e9 + 42;

int n, m, t;
vector<int> cap, start, group_size, deadline, eat_time;

void read() {
    cin >> n >> m >> t;
    cap.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> cap[i];
    }

    start.resize(m);
    group_size.resize(m);
    deadline.resize(m);
    eat_time.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> start[i] >> group_size[i] >> deadline[i] >> eat_time[i];
    }
}

vector<vector<int>> cc;
vector<double> satisfaction;
vector<bool> seated;

struct Option {
    int min_dist;
    int max_dist;
    int idx;
    int pos;
};

vector<Option> opts;

priority_queue<
    pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>>
    ev;
queue<int> waiting;

bool is_better(const Option& a, const Option& b) {
    if(a.min_dist != b.min_dist) {
        return a.min_dist > b.min_dist;
    }
    if(a.max_dist != b.max_dist) {
        return a.max_dist > b.max_dist;
    }
    if(a.idx != b.idx) {
        return a.idx < b.idx;
    }
    return a.pos < b.pos;
}

bool can_seat(int g) {
    bool found = false;
    Option best_opt;

    for(int c = 0; c < n; c++) {
        int sum = 0;
        int last_left, last_right;

        for(int i = 0; i + group_size[g] <= cap[c]; i++) {
            if(i == 0) {
                for(int j = 0; j < group_size[g]; j++) {
                    sum += cc[c][j];
                }
                last_left = -1;
                last_right = group_size[g];
            } else {
                sum += cc[c][i + group_size[g] - 1] - cc[c][i - 1];
                if(cc[c][i - 1]) {
                    last_left = i - 1;
                }
                last_right = max(last_right, i + (int)group_size[g]);
            }
            while(last_right < cap[c] && !cc[c][last_right]) {
                last_right++;
            }

            if(!sum) {
                int left_span = (last_left == -1) ? inf : (i - 1 - last_left);
                int right_span = (last_right == cap[c])
                                     ? inf
                                     : (last_right - i - group_size[g]);
                Option cur_opt = {
                    min(left_span, right_span), max(left_span, right_span), c, i
                };

                if(!found || is_better(cur_opt, best_opt)) {
                    found = true;
                    best_opt = cur_opt;
                }
            }
        }
    }

    if(found) {
        opts[g] = best_opt;
        seated[g] = true;
        for(int i = 0; i < group_size[g]; i++) {
            cc[best_opt.idx][best_opt.pos + i] = 1;
        }
    }

    return found;
}

void remove_group(int g) {
    Option& opt = opts[g];
    for(int i = 0; i < group_size[g]; i++) {
        cc[opt.idx][opt.pos + i] = 0;
    }
}

void solve() {
    // The simulator is deterministic, so this is essentially an implementation
    // problem. We can notice that, constraints for N and C are tiny, so we
    // don't even need to implement operations with BSTs. In theory we
    // should be able to use a BST over empty ranges and one over
    // counters, and always find the largest empty interval which will be split
    // in half. However, for given constraints we don't really need this. We
    // can simply keep an event priority queue, and implement each leaving or
    // entering operation naively.

    cc.resize(n);
    for(int i = 0; i < n; i++) {
        cc[i].assign(cap[i], 0);
    }

    satisfaction.resize(m);
    opts.resize(m);
    seated.assign(m, false);

    for(int i = 0; i < m; i++) {
        satisfaction[i] = -1;
        ev.emplace(start[i], i);
        ev.emplace(start[i] + deadline[i], m);
    }

    while(!ev.empty()) {
        int64_t cur_time = ev.top().first;
        if(cur_time >= t) {
            break;
        }

        while(!ev.empty() && ev.top().first == cur_time) {
            int id = ev.top().second;
            ev.pop();

            if(id < 0) {
                remove_group(-id - 1);
            }
            if(id >= 0 && id < m) {
                waiting.push(id);
            }
        }

        while(!waiting.empty()) {
            int g = waiting.front();
            if(cur_time <= start[g] + deadline[g]) {
                if(can_seat(g)) {
                    ev.emplace(cur_time + eat_time[g], -(g + 1));
                    satisfaction[g] =
                        (double)(start[g] + deadline[g] - cur_time) /
                        deadline[g];
                    waiting.pop();
                    continue;
                }
            }
            if(cur_time >= start[g] + deadline[g]) {
                waiting.pop();
                continue;
            }
            break;
        }
    }

    int64_t tot_sz = 0;
    double tot = 0.0;
    for(int i = 0; i < m; i++) {
        tot += satisfaction[i] * group_size[i];
        tot_sz += group_size[i];
    }

    cout << fixed << setprecision(16) << tot / tot_sz << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Solution with Comments

```python
import sys
import heapq
from collections import deque

INF = 2_000_000_042  # "infinity" span used in comparisons


def solve() -> None:
    data = sys.stdin.read().strip().split()
    it = iter(data)

    n = int(next(it))  # number of counters
    m = int(next(it))  # number of groups
    Tclose = int(next(it))  # closing time

    cap = [int(next(it)) for _ in range(n)]  # seats per counter

    start = [0] * m
    group_size = [0] * m
    deadline = [0] * m
    eat_time = [0] * m
    for i in range(m):
        start[i] = int(next(it))
        group_size[i] = int(next(it))
        deadline[i] = int(next(it))
        eat_time[i] = int(next(it))

    # cc[c][s] = 1 if occupied, else 0
    cc = [[0] * cap[c] for c in range(n)]

    # satisfaction per group, default -1 (means "gave up")
    satisfaction = [-1.0] * m

    # opts[i] stores (counter_idx, pos, group_len) to remove later
    # We'll also store spans if we want, but only counter and pos are necessary.
    opts = [None] * m

    # Event heap: (time, id)
    # id meanings:
    #   0..m-1 : arrival of group id
    #   <0     : departure of group (-id-1)
    #   == m   : dummy wake-up at start[i] + deadline[i]
    ev = []
    for i in range(m):
        heapq.heappush(ev, (start[i], i))
        heapq.heappush(ev, (start[i] + deadline[i], m))  # dummy

    waiting = deque()

    def better(a, b):
        """Return True if option a is better than b.
        option = (min_dist, max_dist, counter_idx, pos)
        """
        if a[0] != b[0]:
            return a[0] > b[0]
        if a[1] != b[1]:
            return a[1] > b[1]
        if a[2] != b[2]:
            return a[2] < b[2]
        return a[3] < b[3]

    def can_seat(g):
        """Try to seat group g now. If success, occupy seats and save opts[g]."""
        P = group_size[g]
        found = False
        best = None  # (min_dist, max_dist, c, pos)

        for c in range(n):
            C = cap[c]
            if P > C:
                continue

            # Sliding window sum over occupancy
            window_sum = 0
            last_left = -1
            last_right = P  # will move to first occupied seat to the right

            # init window [0, P-1]
            for j in range(P):
                window_sum += cc[c][j]

            # For each possible start i
            for i0 in range(0, C - P + 1):
                if i0 > 0:
                    # slide window by 1:
                    window_sum += cc[c][i0 + P - 1] - cc[c][i0 - 1]

                    # if seat leaving on the left was occupied, update last_left
                    if cc[c][i0 - 1]:
                        last_left = i0 - 1

                    # last_right must be at least end of window
                    if last_right < i0 + P:
                        last_right = i0 + P

                # move last_right to the next occupied seat or end
                while last_right < C and cc[c][last_right] == 0:
                    last_right += 1

                # If window is empty, compute option score
                if window_sum == 0:
                    left_span = INF if last_left == -1 else (i0 - 1 - last_left)
                    right_span = INF if last_right == C else (last_right - i0 - P)

                    mn = left_span if left_span < right_span else right_span
                    mx = right_span if left_span < right_span else left_span
                    cur = (mn, mx, c, i0)

                    if (not found) or better(cur, best):
                        found = True
                        best = cur

        if not found:
            return False

        # Occupy seats according to best option
        _, _, c, pos = best
        for k in range(group_size[g]):
            cc[c][pos + k] = 1

        opts[g] = (c, pos, group_size[g])
        return True

    def remove_group(g):
        """Free seats occupied by group g."""
        c, pos, P = opts[g]
        for k in range(P):
            cc[c][pos + k] = 0

    # Main simulation loop
    while ev:
        cur_time, eid = ev[0]

        # cannot start seating at/after closing time
        if cur_time >= Tclose:
            break

        # pop all events at cur_time
        while ev and ev[0][0] == cur_time:
            _, eid = heapq.heappop(ev)

            if eid < 0:
                g = -eid - 1
                remove_group(g)
            elif 0 <= eid < m:
                waiting.append(eid)
            # eid == m: dummy, do nothing

        # after applying all changes at this time, try to seat from the front
        while waiting:
            g = waiting[0]
            # If still within patience, try to seat now
            if cur_time <= start[g] + deadline[g]:
                if can_seat(g):
                    # schedule departure
                    heapq.heappush(ev, (cur_time + eat_time[g], -(g + 1)))

                    # compute satisfaction (per customer)
                    satisfaction[g] = (start[g] + deadline[g] - cur_time) / deadline[g]

                    waiting.popleft()
                    continue

            # If patience expired, group leaves now
            if cur_time >= start[g] + deadline[g]:
                waiting.popleft()
                continue

            # Otherwise cannot seat now and still waiting => stop (FIFO blocks)
            break

    # Weighted average satisfaction
    tot = 0.0
    tot_sz = 0
    for i in range(m):
        tot += satisfaction[i] * group_size[i]
        tot_sz += group_size[i]

    ans = tot / tot_sz
    # print with enough precision
    sys.stdout.write(f"{ans:.16f}\n")


if __name__ == "__main__":
    solve()
```
