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 g[0] < cost:
            out.append('deny-global')
        elif st[0] < cost:
            out.append('deny-tenant')
        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)

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 and g[0] < cost:
            out.append('deny-both')
        elif st[0] < cost:
            out.append('deny-tenant')
        elif g[0] < cost:
            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:
Tenants over their own limit are told the shared service is saturated.

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


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 - g[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:
            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)

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):
    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) if st[0] < cost else st[0]
        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:
            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 idle while others were active never refills, because the elapsed time is measured from anyone's last request.

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


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, [0, 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:
            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)

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, [tr, 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:
            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's first request is denied although it has never used its quota.

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