from collections import deque

arrivals = [(0, 2), (0, 4), (0, 2), (0, 3), (0, 1), (1, 4), (1, 2)]
workers, queue_limit, deadline = 2, 2, 5
assert workers > 0 and queue_limit >= 0 and deadline > 0

def simulate(admission):
    queue, active = deque(), []
    counts = dict(offered=0, admitted=0, rejected=0, completed=0, expired=0)
    latencies, incoming, peak_queue = [], 0, 0
    horizon = arrivals[-1][0] + deadline + sum(service for _, service in arrivals) + 1
    for t in range(horizon):
        # Hủy cả job trong queue lẫn job đang chạy khi deadline đã hết.
        kept = deque()
        for job in queue:
            if t >= job["deadline"]: counts["expired"] += 1
            else: kept.append(job)
        queue = kept
        kept_active = []
        for job in active:
            if t >= job["deadline"]: counts["expired"] += 1
            else: kept_active.append(job)
        active = kept_active
        while incoming < len(arrivals) and arrivals[incoming][0] == t:
            arrival, service = arrivals[incoming]; incoming += 1; counts["offered"] += 1
            due = arrival + deadline
            free_at = [t + job["left"] for job in active] + [t]*(workers-len(active))
            for job in queue:
                worker = min(range(workers), key=lambda i: free_at[i])
                free_at[worker] += job["left"]
            predicted_finish = min(free_at) + service
            reject = admission and (len(queue)+len(active) >= workers+queue_limit or predicted_finish > due)
            if reject: counts["rejected"] += 1
            else:
                queue.append(dict(left=service, arrival=arrival, deadline=due))
                counts["admitted"] += 1
        while queue and len(active)<workers: active.append(queue.popleft())
        peak_queue = max(peak_queue, len(queue))
        if admission: assert len(queue) <= queue_limit
        kept_active = []
        for job in active:
            job["left"] -= 1
            if job["left"] == 0:
                assert t+1 <= job["deadline"]
                counts["completed"] += 1; latencies.append(t+1-job["arrival"])
            else: kept_active.append(job)
        active = kept_active
        if incoming == len(arrivals) and not queue and not active: break
    pending = len(queue)+len(active)
    assert counts["offered"] == counts["admitted"] + counts["rejected"]
    assert counts["admitted"] == counts["completed"] + counts["expired"] + pending
    return counts, pending, peak_queue, latencies

for admission in (False, True):
    counts, pending, peak, latencies = simulate(admission)
    print("\nPolicy:", "deadline + bounded admission" if admission else "accept all")
    print("counts:", counts, "pending:", pending, "peak waiting:", peak)
    print("completed latencies:", latencies)
    print("fraction offered completed on time:", counts["completed"]/counts["offered"])
print("PASS: offered = admitted + rejected; admitted = completed + expired + pending.")
# Admission dự báo FIFO theo service đã biết; production cần estimator và theo dõi sai số.