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

N = 1
observations = []
def solve(x):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60
        if s != sw:
            sw, sc = s, 0
        if m != mw:
            mw, mc = m, 0
        if sc >= ls:
            out.append('deny-second')
        elif mc >= lm:
            out.append('deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, round(t / 60000)
        if s != sw:
            sw, sc = s, 0
        if m != mw:
            mw, mc = m, 0
        if sc >= ls:
            out.append('deny-second')
        elif mc >= lm:
            out.append('deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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 minute counter resets every 60 ms and the minute limit is never effective.

Input {per_second, per_minute, requests [t_ms]} with nondecreasing t. Second windows are t div 1000 and minute windows t div 60000, each resetting its own counter only when its own window changes. The second limit is checked first ("deny-second"), then the minute limit ("deny-minute"); only admitted requests are counted, in both windows. Return [decisions, second count, minute count].

split: open-access


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

N = 1
observations = []
def solve(x):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60000
        if s != sw:
            sw, sc = s, 0
        if m != mw:
            mw, mc = m, 0
        if mc >= lm:
            out.append('deny-minute')
        elif sc >= ls:
            out.append('deny-second')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60000
        if s != sw:
            sw, sc = s, 0
        if m != mw:
            mw, mc = m, 0
        if sc >= ls or mc >= lm:
            out.append('deny-second' if sc > mc else 'deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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:
Clients exhausted on both limits are told to wait for the minute reset instead of the next second.

Input {per_second, per_minute, requests [t_ms]} with nondecreasing t. Second windows are t div 1000 and minute windows t div 60000, each resetting its own counter only when its own window changes. The second limit is checked first ("deny-second"), then the minute limit ("deny-minute"); only admitted requests are counted, in both windows. Return [decisions, second count, minute count].

split: open-access


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

N = 1
observations = []
def solve(x):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = left // len(need)
        if share == 0:
            for c in active[:left]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c] - alloc[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
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):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = C // len(active)
        if share == 0:
            for c in active[:left]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c] - alloc[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
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:
Capacity is split among clients that no longer need it, needing extra rounds and misallocating the remainder.

Input {capacity, demands [[client, demand]]} in integer requests per second. Clients with positive demand are active. Repeatedly give each active client min(floor(left / active count), unmet demand) and drop satisfied clients; when the per-client share rounds to zero, hand single units to active clients in ascending id order until capacity is exhausted. Return [sorted [client, allocation]], unallocated capacity].

split: open-access


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

N = 1
observations = []
def solve(x):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = left // len(active)
        if share == 0:
            for c in active[:left]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = share
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
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):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = left // len(active)
        if share == 0:
            for c in active[:left]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
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:
Light clients receive rate they cannot use while heavy clients are starved.

Input {capacity, demands [[client, demand]]} in integer requests per second. Clients with positive demand are active. Repeatedly give each active client min(floor(left / active count), unmet demand) and drop satisfied clients; when the per-client share rounds to zero, hand single units to active clients in ascending id order until capacity is exhausted. Return [sorted [client, allocation]], unallocated capacity].

split: open-access


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

N = 1
observations = []
def solve(x):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = left // len(active)
        if share == 0:
            for c in active[:0]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c] - alloc[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
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):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = left // len(active)
        if share == 0:
            for c in active[-left:]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c] - alloc[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
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 few units of capacity are left unused even though clients still want them.

Input {capacity, demands [[client, demand]]} in integer requests per second. Clients with positive demand are active. Repeatedly give each active client min(floor(left / active count), unmet demand) and drop satisfied clients; when the per-client share rounds to zero, hand single units to active clients in ascending id order until capacity is exhausted. Return [sorted [client, allocation]], unallocated capacity].

split: open-access