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

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = min(L, remaining)
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = min(L, remaining)
            remaining -= L
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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:
Every node can lease the whole quota, multiplying the global limit.

Input {quota, window_s, chunk, events [[t, node, "req"|"return"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. "return" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].

split: open-access


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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens >= cost and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens >= 0 and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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:
Expensive requests are refused until the bucket fully covers them, starving large callers.

Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].

split: open-access


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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens > 0 and tokens - cost >= -cap:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t
        if tokens > 0 and tokens - cost > -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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:
The overdraft limit follows the bucket size rather than the configured debt bound.

Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].

split: open-access


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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, max(0, tokens) + (t - last) * rate)
        last = t
        if tokens > 0 and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = tokens if tokens < 0 else min(cap, tokens + (t - last) * rate)
        last = t
        if tokens > 0 and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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:
Overdrawn clients start refilling from zero, so debt is never repaid.

Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].

split: open-access


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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        if tokens > 0 and tokens - cost >= -debt:
            last = t
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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):
    cap = x['capacity']
    rate = x['rate']
    debt = x['max_debt']
    tokens = cap
    last = 0
    out = []
    for t, cost in x['requests']:
        tokens = min(cap, tokens + (t - last) * rate)
        last = t if tokens >= 0 else last
        if tokens > 0 and tokens - cost >= -debt:
            tokens -= cost
            out.append(['allow', tokens])
        else:
            out.append(['deny', tokens])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},
   [['allow', 1],
    ['allow', 1],
    ['allow', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', 1],
    ['allow', 0],
    ['allow', 0]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},
   [['allow', 1],
    ['allow', 2],
    ['allow', 0],
    ['allow', -4],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3],
    ['deny', -2],
    ['deny', -1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},
   [['allow', 2],
    ['allow', -2],
    ['deny', -1],
    ['deny', 0],
    ['allow', 3],
    ['allow', -1],
    ['deny', -1],
    ['deny', 0],
    ['allow', -3]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},
   [['allow', 4],
    ['allow', 2],
    ['allow', -2],
    ['deny', -2],
    ['deny', 0],
    ['deny', 0],
    ['allow', 0],
    ['allow', -1],
    ['allow', 1]]]],
 [['overdraft then repay',
   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},
   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],
  ['debt limit',
   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},
   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],
  ['exactly zero balance',
   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},
   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],
  ['refill repays debt',
   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},
   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],
  ['large cost at full balance',
   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},
   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],
  ['random costs',
   {'capacity': 5,
    'max_debt': 4,
    'rate': 1,
    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},
   [['allow', 0],
    ['allow', -1],
    ['deny', -1],
    ['allow', 0],
    ['deny', 0],
    ['allow', -1],
    ['deny', 0],
    ['deny', 0],
    ['allow', 3]]]]]
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 a denial the same interval is refilled again at the next request.

Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].

split: open-access