broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            prev, cur = 0, 0
        elapsed = t - idx * W
        idx = ci
        est = prev * Fraction(W - elapsed, W) + cur
        if est + 1 <= L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 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
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            prev, cur = 0, 0
        idx = ci
        elapsed = t % W + 1
        est = prev * Fraction(W - elapsed, W) + cur
        if est + 1 <= L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 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:
The first request of a new window computes a negative overlap and under-counts.

Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].

split: open-access


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

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

prompt:
A long idle period lets the bucket go negative and admit a burst larger than its capacity.

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

split: open-access


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

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

prompt:
The bucket empties a thousand times too fast, so the limiter admits nearly everything.

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

split: open-access


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

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

prompt:
After a denial the next request drains the same interval twice.

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

split: open-access


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

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

prompt:
A large request is admitted into an almost full bucket and overflows it.

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

split: open-access