broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    cap = x['capacity']
    leak = x['leak_per_s']
    level = Fraction(0)
    last = 0
    out = []
    for t, cost in x['requests']:
        level = max(Fraction(0), level - Fraction((t - last) * leak, 1000))
        last = t
        if level + cost <= cap:
            level += cost
            out.append('allow')
        else:
            level = min(Fraction(cap), level + cost)
            out.append('deny')
    return [out, str(level)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1501, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20501, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3499/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [401, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1001, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [601, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[781, 3],
                 [1209, 2],
                 [1536, 1],
                 [2095, 2],
                 [2724, 2],
                 [3100, 1],
                 [3484, 2],
                 [3740, 2],
                 [4367, 3],
                 [4423, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'],
    '1179/250']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1502, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '999/250']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20502, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '1749/500']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [402, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1002, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [602, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[589, 3],
                 [638, 1],
                 [745, 3],
                 [2131, 2],
                 [2216, 1],
                 [2400, 1],
                 [3010, 3],
                 [3050, 3],
                 [4494, 3],
                 [4689, 1]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'allow', 'allow'],
    '19/5']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1503, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1997/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20503, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3497/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [403, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1003, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [603, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[952, 1],
                 [1197, 1],
                 [1505, 1],
                 [2785, 2],
                 [2886, 3],
                 [3133, 3],
                 [3501, 1],
                 [3696, 3],
                 [4546, 2],
                 [4936, 3]]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'deny'],
    '1849/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1504, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '499/125']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20504, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '437/125']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [404, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1004, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [604, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[81, 3],
                 [993, 2],
                 [1192, 3],
                 [2031, 1],
                 [2228, 3],
                 [2879, 2],
                 [2930, 2],
                 [3521, 3],
                 [4067, 2],
                 [4522, 3]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'deny'],
    '1059/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1505, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '399/100']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20505, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '699/200']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [405, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1005, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [605, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[294, 3],
                 [1702, 1],
                 [1855, 3],
                 [1921, 3],
                 [2460, 1],
                 [2482, 3],
                 [3497, 3],
                 [4189, 1],
                 [4252, 3],
                 [4982, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'allow', 'deny', 'allow'],
    '578/125']]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    cap = x['capacity']
    leak = x['leak_per_s']
    level = Fraction(0)
    last = 0
    out = []
    for t, cost in x['requests']:
        level = max(Fraction(0), level - Fraction((t - last) * leak, 1000))
        last = t
        if level + cost <= cap:
            level += cost
            out.append('allow')
        else:
            level = Fraction(cap)
            out.append('deny')
    return [out, str(level)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1501, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20501, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3499/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [401, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1001, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [601, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[781, 3],
                 [1209, 2],
                 [1536, 1],
                 [2095, 2],
                 [2724, 2],
                 [3100, 1],
                 [3484, 2],
                 [3740, 2],
                 [4367, 3],
                 [4423, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'],
    '1179/250']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1502, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '999/250']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20502, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '1749/500']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [402, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1002, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [602, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[589, 3],
                 [638, 1],
                 [745, 3],
                 [2131, 2],
                 [2216, 1],
                 [2400, 1],
                 [3010, 3],
                 [3050, 3],
                 [4494, 3],
                 [4689, 1]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'allow', 'allow'],
    '19/5']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1503, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1997/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20503, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3497/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [403, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1003, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [603, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[952, 1],
                 [1197, 1],
                 [1505, 1],
                 [2785, 2],
                 [2886, 3],
                 [3133, 3],
                 [3501, 1],
                 [3696, 3],
                 [4546, 2],
                 [4936, 3]]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'deny'],
    '1849/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1504, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '499/125']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20504, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '437/125']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [404, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1004, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [604, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[81, 3],
                 [993, 2],
                 [1192, 3],
                 [2031, 1],
                 [2228, 3],
                 [2879, 2],
                 [2930, 2],
                 [3521, 3],
                 [4067, 2],
                 [4522, 3]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'deny'],
    '1059/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1505, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '399/100']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20505, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '699/200']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [405, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1005, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [605, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[294, 3],
                 [1702, 1],
                 [1855, 3],
                 [1921, 3],
                 [2460, 1],
                 [2482, 3],
                 [3497, 3],
                 [4189, 1],
                 [4252, 3],
                 [4982, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'allow', 'deny', 'allow'],
    '578/125']]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Rejected traffic keeps the bucket full, so a throttled client can never recover while it retries.

Input {capacity, leak_per_s, requests [[t_ms, cost]]} with nondecreasing t. The water level drains continuously at leak_per_s units per second (exact rationals) but never below zero; the drain clock advances at every request. A request is admitted iff level + cost <= capacity, raising the level by cost; a denied request leaves the level unchanged. Return [decisions, final level as a fraction string].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d > t)
        if waiting < qcap:
            dep = next_free
            next_free = dep + I
            deps.append(dep)
            out.append(dep)
        else:
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d > t)
        if waiting < qcap:
            dep = next_free if next_free > 0 else t
            next_free = dep + I
            deps.append(dep)
            out.append(dep)
        else:
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
After an idle period requests are reported as departing before they arrived.

Input {queue_cap, interval_ms, requests [t]} with nondecreasing t. Accepted requests depart one per interval: departure = max(arrival, next_free) and next_free = departure + interval. A request is accepted only while fewer than queue_cap accepted requests have a departure strictly after its arrival; otherwise it is "dropped" and changes nothing. Return each departure time or "dropped".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d >= t)
        if waiting < qcap:
            dep = max(t, next_free)
            next_free = dep + I
            deps.append(dep)
            out.append(dep)
        else:
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = len(deps)
        if waiting < qcap:
            dep = max(t, next_free)
            next_free = dep + I
            deps.append(dep)
            out.append(dep)
        else:
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A request arriving at the same instant another departs is dropped.

Input {queue_cap, interval_ms, requests [t]} with nondecreasing t. Accepted requests depart one per interval: departure = max(arrival, next_free) and next_free = departure + interval. A request is accepted only while fewer than queue_cap accepted requests have a departure strictly after its arrival; otherwise it is "dropped" and changes nothing. Return each departure time or "dropped".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d > t)
        if waiting < qcap:
            dep = max(t, next_free)
            next_free = t + I
            deps.append(dep)
            out.append(dep)
        else:
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d > t)
        if waiting < qcap:
            dep = max(t, next_free)
            next_free = next_free + I
            deps.append(dep)
            out.append(dep)
        else:
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Queued requests are spaced from their arrival rather than from the previous departure, compressing the output rate.

Input {queue_cap, interval_ms, requests [t]} with nondecreasing t. Accepted requests depart one per interval: departure = max(arrival, next_free) and next_free = departure + interval. A request is accepted only while fewer than queue_cap accepted requests have a departure strictly after its arrival; otherwise it is "dropped" and changes nothing. Return each departure time or "dropped".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d > t)
        if waiting < qcap:
            dep = max(t, next_free)
            next_free = dep + I
            deps.append(dep)
            out.append(dep)
        else:
            next_free += I
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    qcap = x['queue_cap']
    I = x['interval_ms']
    next_free = 0
    deps = []
    out = []
    for t in x['requests']:
        waiting = sum(1 for d in deps if d > t)
        if waiting < qcap:
            dep = max(t, next_free)
            next_free = dep + I
            deps.append(dep)
            out.append(dep)
        else:
            deps.append(next_free)
            out.append('dropped')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 151, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1001, 2000, 2010, 5000]},
   [1001, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 201]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 251, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [301, 310, 320, 330]},
   [301, 401, 501, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [47, 86, 231, 429, 438, 486, 490, 650, 653, 673, 689, 793]},
   [47, 127, 231, 429, 509, 589, 'dropped', 669, 749, 829, 'dropped', 909]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 152, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1002, 2000, 2010, 5000]},
   [1002, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 202]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 252, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [302, 310, 320, 330]},
   [302, 402, 502, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [130, 453, 459, 485, 554, 565, 613, 658, 676, 724, 814, 858]},
   [130, 453, 533, 613, 693, 'dropped', 773, 'dropped', 'dropped', 853, 933, 1013]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 153, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1003, 2000, 2010, 5000]},
   [1003, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 203]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 253, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [303, 310, 320, 330]},
   [303, 403, 503, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [1, 48, 98, 246, 258, 261, 333, 405, 500, 646, 651, 768]},
   [1, 81, 161, 246, 326, 406, 486, 'dropped', 566, 646, 726, 806]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 154, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1004, 2000, 2010, 5000]},
   [1004, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 204]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 254, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [304, 310, 320, 330]},
   [304, 404, 504, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [6, 206, 394, 410, 422, 469, 663, 677, 720, 726, 732, 943]},
   [6, 206, 394, 474, 554, 'dropped', 663, 743, 823, 'dropped', 'dropped', 943]]],
 [['burst queues then drops',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [0, 0, 0, 0, 155, 400]},
   [0, 100, 200, 'dropped', 300, 400]],
  ['idle line departs immediately',
   {'interval_ms': 50, 'queue_cap': 3, 'requests': [1005, 2000, 2010, 5000]},
   [1005, 2000, 2050, 5000]],
  ['departure instant is not waiting',
   {'interval_ms': 100, 'queue_cap': 1, 'requests': [0, 0, 100, 100, 205]},
   [0, 100, 200, 'dropped', 300]],
  ['dropped requests do not reserve slots',
   {'interval_ms': 200, 'queue_cap': 1, 'requests': [0, 10, 20, 30, 255, 260]},
   [0, 200, 'dropped', 'dropped', 400, 'dropped']],
  ['first request late',
   {'interval_ms': 100, 'queue_cap': 2, 'requests': [305, 310, 320, 330]},
   [305, 405, 505, 'dropped']],
  ['random arrivals',
   {'interval_ms': 80,
    'queue_cap': 2,
    'requests': [220, 273, 276, 356, 387, 434, 571, 612, 618, 647, 669, 777]},
   [220, 300, 380, 460, 540, 'dropped', 620, 700, 'dropped', 780, 'dropped', 860]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Each drop delays every later accepted request by one interval.

Input {queue_cap, interval_ms, requests [t]} with nondecreasing t. Accepted requests depart one per interval: departure = max(arrival, next_free) and next_free = departure + interval. A request is accepted only while fewer than queue_cap accepted requests have a departure strictly after its arrival; otherwise it is "dropped" and changes nothing. Return each departure time or "dropped".

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    tc, tr = x['tenant_cap'], x['tenant_rate']
    gc, gr = x['global_cap'], x['global_rate']
    tenants = {}
    g = [gc, 0]
    out = []
    for t, ten, cost in x['requests']:
        st = tenants.setdefault(ten, [tc, t])
        st[0] = min(tc, st[0] + (t - st[1]) * tr)
        st[1] = t
        g[0] = min(gc, g[0] + (t - g[1]) * gr)
        g[1] = t
        if st[0] < cost:
            out.append('deny-tenant')
        else:
            st[0] -= cost
            if g[0] < cost:
                out.append('deny-global')
                continue
            g[0] -= cost
            out.append('allow')
    return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [11, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    2,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 2],
                 [0, 'a', 3],
                 [1, 'b', 3],
                 [2, 'a', 1],
                 [3, 'c', 1],
                 [4, 'c', 3],
                 [5, 'a', 2],
                 [5, 'b', 1],
                 [6, 'a', 1],
                 [7, 'b', 2]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'deny-tenant',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    2,
    [['a', 1], ['b', 1], ['c', 0]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [12, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 2],
                 [0, 'c', 2],
                 [0, 'c', 2],
                 [2, 'b', 3],
                 [3, 'a', 2],
                 [3, 'c', 1],
                 [3, 'c', 1],
                 [4, 'a', 2],
                 [8, 'b', 2],
                 [8, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'allow',
     'deny-tenant',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    2,
    [['a', 0], ['b', 1], ['c', 2]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [13, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 2],
                 [1, 'c', 2],
                 [2, 'a', 1],
                 [2, 'a', 2],
                 [2, 'b', 1],
                 [3, 'c', 2],
                 [3, 'c', 3],
                 [4, 'a', 3],
                 [7, 'a', 1],
                 [8, 'b', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-tenant',
     'deny-tenant',
     'allow',
     'allow'],
    4,
    [['a', 2], ['b', 2], ['c', 1]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [14, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 3],
                 [1, 'a', 3],
                 [1, 'b', 3],
                 [1, 'c', 2],
                 [2, 'c', 2],
                 [3, 'a', 2],
                 [5, 'b', 2],
                 [6, 'b', 3],
                 [7, 'c', 1],
                 [8, 'a', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'deny-tenant',
     'allow',
     'deny-global',
     'allow',
     'allow',
     'allow',
     'deny-tenant',
     'allow',
     'allow'],
    4,
    [['a', 2], ['b', 2], ['c', 2]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [15, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'c', 3],
                 [3, 'c', 1],
                 [3, 'c', 2],
                 [4, 'a', 1],
                 [7, 'a', 2],
                 [7, 'b', 1],
                 [7, 'b', 1],
                 [7, 'b', 2],
                 [7, 'c', 1],
                 [7, 'c', 2]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-tenant',
     'allow',
     'deny-global'],
    0,
    [['a', 1], ['b', 1], ['c', 2]]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    tc, tr = x['tenant_cap'], x['tenant_rate']
    gc, gr = x['global_cap'], x['global_rate']
    tenants = {}
    g = [gc, 0]
    out = []
    for t, ten, cost in x['requests']:
        st = tenants.setdefault(ten, [tc, t])
        st[0] = min(tc, st[0] + (t - st[1]) * tr)
        st[1] = t
        g[0] = min(gc, g[0] + (t - g[1]) * gr)
        g[1] = t
        if st[0] < cost:
            out.append('deny-tenant')
        elif g[0] < cost:
            g[0] = 0
            out.append('deny-global')
        else:
            st[0] -= cost
            g[0] -= cost
            out.append('allow')
    return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [11, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    2,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 2],
                 [0, 'a', 3],
                 [1, 'b', 3],
                 [2, 'a', 1],
                 [3, 'c', 1],
                 [4, 'c', 3],
                 [5, 'a', 2],
                 [5, 'b', 1],
                 [6, 'a', 1],
                 [7, 'b', 2]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'deny-tenant',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    2,
    [['a', 1], ['b', 1], ['c', 0]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [12, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 2],
                 [0, 'c', 2],
                 [0, 'c', 2],
                 [2, 'b', 3],
                 [3, 'a', 2],
                 [3, 'c', 1],
                 [3, 'c', 1],
                 [4, 'a', 2],
                 [8, 'b', 2],
                 [8, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'allow',
     'deny-tenant',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    2,
    [['a', 0], ['b', 1], ['c', 2]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [13, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 2],
                 [1, 'c', 2],
                 [2, 'a', 1],
                 [2, 'a', 2],
                 [2, 'b', 1],
                 [3, 'c', 2],
                 [3, 'c', 3],
                 [4, 'a', 3],
                 [7, 'a', 1],
                 [8, 'b', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-tenant',
     'deny-tenant',
     'allow',
     'allow'],
    4,
    [['a', 2], ['b', 2], ['c', 1]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [14, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'a', 3],
                 [1, 'a', 3],
                 [1, 'b', 3],
                 [1, 'c', 2],
                 [2, 'c', 2],
                 [3, 'a', 2],
                 [5, 'b', 2],
                 [6, 'b', 3],
                 [7, 'c', 1],
                 [8, 'a', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'deny-tenant',
     'allow',
     'deny-global',
     'allow',
     'allow',
     'allow',
     'deny-tenant',
     'allow',
     'allow'],
    4,
    [['a', 2], ['b', 2], ['c', 2]]]]],
 [['global exhaustion',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
  ['partial global remains usable',
   {'global_cap': 4,
    'global_rate': 1,
    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],
    'tenant_cap': 5,
    'tenant_rate': 1},
   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
  ['both short reports tenant',
   {'global_cap': 2,
    'global_rate': 1,
    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],
    'tenant_cap': 2,
    'tenant_rate': 1},
   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
  ['tenant clock independent',
   {'global_cap': 20,
    'global_rate': 5,
    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],
    'tenant_cap': 4,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
  ['new tenant starts full',
   {'global_cap': 10,
    'global_rate': 2,
    'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
  ['global capacity bound',
   {'global_cap': 6,
    'global_rate': 3,
    'requests': [[0, 'a', 2],
                 [0, 'b', 2],
                 [0, 'c', 2],
                 [10, 'a', 2],
                 [10, 'b', 2],
                 [10, 'c', 2],
                 [15, 'd', 1]],
    'tenant_cap': 2,
    'tenant_rate': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
    5,
    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
  ['random tenants',
   {'global_cap': 5,
    'global_rate': 2,
    'requests': [[0, 'c', 3],
                 [3, 'c', 1],
                 [3, 'c', 2],
                 [4, 'a', 1],
                 [7, 'a', 2],
                 [7, 'b', 1],
                 [7, 'b', 1],
                 [7, 'b', 2],
                 [7, 'c', 1],
                 [7, 'c', 2]],
    'tenant_cap': 3,
    'tenant_rate': 1},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-tenant',
     'allow',
     'deny-global'],
    0,
    [['a', 1], ['b', 1], ['c', 2]]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A tenant loses its own tokens for requests the shared limit rejected.

Input {tenant_cap, tenant_rate, global_cap, global_rate, requests [[t_s, tenant, cost]]} with nondecreasing whole-second t. Each tenant bucket starts full at its first request and refills from its own last-seen time; the global bucket starts full at t=0. Both refill lazily and are capped by their own capacity. A request needs cost tokens in both; the tenant bucket is checked first ("deny-tenant"), then the global ("deny-global"); both are charged only on admission. Return [decisions, global tokens, sorted [tenant, tokens]].

split: open-access