{"id":"jobshop-taillard-open","name":"Job shop scheduling, Taillard's open 30x20 instances","family":"operations-research","description":"Minimise the makespan on Taillard's ten 30-job, 20-machine job shop instances ta41-ta50, the only Taillard group where every best-known schedule is still unproven. The eval rebuilds the schedule from your machine orders and scores best-known / yours.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":180,"agent_timeout_seconds":1800,"mutable":["schedule.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Job shop scheduling, Taillard's open 30x20 instances\n\n## Goal\n\nA **job shop** has `n` jobs and `m` machines. Each job is a fixed sequence of `m` operations, one\nper machine, each with an integer duration; a machine processes one operation at a time; no\npreemption. The **makespan** is the time the last operation finishes. Minimise it.\n\nTaillard's 1993 benchmark set has 80 instances. Fifty years of tabu search, constraint programming\nand hybrids have closed most of them, but the ten **30-job, 20-machine** instances `ta41`-`ta50`\nare all still open: for each the best-known schedule is strictly above the best proven lower\nbound (by 2 to 94 units). Those ten are the whole benchmark here. Any schedule shorter than a\nbest-known one is a new upper bound on a problem people have attacked since 1993.\n\n## Solver interface\n\n`schedule.py` exposes\n\n    schedule(name: str, jobs: list[list[tuple[int, int]]], time_budget: float, seed: int) -> list[list[int]]\n\n- `name` is the instance name (`\"ta41\"` ...), `jobs[j]` is job `j`'s routing in processing order:\n  `jobs[j][k] = (machine, duration)` for its `k`-th operation, machines numbered `0..m-1`, every job\n  visiting every machine exactly once. You receive a private copy; mutate it if you like.\n- Return **one list per machine, in machine order 0..m-1**: `result[i]` is the list of the `n` job\n  indices in the order machine `i` processes them (a permutation of `range(n)`). That is the whole\n  encoding: no start times, no makespan. The eval rebuilds the earliest-start (semi-active)\n  schedule from your orders plus the routings and measures the makespan itself.\n- A set of machine orders that contradicts the routings (a cycle in the disjunctive graph), a\n  missing machine, a repeated or out-of-range job, a non-integer: all `wrong_answer`, and one bad\n  instance fails the whole run.\n\nEvery 30x20 instance is shipped as `instances/<name>.txt` in the standard JSPLIB / OR-Library\nlayout (`n m` on the first line, then a line per job of `machine duration` pairs). Those files are\nread by the eval, not by you (`open` is not allowed in a solver); the data reaches you as `jobs`.\n\n## Metric\n\n    metric = mean over instances of  best_known(name) / makespan(name)\n\nso 1.0 means matching every best-known makespan and any per-instance ratio above 1.0 is a new\nrecord. Per-instance makespans, records, lower bounds and ratios are in the eval output\n(`per_instance`); instances you beat are listed under `records_beaten`.\n\nEnvironment knobs (both honoured by `eval.py`):\n\n- `ZT_EVAL_SEED` only changes the `seed` handed to your solver. The instance set is fixed; the hub\n  verifies with a held-out seed, so make your method robust to its starting point, and\n  deterministic given `seed` (`random.Random(seed)`).\n- `ZT_EVAL_INSTANCES` is a comma-separated subset of instance names (default all ten). Use it to\n  iterate on one instance quickly, e.g. `ZT_EVAL_INSTANCES=ta45,ta50`.\n- `ZT_EVAL_PER_INSTANCE_SECONDS` is the `time_budget` handed to each call (default 10, so a full\n  eval is about 100 s). The eval fails a call that runs past `1.25 * budget + 3` s. Use the whole\n  budget: on these instances more search time is still worth roughly 1 % of makespan.\n\n## Records\n\nBest-known makespans (upper bounds) and lower bounds from Oleg Shylo's bounds page for Taillard's\ninstances, https://optimizizer.com/TA.php, last updated 2026-06-29, read 2026-09-07. Every upper\nbound in this table was re-verified for this pack by decoding the solution posted on that page\nagainst the instance data with this pack's own eval. None is proven optimal.\n\n| instance | size | best-known makespan (source) | lower bound (source) | gap |\n|---|---|---|---|---|\n| ta41 | 30x20 | 2006 (Shylo & Pardalos 2008, parallel GES) | 1912 (Heinz, Hanzálek & Vilím 2024) | 94 |\n| ta42 | 30x20 | 1939 (Hernandez-Constantino & Segura 2019, parallel memetic) | 1887 (Heinz, Hanzálek & Vilím 2024) | 52 |\n| ta43 | 30x20 | 1846 (Peng, Lü & Cheng 2015, TS/path relinking) | 1809 (Vaessens 1995) | 37 |\n| ta44 | 30x20 | 1978 (Liu, Li & Gao 2026, to appear) | 1952 (Heinz, Hanzálek & Vilím 2024) | 26 |\n| ta45 | 30x20 | 1999 (Liu, Li & Gao 2026, to appear) | 1997 (Vaessens 1995) | 2 |\n| ta46 | 30x20 | 2002 (Liu, Li & Gao 2026, to appear) | 1966 (Heinz, Hanzálek & Vilím 2024) | 36 |\n| ta47 | 30x20 | 1889 (Peng, Lü & Cheng 2015, TS/path relinking) | 1816 (Heinz, Hanzálek & Vilím 2024) | 73 |\n| ta48 | 30x20 | 1937 (Shylo & Shams 2018, guided tabu, arXiv:1808.10813) | 1915 (Heinz, Hanzálek & Vilím 2024) | 22 |\n| ta49 | 30x20 | 1960 (Li, Hao & Wu 2024, hash-based tabu + pattern mining) | 1934 (Heinz, Hanzálek & Vilím 2024) | 26 |\n| ta50 | 30x20 | 1923 (Peng, Lü & Cheng 2015, TS/path relinking) | 1837 (Heinz, Hanzálek & Vilím 2024) | 86 |\n\nSources, as cited on that page: Shylo & Pardalos (2008), parallel implementation of global\nequilibrium search; Hernandez-Constantino & Segura (2019), a parallel memetic algorithm with\nexplicit diversity control; Peng, Lü & Cheng (2015), *A tabu search/path relinking algorithm to\nsolve the job shop scheduling problem*, Computers & Operations Research 53; Shylo & Shams (2018),\n*Boosting binary optimization via binary classification: a case study of job shop scheduling*,\narXiv:1808.10813; Li, Hao & Wu (2024), *Combining hash-based tabu search and frequent pattern\nmining for job-shop scheduling*; Liu, Li & Gao (2026, to appear), a knowledge-driven decoupling\nand coordinated optimisation framework; lower bounds from Heinz, Hanzálek & Vilím (2024),\n*Reinforcement learning for search tree size minimization in constraint programming*, SSRN\n4938242, and Vaessens (1995) as listed on Taillard's page. Cross-check: Weise's survey table\n(github.com/thomasWeise/jsspInstancesAndResults, 2020-11-24) lists ta41 = 2005 (Vilím, Laborie &\nShaw 2015 detailed results) and ta42 = 1937 (Gonçalves & Resende 2014); those two schedules are\nnot posted anywhere we could decode, so this pack pins the verified 2006 and 1939 instead. If you\nreach 2005 or 1937 you have matched a literature claim; below it you have a record.\n\nInstance data: `tamy0612/JSPLIB` on GitHub (`instances/ta41`..`ta50`, commit ac33e816, 2014-04-22),\nchecked operation-for-operation against Taillard's original `tai30_20.txt` (as mirrored in Weise's\nrepository) on 2026-09-07.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no file or process access. The eval rejects other\n  imports and the names `open`, `exec`, `eval`, `__import__`.\n- Respect `time_budget` (seconds, per call). Deterministic given `seed`.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- **Disjunctive graph + critical path.** Evaluate a set of machine orders by a topological pass\n  over job arcs and machine arcs; the makespan is the longest path. Only moves that touch the\n  critical path can improve the makespan, so every good neighbourhood is defined on critical\n  blocks (maximal runs of consecutive critical operations on one machine).\n- **N5 (Nowicki & Smutnicki 1996):** swap only the first two or last two operations of each critical\n  block. Small, always feasible, and the original *TSAB* tabu search with this neighbourhood, a\n  short tabu list and back-jump tracking to elite solutions was the state of the art for years.\n  **N6 (Balas & Vazacopoulos 1998):** move an operation inside a block to the block's start or end\n  (forward and backward insertions with a feasibility test on head/tail lengths). Larger and\n  stronger; used by Zhang et al.'s TS/SA hybrid and by Peng, Lü & Cheng's tabu search / path\n  relinking, which set three of the records above.\n- **Fast move evaluation.** Recomputing the whole schedule per neighbour costs O(nm); computing\n  heads (longest path from the source) and tails (to the sink) once lets you bound a swap's new\n  makespan in O(1) (Taillard's estimate), so you evaluate the whole neighbourhood and recompute\n  only for the chosen move.\n- **Shifting bottleneck (Adams, Balas & Zawack 1988):** sequence machines one at a time, each as a\n  one-machine problem with heads and tails (Carlier's algorithm), re-optimising already sequenced\n  machines after each insertion. Good starting solutions for 30x20; pair with tabu search.\n- **Starting points and diversification.** Giffler-Thompson active schedules with priority rules\n  (most work remaining, shortest processing time) are cheap; random restarts from them are weak.\n  Path relinking between elite solutions (Peng, Lü & Cheng) and the *big valley* structure\n  (Nowicki & Smutnicki 2005's i-TSAB) are what distinguish record-setting runs from ordinary tabu.\n- The budget is short. A tabu search with an O(1) move estimate does tens of thousands of\n  iterations per second in plain Python on 600 operations; make the inner loop tight (flat lists,\n  no dicts keyed by tuples) before adding cleverness.\n\nWrite one honest line in `NOTES.md`: the idea, and which instances it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for jobshop-taillard-open. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns, for every machine, the order in which the jobs visit it. The eval rebuilds the\nearliest-start schedule from those orders and the job routings, rejects anything that is not a\npermutation per machine or that contains a cycle, and computes the makespan itself. Environment:\n  ZT_EVAL_SEED                    seed handed to schedule() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated instance names (default \"ta41,ta42,ta43,ta44,ta45,ta46,ta47,ta48,ta49,ta50\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to schedule() per instance (default 10)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom collections import deque\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"10\"))\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"ta41,ta42,ta43,ta44,ta45,ta46,ta47,ta48,ta49,ta50\").split(\",\") if x.strip()]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known makespans (upper bounds) and lower bounds for Taillard's 30x20 instances, from Oleg\n# Shylo's bounds page https://optimizizer.com/TA.php (last update 2026-06-29). Every upper bound\n# was re-verified here by decoding the solution posted on that page against the instance data\n# (2026-09-07). None is proven optimal. Update RECORDS when a hub-verified submission goes below.\nRECORDS = {\"ta41\": 2006, \"ta42\": 1939, \"ta43\": 1846, \"ta44\": 1978, \"ta45\": 1999,\n           \"ta46\": 2002, \"ta47\": 1889, \"ta48\": 1937, \"ta49\": 1960, \"ta50\": 1923}\nLOWER_BOUNDS = {\"ta41\": 1912, \"ta42\": 1887, \"ta43\": 1809, \"ta44\": 1952, \"ta45\": 1997,\n                \"ta46\": 1966, \"ta47\": 1816, \"ta48\": 1915, \"ta49\": 1934, \"ta50\": 1837}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in {path.name}: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef load_instance(path: Path) -> list[list[tuple[int, int]]]:\n    \"\"\"JSPLIB / OR-Library layout: `n m`, then one line per job of `machine duration` pairs\n    (machines 0-based) in routing order.\"\"\"\n    toks = path.read_text(encoding=\"utf-8\").split()\n    n, m = int(toks[0]), int(toks[1])\n    if len(toks) != 2 + 2 * n * m:\n        raise ValueError(f\"{path.name}: expected {2 * n * m} numbers after the header, got {len(toks) - 2}\")\n    it = iter(toks[2:])\n    jobs = [[(int(next(it)), int(next(it))) for _ in range(m)] for _ in range(n)]\n    for j, ops in enumerate(jobs):\n        if sorted(mc for mc, _ in ops) != list(range(m)) or any(d < 0 for _, d in ops):\n            raise ValueError(f\"{path.name}: job {j} does not visit every machine exactly once\")\n    return jobs\n\n\ndef makespan(jobs: list[list[tuple[int, int]]], orders, name: str) -> int:\n    \"\"\"Earliest-start schedule implied by the machine orders. Fails on malformed orders or a cycle.\"\"\"\n    n, m = len(jobs), len(jobs[0])\n    if not isinstance(orders, (list, tuple)) or len(orders) != m:\n        fail(f\"schedule({name!r}) must return {m} machine orders, got {type(orders).__name__} of length \"\n             f\"{len(orders) if isinstance(orders, (list, tuple)) else '?'}\", \"wrong_answer\")\n    op_of = {}          # (job, machine) -> operation index within the job\n    for j, ops in enumerate(jobs):\n        for k, (mc, _) in enumerate(ops):\n            op_of[(j, mc)] = k\n    mpred = {}          # (job, k) -> (job', k') scheduled just before it on the same machine\n    msucc = {}\n    for mc, order in enumerate(orders):\n        if not isinstance(order, (list, tuple)) or len(order) != n:\n            fail(f\"schedule({name!r}): machine {mc} order must list all {n} jobs\", \"wrong_answer\")\n        seen = set()\n        prev = None\n        for x in order:\n            if isinstance(x, bool) or not isinstance(x, int) or not 0 <= x < n:\n                fail(f\"schedule({name!r}): machine {mc} order contains {x!r}, not a job index in range({n})\", \"wrong_answer\")\n            if x in seen:\n                fail(f\"schedule({name!r}): machine {mc} order lists job {x} twice\", \"wrong_answer\")\n            seen.add(x)\n            node = (x, op_of[(x, mc)])\n            if prev is not None:\n                mpred[node] = prev\n                msucc[prev] = node\n            prev = node\n    # Kahn's algorithm over the disjunctive graph: job arcs plus the chosen machine arcs.\n    indeg = {}\n    for j in range(n):\n        for k in range(m):\n            indeg[(j, k)] = (1 if k > 0 else 0) + (1 if (j, k) in mpred else 0)\n    ready = deque(node for node, d in indeg.items() if d == 0)\n    finish = {}\n    done = 0\n    while ready:\n        j, k = ready.popleft()\n        start = finish.get((j, k - 1), 0) if k > 0 else 0\n        p = mpred.get((j, k))\n        if p is not None:\n            start = max(start, finish[p])\n        finish[(j, k)] = start + jobs[j][k][1]\n        done += 1\n        for nxt in ((j, k + 1) if k + 1 < m else None, msucc.get((j, k))):\n            if nxt is not None:\n                indeg[nxt] -= 1\n                if indeg[nxt] == 0:\n                    ready.append(nxt)\n    if done != n * m:\n        fail(f\"schedule({name!r}): the machine orders contradict the job routings (cycle); \"\n             f\"only {done} of {n * m} operations could be scheduled\", \"wrong_answer\")\n    return max(finish.values())\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"schedule.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import schedule as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import schedule.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"schedule\"):\n        fail(\"schedule.py must define schedule(name, jobs, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"jssp|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for name in INSTANCES:\n        if name not in RECORDS:\n            fail(f\"no record for instance {name!r}\", \"error\")\n        try:\n            jobs = load_instance(here / \"instances\" / f\"{name}.txt\")\n        except (OSError, ValueError) as e:\n            fail(f\"instance {name}: {e}\", \"error\")\n        handed = [[(mc, d) for mc, d in ops] for ops in jobs]   # the solver may mutate its copy\n        t0 = time.perf_counter()\n        try:\n            orders = cand.schedule(name, handed, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"schedule({name!r}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"schedule({name!r}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        cmax = makespan(jobs, orders, name)\n        per_instance[name] = {\"makespan\": cmax, \"record\": RECORDS[name], \"lower_bound\": LOWER_BOUNDS[name],\n                              \"ratio\": round(RECORDS[name] / cmax, 6), \"seconds\": round(elapsed, 2)}\n        if cmax < RECORDS[name]:\n            beaten.append(name)\n    metric = sum(v[\"ratio\"] for v in per_instance.values()) / len(per_instance)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per_instance, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"instances/ta41.txt":"30 20\n 5 59 13 72  3 92 15 35 19 17  9 48 10 57  6 18 12 55  4 51  2  8 14 68  8 90  7 39 16 79 11 40  0 66 17 55 18 62  1 66\n13 42  2 60 15 52 12 14  4 83  9 95  3 36  7 28  5  4  0 31  8 14 14 23  6 71 19 95  1 69 10 17 18 13 17 23 16 78 11 51\n 8 93  5 12  2 34 18 32 17 59 14 73  0 46  4 25 11 82  3 90 16 70  7 27  6 82  1 85 12 40 15 35 10 61 19 92 13 98  9 53\n13 31  8 95  0 36 11 61  3 92 14 24  7 70  4 15 18 76  6 50 19 18  5 30  2 93  9 62 10 83 15 16 17 75  1 29 12 35 16 31\n 8 27  6 10  2 93 13 26 16 64 11 70 15 16 12 48  9 46  4 37 19 89 17 83  5 71  3 72  7 45  1 73 10 97 18 12 14 57  0 62\n 1  9 13 16 10 75  0 21  2 49 12 97 19  5  5 20 17 26 16 50 18 26  4 20 15  8  8 96  7 50  6 84 14  7 11 52  3 73  9 43\n 2 20  3 76 16  3 17 45 10 53 15  6 13 83 12 77  9 21 19 52  8 32  0 27 18 93 11 81 14 78  1  6  5 93  7 60  4 12  6 35\n12 41 10 59 17 37  4 89  3 87 11 32  2 98 19 24  8 30  9 84 13 49 14 84  7 44 18 16 15 43  6 65 16 44  1 83  5 71  0 71\n10 46 14 36  3 60  0 59  7 53 17 58 19  8  2 33 11 70 16 93  6 38  4  5 18 75  1 23 13 98  5 90 12 18 15 62  8  4  9 56\n 0 27  2 31  3 45  9 57  8 79 12 14 16 82 13 96  4  4 10 17  6 46 19  3 15  7  1 42  5 24 17 86  7 67 14 79 18 43 11 17\n 1 72  4 54  0 51 10 87 15 52 11  4 16 35  9 62 19 15 13 45 14 84  8 65  6 85 17 49 18 98 12  5  2 81  7  8  3 72  5 33\n 6 31  5 86  9 46 10  3  0 63  2 58  3 81 12  7 11 54  7 39 13 46  8 92 19 96 14 57 16 40  4 49 17 57  1 86 18 20 15 91\n13 35 19  5 11 43  5 84  2 77 15 20 14 84  4 70  3 79  6 52 10 92  1 34 12 39 18 30  9 65  7 11 16 88 17 32  8 80  0  2\n10 59  3 36  4 72  9 46 17 48  8 72  0 76 19 48  2 69 11 62 12 30  1 48 18  7 15 89  5 37 16 49  6 30 14 52 13  1  7 56\n 4 18 14 35  8 61 15 23 11 46  9 12 10 38  1 59 17 50 16 75  5 60 18 57  6 63 13 89 19 71 12 52  7 83  3 86  2 81  0 98\n 4 33  9 14 18 19 19 84  3 69 17 59 15  2 16 83  5 12  8 21 11 73 14 83  0 26  2 94  1 65 12 98  6 83 10 45 13 40  7 89\n17 63 10 72 13 80 19  2  0 94 12 11 14 25 18 10  2 90  5 73 11 20 16 92  7 11  4 85  8 63  1 97 15 38  6 13  9 42  3 59\n19 95 13  4  9 95  3  6  6 67 17 30  7 88 16 26  5 57 14 61 15  9 18 35  0 23  2 47  1 46 12 96  8 19 11 54 10 75  4 11\n 9 64 11 79 17 87 13 91  3  2  1 61 10 31 16 85  0 53  5 77  7 25  6 94  4 43  2 13 18 40 15 59 14  3 19 80  8  7 12 98\n17 56  8 12 13 74  7 42  4 98  0 75  6 18  9 98 16 20 18 72 11 34  5 74 10 10 12 98  2 12 19 95 15 33 14 69  3 93  1 81\n17 73  2 38  7 25 16 92  6 38 12 91 14 95  9  2  3 79 18 41  0  3  4 99  5 83  8 18  1 12 19 71 10  4 11 66 15 20 13 53\n 0 61  7 24 16 24 12 22  3 85  6 56 19 98  2  5 10 29  9 73 18 27  8 99 13  4  5 99 11 63  4 25 15 61  1 51 17 84 14 30\n10  5 18 17  4 40  5 88 12 30  6  3  9  1  1 96 11  9 13 94  8 69  7 72 17 90  0 14  2 41 14 50 19 69 15 38 16 12  3  1\n14 55  0 19  5 61 11 61  9 97 19 76 10 38 15 69  2 24  3 62  4 24 18 94 17  3 13  5 12 84  7 43  6 73  1 76 16 47  8 91\n11 85  6 98 18 68 14 57 16 63  0 58 17 74 10 52  9 59  2 47  7 73  4 79 19 48  5 38  8 88  1 85 12  4 15 44 13 37  3 75\n18 44 13 32 10 38 12 93  1 40  9 56  0 80  7 90  2 74  5 82 16 59  6 91 17 40  8 26 14 74  3  7  4 49 11 88 19 60 15 35\n14 75  2 73 19 13 10  4 11 77 16  5  9 57  7 98 15 60  1 99  5 12 13 14  4 25  8 86 18 13  0 93  3 41 12  1  6 53 17 54\n 0 33 18 75  8 97  9 31 12 84 17 49 16 51 19 30 15 62 11 67  2 84 13 45  3 48 10 62  5 64  7 87  6 14  4 76  1 42 14 71\n18 74 11 98  9 11 14 96  4 39  0 31 16 54  3 49  8 51  6 40 13 21 15 19  7 44  2 76 10 64 12 43 19  9 17 30  5 66  1 17\n16 31  3 77  9 92  6 27  2 71 18 82 11 36  1 33  4 48  0 91  5 49  7 39 12 91 15 47  8 74 14 17 13 62 19 28 10 91 17 58\n","instances/ta42.txt":"30 20\n 4 11 10 45 12 34  5 61  3  8  8 97 19 59 15 72  6 82  0 57 11 87 13 61  1 90 16  4 17 17 18 69  2 95 14 15  7 97  9 93\n 6 57  1 64  2 15 13 19 11 14  3 54 12 71 14 29 10 17 19 43  7 81 18 87 16 65 17 62 15 80  5 75  0 19  4 48  9 33  8 68\n17 71 15  1  8 90 16 81  1 84 10 19 13 75 14 83  6 25 12 69  0  1  9 80  5 35 18 76  2 37  4 23  3 13 19  4 11 81  7 20\n 7 16  1 91  2 22 17 28 16 89  8 99  9 69  4 22 15 85 14 25  6 60 18 33 13 17  3  6  0 94 11 56 19  8 12 77  5 54 10 82\n10  3  1 51  7 43  3 21 17 66  0 71  2 17 18 98 12 73 16 76  6 93 13 88 11 61  8 79 15  9 19 18  9 31 14 80  5  4  4 32\n 4 44  8 97  3  7  9 54 12 12  2 68  6 26 18 42  5 19 19 92  1 57 11 71 17 67  0  2 13 49 16 40 14 51  7 27 15 35 10 22\n17  5  4 55 13  2 19  6 15 65  3 42  2 19  1 64  7 51 16  4  8 13 10 46 12 52  6 38 11 15  9 87 14 74 18 64  5 80  0 91\n10 92  1 39  0 24 17 71 18 12  7 37 16 64  6 17 15 95 12 52  2  9 11  3  4 87  8 46 14 71  5 29 19 22 13 62  3 43  9 51\n17 78  0 91  9 26  7 81  4 43  2 43  5 93 18 35 11 36 12 74 14 18 13 30 19 15  3 64  8 90 10 75  1 37 15 35  6 39 16 87\n11 14  1 21  9 74 16 30 12 62  3 70  6 87 13 29 10 86 14 88  8 24 19 54  4 11 18 15  0 21  5 29 17 57 15 75  2 57  7 43\n19 40 18 34 14 46 10 97 13 67  5 59  3 65 11 47  8 20  7 22 16 15  0 66  6 20  4 40  2 72 12 73  9 50 15  4 17 88  1 44\n 5 33 18  9  6 84  9 70 17 56 12 60  3 16 14 84 15 13  0 47 19 65  4 76  2 51  1 34 10 53  8 63 16 14 11 84 13 78  7 92\n 2 67  0 18  5 66 18 37 19 65  9 92  7 30 10 57 11  1  4 16  8 89 15 36 17 30  1 49 14  7  6 73 12 20 13 26 16 29  3 42\n10 99 12 72  4 22  8 79 13 60 17 28  2 59 19 95 15 84 16 49  3 86  0 37  6 10  5 68  1 70 11 20 18 71 14 23  7 71  9 51\n 1 39 16 88 19 82  0 41 17 99 15 45  2 11  9 48  3  2  6  8 10 88 18 95  7 64 14  7 13 62  8 19 12 61 11 60  4 45  5 32\n 2 81 14 18  9 77 16 33  3 17  0  9  4  5 12 76 13 75 19 65 17 11 15 69  8 17 18 66 11 36  7 23  6 75  1 64  5 14 10 42\n17 47  8 51 19 60  7 94  4 15 18 13 12  8 13 16  3 61 11 72  6 69  9 17  1 44  5 84 10 97 15 93  0 91 14 60  2 99 16 57\n13 28  2 70  6 42 14 96 18 14  7 81  8 57  0 16 16 45  1 44  3 40 10 11 19 70  4 97 12 20 11 80  5 24 15 27 17 55  9 13\n15 92 19  4 11 31  0 76  4 91 10 66  7 59  1 97  8 15  6 27  9 15 18 62 14 82 13 94  3 55 12 52  2 77  5 39 16 38 17 53\n17 17  8 99  4 47 10 82 12 14  0  2 11 82  9 69  7  6 16 89 18 66 19 39  1  9 13 90  3 91  6 63  2 13 14 34 15 36  5 81\n 8 99  1 68 11 56 19 70 16 72  5 77 17 51  7 64  2 66 15 57 12 74  0  9  9 72  3 94 13 63  6 21  4 39 10 23 14 80 18  8\n16 67 13 22  0 59  1 37 10  6 15 64 14 17  8 50 17 45 18 30 19  7  2 78  4 72 12 36  7 23  6 94  9 25 11 74  3  6  5 97\n 7 42  6 90  4 28 17 19 15  7 14 97 19 82  8 41 10 69  0 47  3 76 12 88 16 11  5 68 13 70  9 31 18  8  2 81  1  3 11 84\n 9 62  1 34  4 98 11 65 17 12 16 66 12 32 14 60  6 12  2 85 15 73  5 55 10 97  0 24  8  9 13 26 18 92  3  3  7 41 19 83\n12 12  3 93 14 74 10 20  0 33  4 89 11 41  5 96 15  4  9 99  2 47  6 23  8 12 13 91 18 25 17 83  1 34 16 83  7 70 19 27\n13 99  8 50  4 17  6  9  3 72  7 91 19 37  2 39  5 72  9 31 18 72 11 97 10 40 16 43  0 96  1 51 14 29 12 21 17 18 15 50\n10 55  0 41  1  4 13 75 12 86 11 59  5 44  8 73 19 66  2 70  3 79  7 85  4 51  6  5 17 35  9 17 15 30 16 35 14 34 18 91\n16 97 19 32 13 41  3 33 15 23  1 39  8 74 14 49 12 69  2 28  5 55 17 60  0 61  9 84 11  2 10 84 18 17  4 73  6 26  7 91\n11 21  4 51  8 99 13 79  5 21  3 48 18 44  1 67 17 48 14 96 12 19  9 39  6 56 19 76 10 16  2 40  0 69  7 93 15 15 16 52\n16 45 11 22 14 89  8 42 19 43  5 99 17 91 12 34  3 43 15 68 13 76 18 55  9  1  6 73  1 56  0 89  7 13 10 99  4 82  2 72\n","instances/ta43.txt":"30 20\n 3 86 17  5 14 21 10 67  5 87 12 90 18 21  8 87 15 82  4 68  1 25  7 10  9 58  6 65 16 20  0 34 13 12  2 35 11 63 19 41\n 8 91  7 80 12 38 14 79  1 66  4  6 17 21 19 89  9 50 15 93  0 52  3 33  2 82  6 51 11 90 16 55 10 99  5 75 18 22 13 58\n18 59 14 22  1 10 11  1  0 75  6  1 12 35  4 15 15 39  5 28 13 29 17  8  9 65 16 45  8  5  2 90 19 18  3 11  7 39 10 70\n15 20  1 39  4  2 11 32  3 44  2 85 17 30 10 68 14 67 13 57 16 14  7 75 18 71  0 41 12 36  5 33  8 72  9 32  6 92 19 17\n 5 82 10 71 15 55 13 28 16 73 19 12 18 18  2 41  4 78  7 71  8 26 17 97 11 23  9 65 14 54  6 88  3 94  0 28 12 22  1 95\n 9  5 16 29  1 73  5 69  6 51 11 70 13 24 14 89  2 21  0 89  4 83 17 14 15 61 19 12 10 97 18 57  8 61  3 61  7 19 12  3\n 2 43  6  4  7 32 14  4  4 96 12 34 15 21 16  2 13 33  5 77  1 62 10 39  0 89 17 90  9 90 18 42  3 16 19 73  8 75 11 57\n 8 78 14 63 13 26 16 48 10  9  7 26  2 55 19 93  0 15  6 85  5 39 12 87  4 66 11 54  1 68  3 30 18  7 17 52  9  2 15 31\n 3 55  0 87 14 10  4  5 15 48  6 78  8 87  5  8 17 70  9 69 13 57 16 85  1 58  2 74 12 92 10 77 18 54 19 43  7 28 11  6\n 1 42 19 71  0 68  7 77  2 19  6 12 10 59  4 74 17 71  5 22 12  7 13 53 14 99 15 71 18 88 16 91  3 22  8 46  9 80 11 55\n 9 77  0 17  1 79 13  1  3 72 16 88 14 42  2 83  5 84 12  8  7 40  8 91 19 66  4 85 18 43 10 51 11 94  6 23 15 84 17 15\n 1  6 14 41  4  5 11 87  2 46  7 75  3 49 12  6 16  1  9 50 13 88 17 65 18 10  0 88 10 46 15 33  5 47  8 72  6 48 19 12\n 0 56  9 75 10 53  4 34  2 73  3 83  7 72 12 15 11 28 17 52 14 49 15 15 13 81  6 88  8 11 19 52 18 48  1 88 16 18  5 46\n17 68 11 36  5 34  3 11 14 63  7 31  1 30 15 59 10 85 12 60 13 78 16 82  2  6 18 88 19 43  0 66  9 93  8 82  4 39  6 16\n 3 58 19 48  4 97 10 67  2  3  1 85 11 36 15 24  0  2  5 37 14 72 17  2  8 25 13 74 12 46  6 43  7 62  9 27 18 77 16 82\n 9  5  0 93  6 79 14 40  3  4 11 82  8 73 10 71  2 61 13 65 15 74 19  2  4 57 18 78 17 12 12  1  1 83  5 10  7 85 16 48\n17 75 12 63 18 16  6 15 14 42 16 34 13 27  2  3  9 83 19  7  7 12  3 63  8 94 11 20  0 35  4 75  1 52  5 25 15 98 10 83\n 3 39 15 65  0 21  2 34  4 66  6 27  9 81 10 33 14 29 16 95 11  1  5 64 17 82 13 61 18 74 19 51  8 48  1 99 12 23  7 57\n 0 88  6 93 17 11  4 90  1 27  2 63 18 20 12 51 11 36 16 76 10 26 15 10  3 71 13 74  8 35 14 48 19 12  7 36  9 24  5 10\n 6 93 19 56  3 28 13 57 18 21  4 59  7 48  1  6  9 16 16 90  8  6 17 49 10 32 14 82  2  3 15  4 11 31 12 25  5  8  0 28\n 8 68 18 11  7 99 14  3  0 78 11  1  4 39  9 65 13 19  5 16  3 11 12 26 17 10 16 54  2  2 15 69 19 91  6 39 10  1  1 91\n15 10  0 24  8 55  9 71 13 99  5 85  3 58 16 18 10 11 17 90  1  7  7 88 14 75  4 97 18 75  2 11 12  8  6  6 19 45 11 78\n14 68 17 57 19 15  5 36 16 27  6 26  4 66 10 38 15 97 18 55 12 73 13 23  8 68  2 19  7 89  9 46  1 34  0 39 11 23  3 60\n19 28 13 20  2 44 17 81  9 62  1 66  4 44  0 52  3 40 11 89 10 92  8 27 18  6 14 75 16  6 12 96 15 50  7 73  5 60  6 31\n 6 90 14 55 15 41  7 20  4 51 16 44 11 67  0  6  1 82 10  5 17 10 19 63 13 80 18 39  3 22 12 48  8 24  5 66  2 46  9 91\n 8 41  6  4  4 34  7 68 15 58 10 71 18 57  3 81 13 62 19 84 14 57  5 23  0 31  2 59 11 18 16 74 17 60 12 38  9 70  1 49\n 4 53  0  6  5 79  8 84  9  3 18 41 14 28 15 61 10 43 12 36 13 68  7  8 11 35  3 73 16 81  2 93  6  1  1 94 19 96 17 73\n18 92  7 94  3 54  9 17 14 11  6 41  0 55 15 15  8 87 19 81 11 62 12 78 13 28  5  8 10 77  4 82  1  1 16 68  2 84 17 58\n 3 82 15 31 11 12  9 78 16 83  5 33 12 39 19 78 13 33  0 11 17 91  2 54  8 26  1 90  6 71 14 12 18 28  4 57  7 99 10 49\n 7 37 18 17 16  3 10 57  4 71  3 82 11  9  0 29 17 17 14 99  2 96  5 97  9 10  6 26 19 36 15 32 13 14 12 35  8 34  1  8\n","instances/ta44.txt":"30 20\n 5 51  0 93  6 49 16  1  2 52 15 26 19 74 10 59 12 44 13  8  4 81  3 95  9 68 17 57 18 57  1 40  7 17  8 92 14 88 11  6\n17 75 11 22 16 11 13 49  1 31  7 32  4  5 14 51 10 14  8 43  2 43 19 24  3 83 12 67  6  2  5 45  0 75 15 35  9 50 18 95\n15 80  9 13 18 36 19 51  1 63 16 58 17 30  8 75  0 72 14 92 13 13  2 13  7 92  3 12 12 76 11 29  5 64  6 58 10 26  4 21\n13 91  1 95 19 51  2 75 10 89  6 56  8 74  3 60  0 86 16 70  9 97  5 11 14 61 17 68 15 43 11  5 12 17  4 18 18 14  7 93\n13 40  3  9  2 80 19 82  1 67  0 33 15 84  6 39 18 48 14 89  5 95 16 60 17  4  9 99 11 92 10 52 12 79  7  9  4 89  8 54\n 6 55 17 70 14 95 19 60  7  9 12 82  3 52 18 30  5  6 11 27  8 57  0 89  1 63 15 29 16 55 10 37 13 66  4 16  2 87  9 63\n 0 44 10 47 15 90 11 35 17 79 14 57  5 58  6 98  8 62  3  8  9 31 16 94 12 49  2 90  1 11 19 63 18 22 13 44  7 96  4 86\n 9 63 10 80  8 72 13 83 16 25 18 55 15 68  3 42  6 70  5 64  1 24 11  7 14 45  0 12  7 17 17  8  2 41 12 88  4  7 19 83\n 4 68  6 99 19 37  5 33  2 72  9 98 16 92 18 28  7 14  8 16 12 99  1  9 15 93 13 25 17  8 10 64  0  4 14 74  3 35 11 37\n17 79  1 34 12 36  5 83  2 48  3 23  8  2  7  5  6 16  9 76 19 10 15 95 14 12 10 94  4 46 18 53 11 35 16 73 13 78  0 55\n17 31 15 75 11 11  0 92  7 46  6 84  5 39  9 17  4 83 12 87 10 86  2 93 14 68 16 67 19 83  3  4 13 96  8  3  1  7 18 51\n13  4 14 50  2 20  5 74  0 37 11 95 16 65 17 83 15 98  9 25 18 64  6 90 19 51  7 61 12 97  3 70  4 14  1 13 10 99  8 83\n 3 41  5 81 13 93  0 78 14 53 12 66 11 40 16  8  2 63 19 66  8  2  9 36 15 24  4 61  7 75 17 27  6 71 18 23 10 18  1 60\n15 87  5 29 18 36 17  2  6 18 16  2 13 11 12 47  3 94  2 92  9 58  0 93  1 47 14 90  8 28 10 54 11 28 19 84  4 68  7  4\n10 23  6 74 19 95 15 64  4 21 17 46  8 86  1  8 12 58 18 64  0 99  9 29  3 47  5 64 13  6 11 25  2 63 16 59  7 96 14 19\n 3 75  9 75 16 76  6 83  7 22 11 98 14 85  8 75 18 11 12 64  5 21 17 94 19 46 10 63  2 78  1 35  0  9 15 16 13 39  4 28\n13 57 18 66  5 46  6 84  8 16  0 19  4  1 10 29  7 65 12 42  1 87 15 38  3 88 16 83 19 86  2 21 11 38 17 61  9 29 14 74\n 5 66 15 74  1 43  2 55 19 86 18 69 12 11 13 12 16 61 17 56 14 56  9 77  0 80 11 16 10 13  3 14  8 14  4 96  6 88  7 20\n 8 52 14  1  6 82  3 57 11 18  4 94 12 44 15 81  1 25  0 75 17 29  7 74  5 10 10 24 19 63  2 42 18 62 13 98 16 67  9 72\n10 81  0 95 14 46  2  6 16  5 19 18 17 79  6 43  3 28  8 27 12 84 11 83  7 99 13 60 15 86  9 21  1 13  5 28  4 91 18 20\n17 63 14 56  1 24  4 43  7 30 16 22  0 31 18 64 19 56 13 62 15 25  8 85  2 13 11 76 10 63  6 51  3 87 12 21  9 65  5  1\n14 54 16  1 17 71  5 76  4 23  8 90 10 19 12 97  3 84 19 27  2 70  9 38 18 62 13 94 15 47  0 22  7 52  1 21  6 11 11 97\n 1 91 14 67  2 12  8 75 13 42  6 38 12 63  3 92  5 41 18 14 17 28 11 84 10 39  0 49  7 23 19 58 15  9  4 19 16 17  9 46\n 7 89 11 44  3 61  9 63  8 95  4 70 18 49  5 99 14 44  0 68 10 86 13 86  1 11  2 13 15 17 17 85 19 62  6 80 12 37 16  2\n19 39  6 42  9 19 16 81 17 46  8 87 14  7 11 58  7 27 10 97 18 53  2 21  3 69  0 97  1 64 12 47  4 11  5 43 15 67 13 11\n 2  4 16 13 17 44  6 27  3 23  4 25 11 44  5 39 18 38 14 31 15 38 19 95  0 13  9 19  7 29 12 37 13 44 10 77  1 24  8 39\n13 56 11 91 16 37 14 36  6 86 15  2  1 39 17 19  0 90 12 43  5 72  3 87  2 37  4 39  7 90  8 33 10 73  9 88 18 34 19 66\n10 56  2 32  6 48  0  6 19  9 14 57  7 21 12 56 18 37 16 75  5 40  9 93 15 97  3  5 11 67 13 24  1 20 17 15  4 16  8 21\n15 31 19 30 11 88 17 45 18 37 13 38  4  3  6 97  8 40 12 29  3 24 14 30  1 29 10 45 16 51  2 58  5 82  0 51  7 85  9 37\n 0 38 18 77 19  8  6 48 11 46  4 89  5 96 13 50  2 21 12 38 17 57  3 26  1 97 16 70  8 23 10 18  9 33  7 34 14 35 15 69\n","instances/ta45.txt":"30 20\n11 38 18 65 19 92  9 13  1 61 10 56  3 95 13 77  7 40  5 23 15 87  0 96  4 95  6 51  8 98 17 44 16 10  2 57 14 44 12 28\n 8 81 15 37 18 13 16 48  6  7  0 87  2 12 11 23 13 83  7 69 10 26 19 61  9 16 12 60  3 79 17 52 14 84  4 93  5 73  1 92\n17 70 18  1  2 72  4 36 14 66  7 65 10 62 12 98 13 22  0 65 19 26 15 89  5 12 16 52  1 73 11 52  9 28  6 60  8 11  3 26\n 2  4 17 27  4 65 10 39  9 93  6 12 12 92  8 86  5  9 18 87  3 65  7 79 16 92 11 41 19 97 14 45 15 84 13 89  1 64  0 37\n 4 60 11 89 18 16  9 24  2 49 12 93 16 80  5 35  7 61  6 46  8 36 15 68  3 23 13 13 14 51 10 25  0 76  1 46 19 98 17 58\n 4 35  6 18 16 72 18 86 14 99  2 52  7 48  9 98  1 58 15  7 10 26 12 15  5  3  8 37 19 92 13  9 17 63  3 20  0 91 11 86\n19 56 14 10 11 62  3  8  6 50  9 19 15 53  4 69  2 67 12  8 17 10 10 22 13 40  8 85  0 44 16 22  7  1  1 90  5 47 18 59\n 6 82  9 83 17 75 12 89 16 72  5 39  0 47  8 39  1 15  3  1 14 64 13 66  7 17  2 68  4 43 15 63 18 96 11 37 10 64 19 35\n10 58 16 48 17 19  5 17 15 33 18 29 14 46  2 81  0 11  1 88  4 58 13 70  7 99 12 96  9 90  6 46  8 69  3 92 19  4 11 45\n 6 74 11 78 15 79 17 44 14  2  9 63  7 68 10 57 16 33 19 90  8 69  1 91  4 35 13 80  5 26  0 44  3 91 12 27 18  2  2 61\n10 59 11 46  7 81 14 42  5 53  2 44 19 21 15 45  1 91 12  4  8 76  0 18 16 72 13 78  9 20  4 44 17 52  3 37 18 68  6 33\n19  2  9 63  0 82  3 37 14  3  7 53 13 89  6 31 11 63  8  6 15 98 10  2  4 23 12 38  1 87  2 91 18 60 17 55  5 93 16 38\n 6 74 16 85 10 55 13 52  9 87 18 25 14 85  4 33  1 42  8 65 17 59  5 91  2 91 12 16  3 30 19 62  0 70  7 14 15 35 11 19\n 4 16 11 23  5 70  0 41 15 12 12 99 13 26 19 43 14 14  3 91 16 50 10 78  9  1  1  2 18  4  6 80 17 14  8 63  7 55  2 14\n 1 86 12 32  3 56 15 81 11 52  2 14  5  7  8 74 16 33  9 69 17 23  7 68  4 45 13 19  6 38 14 35  0 21 10 42 19 86 18 98\n19 33 12 51  7 96 14  5 13 56 10 90  2 50 11 41  3 34  0 93 16 61 17 67  9 60  1 31 18  5 15 41  8 85  5 58  6 57  4 10\n16 25 19 92 12 17  9 94  3 67  5 60  6 71 17 28 13 70  4 97  8 56  7 29  1 56 10 41 14 57  0 70 11 26 15 50  2  2 18 44\n 7 27  6 48  0 85 19 17  9  1  3 86 16 88  8 43 11 58  4 82 12 51  2 59 13 38 17 99 18  7 15 49  1 88 14 56  5 80 10  1\n12 61  9 48 19 90 14 59  7 80  8 44  0 26 13 44 16 86 11 31  6 72  3 29  1 68  2 29  4 49  5 23 10 59 15 61 18 70 17 49\n 1 37  4 45 18 24 11 88  0 18 16 33 12 42  8  4 13  7  7 69  2 68 19 39  3 87  5 61  9 42 15 16 17 43 14 83 10  6  6 36\n10 91 16 35  3  9  5 98  4 49  7 96 11 68 19 81 15 10 14 58  9 21  8 90  6 26 18 36 12 91  0 52  1  9  2 49 13 15 17 80\n 5 11  4 78  7 59  8 47  0 11 11 24  1 55  3 87 17 28 14  2 16 23 19 38 15 71 13 69 10 97  6 74 12 43  2 57  9 44 18 23\n13 13 14 54 16 19  5  3  0  4  7 13 18 77 12 74  1  2  3 66 19 81 17 60 11 38  4 90  2 67  9 34 15 27  8 57  6 72 10  7\n14 29 16 69 19 13 15 96  7 90 11 24  4 90  9  3 10 57  3 83 18 78  6  4 13 24 17 65  2 44  0 21  5 56 12 73  1 93  8 97\n 8 53 13 13  6 18  5 33  1 79 19 45 14 17 17 47  9 45  0 79 12  7 11 89  3 51  4 32  7 26 10 32 15 43 18 62 16 31  2 14\n 0 63 19 56 12 68 16 49 10 40  5 51 14  3  8 87  7 63  9 52 18 95  1 56 11 97  6 30 17 99 15 39 13  6  2 76  4 34  3 73\n12 68 14 31 11 59  6  6  0 30  9 58  3 73 13 62  4 71  1 96 18 23 15 71  8 20  5 11  2 50  7 92 10 62 16 67 17 10 19 65\n18 98 13 83  7 89 15 64  1  4 11 27  0 79 14 25  2 78  3 36  8 52 10 41  6 21  4 62 12 78 17 92  5 92 19 88 16 80  9 64\n11 88  5 78  7 10 10 14  8  8  1 18  2 10  6 37 14 49 12 27 17 94 13 95  0 37  4 23 16 15  9 87  3 54 19  1 15 74 18 40\n 0 21  1  3 19 32 10 51 16  9 14 76  5 23  6 73 12 53  3 81  7 74  4 92 18 69 17 56  9 93 15 52  2 83 13  1 11 17  8 46\n","instances/ta46.txt":"30 20\n19 49 12 91 14  1 10 37 15 32  7 69 11 56 17 65  1 45  5 66  8 17  0 72 18 38  2 64  3 20  4 68  9 71 13 51  6 17 16 26\n10 59  5 43 11 90  8 51 16 96  6 62 19 35 15  6  0 54 13 81  1  3 17 80  3 94  7 39 18 37  4 21  2 52 14 51  9 36 12 89\n15 57 19 90 10 34  5 37  6 60  7 51  3 27  9 29  1 53 16 20 17 45 11 16 14  2 12 24  4 34 18 18  2  2  8 75 13 78  0 46\n13 33  9 15 14 68 18 19  1 43 11  7 19  2  2 19  3 15  4 58 10 80  5 48 12 49 17 82  6 63  8 26 16  4  0 38 15 62  7 41\n 3 82  2 63 10 72  8 47  1 56  4 89  5 71 15 91 12 75 11 93 13 59  7 58  0 20 16 84 17 63  9 50  6 48 19 85 14 39 18 45\n19 56 11 32  6 34  9 30  7 40 18 67 13 30 14 49 15 17  0 17 16 15  8 58 12 47  3 15 10 21  1 74  5 85 17  7  2 41  4 79\n15  5 10 76  5 48  9 58 19 23  0 44  8 63 18 56 12 59 13 72  6 34  4 82 17 86 14 43  7 70  2 41  1 97 16 57  3 38 11 24\n19 59  5 34 14 66  3 20  4 13 12 88 15 95 13  6  6 68 18 41  7 51  9 20 11 80  1  1 16 43 10  6 17 37  0 34  2 72  8 62\n12 55  5 59 19 53 10 74  8 77 11 72  0 76 17 95  4 66  6  2 13 26  9 53 16 41  3 28  2 26 14 69  7 74 15 60  1 79 18  5\n 9 63 15 94 12 86  5 97  3 94 13 82 19 88  8 25 16 10  4 72 18 39 17 49  7  5  2 38  6 85  0 42 10 89  1 22 14 34 11 18\n 1 62 19 65 18 25 10 74  6 48  2 73 15 92 14 69  7  2 17 17 11 79 13 81  5 55 12 37 16 79  4 95  0 94  9 31  3 16  8 44\n11 53 19 14  2 77 17 92 14 32  7 47 15 93  4 41  5  6  0 71  1 69  8 70  3 96 10 11 13 39 16 10 12 15  6 39  9 98 18 29\n 6 25  5 80  3 38 11 44 13 78 14 39  9 29 12 40  8  5  0 47 19 61  1 47  2 63 18 80  4 46  7 76 15 15 17 54 10 21 16 25\n 2 53  6 99  4 44 12 54 17 89 16 75  0 26 10 58  7 30  3 17  5  3 18 17  1 14  8  1  9 60 19 49 15 76 11 83 14  9 13 32\n 9 22  5 10  1 94  7 54 11 91  0 99  8 91 12  8  2 39 19 59 10  3  6 55  4 29 15 37 13  6 18 64 14 81 16 84  3 29 17 95\n14 72 11 67  5 29 10 57  4  9  3 40  1 78 13 99  7 53 15 66  2 85 17 31  0 42 19 83 18 46  8 27  9 47  6 60 16 67 12 47\n 2 45 12 44  5 83 13  8 17 60  4  2 14 10  7  3  6 29 11  9 19 37  0 29 16 22 10 97 15  6  3 41  9 81 18 74  1 62  8 95\n 5 92  4 37  2 32 15 28 10 29  3 62 14 93  7 30 19 92  0 45 11 35 17 77  8 46 12 47 16 46  9 81  1 43 13 43  6 30 18 18\n 4 49  9 86 13 20  5 90  8  4  6 44  7 72 17 22  0 90 12  1  1 30  3 71 16 77 15 62 19 48 10 25  2 89 11  6 18 95 14 44\n14 62  3 63 16 92 10 16  6 20  2 69  5 65  0 81 13 21 12 54  9 97  7 79  8 37 19 97 18 93  1 55 17 70 15 60 11 36  4 57\n17 76 13 54 16 76 15 36  5 93  4 67  3 35 11 37  0 44  7 88 10  3  2 22 12 73 14 65  1 26  8  3 19 99 18 78  9 38  6 30\n 2 77  9 82 17 66  4 75  7 95  5 72  0 76 18 52 19 72 13  4 11 70  1 76  8 61 15 88 16 39 12 36 10 88  6 69 14 58  3 14\n12 65  4  8 18 90  1 57 19 73  5  2 14 62  8 48  0 76 10 87 15 53  6 23 17 76  2 74 11 99 16 34  3 71 13 27  9 87  7 46\n13 76  6 54 11 75  5 69 17 44 16 26 19 63 10 75  0 78  4 78  3 39  1  7  9 73 18 27  2 55 14 23  7 55  8 29 15 56 12 36\n14 17  9 42 13 56 11 84  2 44  5 74  6 62 17 55  8 55  4 31 12 71  0 11 15 16  1 29 18 50 19 72  3 64  7 42 16 28 10 70\n 9 76 18 56  6 78  8  2  1  6  4 71 16 19  7 69 12 30 10 87 13 57 17 33  5 87  2 68  0 24 11 31 19 56 15  5 14 19  3 82\n 2 64 19 36 15 19  8 90 14 65  3 80  4 26  1  2  6 52 11 72 17 17 12 29 13 60  5 16  9  6 16 91 18 79  7 43 10 99  0 26\n19 82  1 80 17 60  6 93 13 54  2 24 12 87  8 63  0 59  9 85 11 13  3 32 10 93  4 33 15 15  7 48 16 72 18 23  5 97 14 76\n17 61 14  6  6 87  5 74 18 67 16 44 13 63  0 12 19 81  9 61  2 26  7 23 10 76  8 93  4 97  1 75 12 76 15 46  3 66 11 54\n19 77  7  6  8 62  0 22  4 81  3 44 18 28  9 97  5 16  2  7 12 34 11  3 13 93 17 12 15 35  6 88 14  9 10 93  1 87 16 51\n","instances/ta47.txt":"30 20\n11 66 19 38 16 15  7  7 12 93  1 57 10 92  8 56  6 93 18 60  2 40 13 74 17 59 14 72  0 21  3 24 15 24  4 57  5 74  9 69\n 4 88 19 70  8 42 17 14  0 66  5  8  1 32  6 77 11 11 12 30 10 48 13 97  2 89  3 82 15 81 18 89 16 76  7 87 14 44  9 26\n19 53 10 82 14 37 11 85  3 31  2 81 13 24  1 67  0  3 12 12  9  8 18 72  4 87  5 69 16 19 17 35  7 97  6 46  8 73 15 12\n 2 31 15 50  6 74 19 12 17 52 14 89 12 67 13 52  1 21 11 11  5 31  4 69  9 35 16 99 18 24 10 93  8 87  7 15  0 20  3 66\n17 14  8 90 10 14 16 68 19  6  4 79  2 14  6 15  0 17  3 68  9 19 12 46 11 72  7 33  1 20 15 12 14 56 13 97 18 26  5 36\n 5 71  6 95 13  2 10 81 19 93 16 21  9 98  8 64 15 30 12 40  4 67  7 65 14 16 11 33 17 51  3 49 18 68  2 89  0 92  1 35\n 2 28 19 33  4 81  8 94  9 11  6 61  7 36  5 33 11 92  1 83 13 14 14 97 17 36 18 61 10 72  3 65 12 26 16 14  0  4 15 80\n16 70  7 96  1 35  6 11  5 99 12 83  4 39 10 43 14 87 15 19  8 14 18 46  0 91  3 17  9 32 11 32 17 38 13 46 19 96  2 22\n12 69  0 36  2  8  4 21  1  2  6 32 14 75 16 81 19 47  3 64 17 80  5 75 11 49  8 41  9 82 10 25 13 89 15 33  7 29 18 47\n 6  9 17 36 13 22 19 59 16 32 18 33 11 72 10 27  3 45  2 19 14 49  8 35  5 57  7 87 15 59  9 49 12 83  4 52  0 66  1 61\n12 24 18 53 11 61  7 31 17 14 10 19  6 26  9 91  3 53 19 41 14 77  1 66  4 81 15 32  0 29  2 83 13 13  5 31  8  6 16 21\n 0 45 18 89 11 29  3  7 15 47 10 47  5 25  4 45  7 60 13 28  8 83 19 68 17 12  2 37 14 69  1 46  6 47 16 91  9 20 12 45\n 3 23  4 55  7 60  6 52  5 17 15 75  8 54 13 76 17 35 12 61  9 51 10 84 18 38  2 94 14 30  0 14 11 78  1 29 19 99 16 88\n 5 14 12 22 14 99  6 59  3 89 10 44 13 98  7 56  8 22 17 33 15 41 18 46  4 65  0 85  1 38 16  3  9 19 11 39  2  5 19 72\n 7 12  4 27 10  8 13 13 11 26 16 35 18 33 12 49  8 29 15 39 19 37  1  1  0 74 17 22  2 38  3 31  9  6 14 98  6 86  5 69\n 0 72 17 74  4  6 15 58 11 27  3 21 14 19 13 97 10  8  7 70  8 49  1 25  9 39 16 95  5 71 18 81 12 88  6 11 19 93  2 71\n19 11  1 82 11 82 17 80  5 74 18 60  7 43 10 75 12  4  2 64  0 52  3 73  4 77 13 80  6 89  8 66 16 28  9 62 15 82 14 42\n 3 11 12 16  1 12 15 72  7 35  6 83  8 73  9 41 13 23 16 63 19 16 10 37  4 28 17 88  5 75 18 51 14 23  2 40  0  4 11 78\n11 53 10 30 15 85 12  8  7 67 19 35  9 58  4 29  8 54  2 16  1 58  5 73  6 15  3 82 17 76 13 88  0 71 16 57 18 63 14 13\n 0 34 13 17  9 36  5 96 15 84 14 84 17 29  6 56 11 83  7 84 12 52  2 37 10 41 16 93  1 79 19 93  4 37  8  1 18 45  3 33\n14 19  2 79 13 43 16 43  9 64 19  2  7 14  6 58 18 47 15 23  4 93 17 19  0 57 12 77  5 32  3 61 11 27  8 25 10 52  1 53\n16  3  9  1 17 73  8 81  6 88  4 56 19 58 18 14  7 88  2 68 14 16 15 78 12 48  5 30 10 68 13  5  3 47  0 28 11 71  1 19\n 5 39 19 72  2 37 16 33 10 53  6 95 13  8  4 13 11 23  1 40  3 15 17  6  9 25  8  1 15 22  7 30 18 10 12  7 14 59  0 14\n 4 37  0 98 10 81  2 73  1 58  8 27 18 22  5 39 13 98  7 35 19 98 14 73  6 25 15 73 17 72 16 79 12 54 11 94  9 27  3 30\n 6 49  5 63 10 97 11 87  3 86  7 81  0 15  8 92 15 73  9 76 17 53  4 75  2 93 19 70 16 35 12 13 13 85 18 95  1 39 14 57\n18 34  9 42  0 63 11 73 14  6  4 71  1 76  5 86 19 97 12 16 17 54 10 44  6 49  3 94 13 92  2 24 15 31  7 72  8 35 16 46\n17  4  0 72 16 30  4 47 18 83  1 23  8 88  5 72 15 76  2  4  3 10  7 89 19 75 12 75 11 24 14 63 13 76  9 77 10 36  6 88\n 4 80 17 68 13 65  2 15 15 36  7 34 10 94  1  7  9 99 16 44 11 72  6 12  8 33 18 77 12 24  0 57  3 68 14  1  5  3 19  6\n 6 90 18  3  5 70  2  5  3 72 17 60 19 32  1 91 14 42  9 54 12 18  0 63 15 54 10 83  4 92 13 57 16 96 11 11  8 98  7 47\n10 77 11 33 17 66  3 68  6 99  7 47  5 52 12 88 14  4  1 71  9 20 18 29 15 82  0 11 13 16 19 57  2  4  4 18 16 29  8 68\n","instances/ta48.txt":"30 20\n 6 59  5 77 15 73  8 46 13 99  2  7 10 11 17 75 11 27  0 22  9 33  1 70 19  9  4 17 16 33  3 17 12 40  7 75 18 15 14 80\n 2 16 13 25 11  8  4 41 18 48 12 88 16 38 17 61 19 27 14 78  5 84  3  7  1 16  7 90  9 66  6 41 15  3  0 47  8 33 10 57\n18 87 16 14 14 49 13 90  0 87  7 29  1 47 19 68  3 12 12 68 15 66  6 58  5 67  2 89  8 32  9 89  4  2 10 63 17 70 11 77\n 9 10 10 74  5 56 14 88 18 77  2 79  8 69 11 42 12 12  3 76  4 78  1 74  6  1 19 16 13 34  7 60  0 66 16 71 15 77 17 84\n 8 95  3 24  7 86  9 61  5 67  1  4 17 27  4  8 14 13 15 12 13 43 12 64 16  6 10 50 11 36  0 46 19 71  6 81  2 42 18  4\n 6 82  8 99  9 34  2  4 13 89 14 84  1 77  3 51 15 12 19 72  4 37  0  4 18 18 10 91 12 99 17 16  5  6 16  4 11 77  7 97\n16 37  7 44 12 81  2 72 13 13  6 66  5 52  8 68  3  4 18 14  9 31 15 91 17 71 11 86 14  4  0 55 19  7 10  8  1 89  4 80\n 9 34  5 32  2 55  8 66 10 18 13 76  4 32  1 28 11  7 17 75 19 77  3 24 14 91 16  4  0 72  7 84 15 50 18 45 12 25  6  6\n16  6  4 97 15 68  1 22 11 82  8 74  3 12  6 80  9 79 17 15  0 48 18 91 10 51  2 19 12 74 13 48 19 68  5 43 14 13  7 31\n 3 82 14 19 15 80 17 13  8 35 10 98  6 68 19 12  0  1 18 15  9 58  1 94 16 54  5 74  4  9 13 50 11 82 12 68  7 23  2 76\n 2 79 15 20  4 74 16 43  7 88  8 99  1 46  6 75 18 67 19 81 10 94 14  6  5 60  3 93 17 88 13 39  0 32 11 88 12 80  9 30\n13 74 11 53  5 31  9  1 17 19  6 18  7 38 16 79  0 46  8 74 15 82 10 84 18 27  1 46  2 11 19 37  4 97  3 88 14 25 12 51\n16 59  7 59 13 55 12 20  2 92 19  1 10 31 14 61 15 87 17 10  5 40  1 35  4 15 11 86  0 20 18 43  3 39  9  9  6 38  8 28\n 2 26  0  2 19 81  8 64 18  9 10 47 17 28  3 78 13 64  6 77 14 16 16 69 12 50  7 81  4 31  1 87 11 42 15 23  5 46  9 45\n 5 61  1  7 14 75  9 72  8 83  3  8 11 63 10 27  0 81  7 76 13 57 12  7  2 88 16 62 19  5 17 32  4 25 15 53 18 43  6 75\n17 12 16 48  4 71  0 54 15 49  5 47  3 37 14 72 12 39  2 77 10 94 18 82  8 49  6 42  1 87 19  2 11 10 13 58  9 81  7 41\n10 84  4 36  3 98  1 10 17 22  0 53  5 51  8 95  7 62 12 82 19 48 13 10 15 29  9 68 14 60  2  5 16 41 11 15  6 84 18 45\n 3  9 16 40 15 20  5 39 13 83 11 28 19 94 12 68  8 19  6 25 18 13  7 63 17 69 10 17  0 74  1 95 14 91  2 89  4 16  9 35\n14 69  0 80 11 20  5 99  4 23 12  8 18 43  8 34 10 35 13 83 16 41  7  5  6 86  1 16  3 29  9 92 15 44 17 54  2 21 19 81\n 7 82  4 97 11  5  2 36 15 40 14 58  5  8 19 59 16 78  1 18  9 32 13 34  3 66  8 25 10 10 12 36  0 88  6 50 17 82 18 35\n 8 74  6 42 10 86 15 22  5 39  3 45 18 26  1 63 17 65  9 70 19 33  4 39 16 74 13 75  0  8  7 26 11 25 14 13  2 72 12 98\n10 25 17 46  6 61  8 74  7 40 19 25  2 42  0  5  3  2  5 65  4  1  1 77 14 13 16 42  9 31 18 45 12  7 11 20 15 95 13 75\n 7 50  0 78 14 72  9 53  1 67  6 46 11 95 10 29  2  3 17 31 15  8  5 26 19 60  8 52 18 35 12 57  4 57 13 91 16 91  3 35\n18 26 15 80 16 71 10 64 12 57  6 43  2 72  1 99 17 87  5 81 13 15  4 23  7 73  8  7  9 70 19 98 11 66  3 47  0 10 14 73\n 0 20  6 55 12 87  4 10  8 16  1 59  5 91 17 82 15 53  2 67  7 60  9 34 11 78 13 66 16 98  3 39 10 14 18 65 14 52 19 54\n18  3  9 26  6  8  4 42 11 70 19 17  8 56 10 31  3 29  0 88 13 60 15 81 12 23  2 23 16 43  5 29 17 74  7 29  1 30 14 63\n 5 67 10 66  1 88 14 78 11 79 18 37 16  6  7 35  9 61 13  3 17 67 15 51  2 64 12 69  6 65  3 90  8 95  4 11  0 28 19 50\n 5 54  6 52  8 16  3 39 15 56 19 51  4 49  2 70 16 59 14 66 13 57 10 74  1 86  7 83 18 82  9 65  0 40 11 89 12 53 17  3\n18 68  8 44  1 62 14 25  4 69  6 48 15 68 10 70  7 61 13 51 17 74  5 24 11 54 16 69  3 69 12 33  2 61  0 18  9 36 19 78\n 6  7 13 26  5 79  8 65  2 16 18  3 17 71 19 62 14 42 10 44  7 73 15 79  0  9  9 61 11 63  4 12  1 47  3 67 16 34 12  5\n","instances/ta49.txt":"30 20\n 8 17 10 42  5  3 13 77 11 53 17 65 19 14 18 14  9 77 15 22  3 26 16 53  0 36 12 66  7 26  2 56  1 14 14 41  6 69  4 85\n14 57 18 93  1 85  2 20 13 94  9  3 16 59  6 80 19 40 17 83  7 67  8 55  3 25 10 24  0 74 11 47 15 37  5 98 12  9  4 84\n 9  2  6 62 13 35 10 87  5 37 15 79  2  4  8 79 19 61  1 35  4 39 18 26 11 24  7 17 16  8 12 88  0 39  3 25 14 92 17 48\n14 51  3 30 10 79 16 27 18 25  1 13 17  3  0 23  6 17  8 22  2 45 11 13 19 72  5 52  7 56 15 56 12 84  9 16  4 50 13 64\n 5 72 16 80 11  4  9  7 17 85 10 30 18 75 15 47  0 94 19 11  6 75  4 63 13 58  2 63  1  4 14 33  3 47 12 78  7  8  8 20\n 7 32  9 82  1 45  2 14  4 10  6 60 10 98 18 95 17 61  8 88  5 66  0 79 19 98 15 44 14 48 13 27 11 47 12 31  3 13 16 50\n 0 32 12 53  1 33 14 70 18 59  6 41  8 95 17 65 10 91  2  7 19 19  5 82 16 93 11 56  7 44 13 47  9 32  3 62 15 52  4 15\n16  5 14 44 18 94 11 20  1 35 10 75  5 92  9 30  7 69  2  4 12 99 15 71 17 18  8  1  0 75  4 44 19 35  3 37  6 53 13 96\n10 60 19 54 18 41 15 45  8 79  0 19  2 53  9 91 13  1  3 74  6 16  7 56 12 75 11 95  1 90  4 86  5 58 16 42 14 79 17  8\n 9 78 14 56 10 24 19 60  8 88 12 47  7 33  6 11 18 92  2 72 11 42  0 88 13 30 15 57 16 97  1 25 17 26  4  5  3 62  5 45\n 3 95  4 62 18 53 15 69  6 45  2 48 16 49  7 59  5 37 12 23  9 94 17 19  0 79  8 81  1  9 10 66 14 32 11 17 19 38 13 59\n 2 61  4 73  1 79 15 25 16 75  3  5 17 76  6 26 11 69 12 18  7 21 18 21  8 16 13 39  0 15 14 64 19 98 10 70  9 54  5 32\n16 46 19 94 10 33  9 24 14 31 12 57 18 57  2  8 17 88 15 55  6 69  7 51  5 94 11 43  1 35  0 61  4 14  3 30  8 84 13 79\n12 97  3  7 17 59  4 87  8 57  9 37  2  4 11  2 13 23  5 45 18 73 10 72  6 98  7 79  1 61 15 15 16 80 14 77  0 15 19 76\n 7 53  0 66 18 42 19 59 15  6  2 60  9 30  1 59 10 63  6 61  3 83 11 14 13 78 12 90  8 38  4 88 16 20 17 23  5 81 14 64\n 1 75 19 38 14 15  7 48 17 37  0 92 13 99 11 37 16 79 12 28 10 68  9 20  6  6  3 57 18 79  8 97 15 76  5 11  4  6  2 95\n10 74 17 45  9 93 16  9 18 58  4 16  2 27 11 19  5 19 15 69  8 82  3 25  7 31  0 51 12 85  6 42 14 10 19 85 13 85  1 27\n12 30 11  5  7 54  9  3 19 63 16 47 17 59  6 45 15 63 13 40 10 10  4 16  1 42  8 46  5 66  0 34  2  1  3 15 14 81 18 69\n15 98 17 89 10 45  4 11 14 12  1 49  3 44 18 98  8 15 16 79  6 98  2 48  0 19  7 90 11 20 12 20  5 13 13 78 19 32  9 39\n 0 20 11  4 17 65 10 99 15 56  5 61 12 45  9 93  6 32  3 44  4 62  1 94  7 57 14 58 16 44  2 88  8  1 13 65 18 73 19 64\n13 15  6 71  4 39  8 31 18 32 12 80  0 54  5 38  3 51  9 50  1 58 14 96 11 96 16  9  2 65 15 32  7 19 19 54 17  7 10 10\n 8 53  6 19 14 68 12 99  0 77  9 12 10 81  2 96 18 46 19 56 13 41  5  8 17 93  1 10 11 75  7 75  4 85 15 32  3 80 16 84\n12 96 16  9  8 42  4 52 19 66  9 80 13 45  6 91  3 31  2 40 10 12  5 60 14 99 11 57 15 68  1 44 17 16 18 55  0  6  7 84\n10 98 18 29  8 75 15 40  6 81  7 73  2 70  0 29 11 85  5  3 17 89 12 12 14  1  9 46 13 30  3 28  4 82  1 10 19 18 16 97\n 6 21 16 47  4  2 15 63  0 57 12 25  7 25 10 80  5 70 13 44 17  7  3 30 14 62 18 55  1 68 19 56  8  1  2 25  9  5 11 13\n13 41 19  6  0  7  5 80 14 93  8 12 10 54 17 12 15 38 12 30 18 68  3 36 16 19 11 46  6 71  1 71  7 94  2 66  9 99  4 57\n16 57 18 55 11 46 15 15 17 61  4 64  9 19  1 14 10 49  5 58 13 54  3 54  8 50  0 32 14 40  2 47 19 70 12 97  7 50  6 65\n 7 53  0 32 18  2 16 85  6 17 13 94 17 46  5 83 14 63 11 67  9 46 19 84  3 34 12 22  4 24  8 70 10 63 15 14  1 76  2 67\n17 25 16 83  9 87  1 50  0 60 15 63 11 86  5  5  3 11 18 27 12  8 14 32 13 16  2 49  7 20 19 42 10 59  8 13  4 86  6 38\n 7 64  1 20 16 31 17 14  3 50 13 93  0 72 19 74  6 13 10 42  9 18  8 25 15 83 18 33  5 21  2 92 11 48 14 60 12  4  4 80\n","instances/ta50.txt":"30 20\n 2 96  8 26  6 33  0 19  4 43 15 17 16 26 13 66  5 84 12 56 10 83  7 66 14 74 19 24  1 85  3 47 18 88 17 97  9 41 11 77\n 0 70 10 46 13 90  3 61  2 24  7 63  1 95 16 34  9 47 17 50 18 62 15 10 11 66  8 52 19 49  5  4  4 94 12 38 14 93  6 84\n 0 48 19 60 11 15  9 25 15 21  3 99 13 56 18 32  1 31  5 36  7 74  6 72 10 91  4 29 14 34  8 50 12 21  2 36 16  1 17 30\n 7 50 19 84 10 74 11 35  9 86 14 42  6 31 12 62 16 82 13 66  5 39 15 48  4 98  3 99 17 48  8 77  1 31 18 51  2 44  0 41\n 0 90  6 27 11 30  1 68  3 25 16 94 19 66 12 48 10 47  7 16  5 90  2 23 15  5  4  3 18 10 14 37  9 74  8 28 13 25 17 86\n17 32  8 76 19 29 16 60  0 60 12 21 13  2 14 65  3 22  2 36  1 80 10 61  7 55  9 84 15 99  4 25  6 68 11 80 18 67  5 50\n18 90  1  9  9 28 11 38 17 36  0 19  2  4  6 46 16 84 10 71  4 60 14 23 19 63 12 77 15 72  7  2  3 63  5 24  8 60 13 99\n14 96  9 78 11 79  8 90  2 63 16 80  4 10  1  2 19 67  6 96  0 69  7 13 15 42 18 54 12 76 17 32 13 75  3 52  5 98 10 16\n 3 31 14 80  9 77  0 56 11 85 10 95  4 59 12 46  5  4 16 85  2 42  1 14 13  4  7 40 17 40 19 48  6 90 18 82  8  4 15 87\n13  3  7 53  9 33  0 93  3 62  8 17 11 65  4 23  5 10 14 44 15 49  6  2  2 54 17 25  1 42 10 57 19 23 18 16 16 76 12 12\n 4 68 17 54  2 75  8 29 11 29 19 98 18 17 13  4 12 10  3 71  1 26 10  3  5 51 15 79 14 30  9 58 16 76  6 81  7 63  0 60\n 6 98  0  6 12 66 18 53  1 60 14 93 19 52 16 68 10 81  8 51 17 85 11 74  2 12 13 23  7 43  4 98  5 26 15 51  3 22  9 26\n 2 90  7 35 13 76  0  7 19 67  4 10  9 41 11 41 16 18  3 41  5 35  6 13 14 30 18 28 12 32 15 95 10 92  1 71 17 76  8 78\n14 31  3 64  6 21  7 72  8 78 12 88 15  4  5 74 16 26  4 11  0 41 17 93  1 32 18 74  2 18 19 37 10 28 11 47  9 98 13 65\n18 10 11 37  2 99  3 28  5 84  4 92 15 12 13 72 19 84  6 90  1 35 14 40  0 63 12 29  8 89  9 16 16  4  7 38 10 22 17 84\n10 41 13 38 16 71  8 65 17 86 11 30  7 57  5 71 14 24 15 10  6 78  3 74  0 16 19 25 18  6  2 75  4 68 12 67  1 69  9 56\n 2 46 10 79 19 36  7 13 18  3  4 57  6 79  5 53  0 11 11 45 13 39  1 87  9 25 12 62  8 32 16 13 14 22  3 93 15 90 17 90\n 1 64 13 70 11  9  2 92  3 15 18 32 17  6  9 96 16 51  6 87 12 49 15 75  0 84  4  1  7 10 14 39  8  3  5 89 10 13 19 21\n18 45 10 40 12 14 16 69  1 45 11 98  8 90 19 19  9 40 17  2  5 47  2 70 13 46 14 70  7 93  6 70 15 93  0 33  3  9  4 85\n 7 13  8 85 14 32 11 30 10 70 13 61  6 42 16 41 19 92  2 87 18 36  3 58  5 66  4 70  1 21 12 22 15 41  0 88  9 91 17 94\n11 19  6 51 17  8  8 94  4 72 12 99  1 18  0 39 19 30  9 61 16 19 18 74  2  2  3 77 10 66 15 28 14 23  7 14  5 92 13 90\n16 96 19 92  4 34  5 10  3 68 18 94 15 62  8 83 13 26  0 87 10 29 14 95 11 30  1 49 12 43  2 85  9  1  6 60 17 80  7 48\n 3 42  4 14  2 55  9 97  7 65 16 63  0 74  5 63 13 67 11 48  8 63 14 81 18  8 10  7 17 22  6 43 12 53 15 22  1 93 19 89\n 7 14  2  2 14  8  5 22  6 93  9 59 10 15 15  9  3 10 16 81 18 85 12 62 11 70 17 64  0 93  8 26  4 30 13  6 19 86  1 27\n17 10 11 39 18 56  7 23 12 44  4 93 10 90  3 99  8 80 13 47  2 38  9 15 15 41 19 26  6 48  1 52 16 75 14 65  5  4  0 57\n 1 46  4 78 10 10  7 13  0 32  9 63 14 71  5 66  2 40 18 13  6 50  3 97 19 41 16 95 11 58 12 57 15 63 17 42 13 56  8 31\n10 88 14  2 12 34  6 19 18 86  2 90 13 84  8 40  9 52 19 66 11 76 15 62 17 27  7 28  0  5  5 72 16 54  3 46  1 57  4 66\n14 98 13 44  1 33  5 20 17 74  2 30  4  4 18 88  3 19 12 85 19 81  0 29 10 72  9 79 11 54  8 37  7 95 15 11 16 11  6  2\n 5 48 11 34 16 25 12 26 15 53 10 97  0 26  2 23 14 36  4 17  8 65  1 97 18  5  9 13 17 71  7 32 19 26  6  6  3 47 13 57\n19 22 14 87  4 89  8 41  0 70  1 35 15 95  9 62  3 57 12 52  6 18 13 94 17 60  7 34 11 87 16 22  5 96  2 59 18 81 10 90\n","schedule.py":"\"\"\"Baseline: a Giffler-Thompson active schedule built with the most-work-remaining rule, then\nsimulated annealing over swaps of adjacent critical operations on one machine (van Laarhoven's N1\nneighbourhood restricted to critical arcs, which can never create a cycle). Scores about 0.85 of\nthe records in 10 s per instance. Beat it.\"\"\"\n\nimport math\nimport random\nimport time\n\n\ndef _evaluate(jobs, orders):\n    \"\"\"Earliest-start schedule for the given machine orders.\n\n    Returns (makespan, start, mpred) with start[j][k] the start of operation k of job j and\n    mpred[(j, k)] the operation scheduled just before it on the same machine (if any).\"\"\"\n    n, m = len(jobs), len(jobs[0])\n    op_of = [[0] * m for _ in range(n)]\n    for j, ops in enumerate(jobs):\n        for k, (mc, _) in enumerate(ops):\n            op_of[j][mc] = k\n    mpred, msucc = {}, {}\n    for mc, order in enumerate(orders):\n        prev = None\n        for x in order:\n            node = (x, op_of[x][mc])\n            if prev is not None:\n                mpred[node] = prev\n                msucc[prev] = node\n            prev = node\n    indeg = {(j, k): (k > 0) + ((j, k) in mpred) for j in range(n) for k in range(m)}\n    ready = [node for node, d in indeg.items() if d == 0]\n    start = [[0] * m for _ in range(n)]\n    finish = {}\n    while ready:\n        j, k = ready.pop()\n        s = finish[(j, k - 1)] if k > 0 else 0\n        p = mpred.get((j, k))\n        if p is not None and finish[p] > s:\n            s = finish[p]\n        start[j][k] = s\n        finish[(j, k)] = s + jobs[j][k][1]\n        for nxt in ((j, k + 1) if k + 1 < m else None, msucc.get((j, k))):\n            if nxt is not None:\n                indeg[nxt] -= 1\n                if indeg[nxt] == 0:\n                    ready.append(nxt)\n    if len(finish) != n * m:\n        return None, None, None\n    return max(finish.values()), start, mpred\n\n\ndef _critical_machine_arcs(jobs, start, mpred, cmax, rng):\n    \"\"\"Walk one critical path backwards; collect (machine, job_before, job_after) pairs on it.\"\"\"\n    n, m = len(jobs), len(jobs[0])\n    node = None\n    for j in range(n):\n        if start[j][m - 1] + jobs[j][m - 1][1] == cmax:\n            node = (j, m - 1)\n            if rng.random() < 0.5:\n                break\n    arcs = []\n    while node is not None:\n        j, k = node\n        s = start[j][k]\n        choices = []\n        if k > 0 and start[j][k - 1] + jobs[j][k - 1][1] == s:\n            choices.append((j, k - 1))\n        p = mpred.get(node)\n        if p is not None and start[p[0]][p[1]] + jobs[p[0]][p[1]][1] == s:\n            choices.append(p)\n        if not choices:\n            break\n        nxt = rng.choice(choices)\n        if nxt == p:\n            arcs.append((jobs[j][k][0], p[0], j))\n        node = nxt\n    return arcs\n\n\ndef _giffler_thompson(jobs, rng):\n    \"\"\"Active schedule; ties on the conflict set broken by most work remaining, then randomly.\"\"\"\n    n, m = len(jobs), len(jobs[0])\n    nxt = [0] * n\n    job_ready = [0] * n\n    mach_ready = [0] * m\n    remaining = [sum(d for _, d in ops) for ops in jobs]\n    orders = [[] for _ in range(m)]\n    for _ in range(n * m):\n        best, best_j = None, None\n        for j in range(n):\n            if nxt[j] < m:\n                mc, d = jobs[j][nxt[j]]\n                c = max(job_ready[j], mach_ready[mc]) + d\n                if best is None or c < best:\n                    best, best_j = c, j\n        mc = jobs[best_j][nxt[best_j]][0]\n        conflict = [j for j in range(n) if nxt[j] < m and jobs[j][nxt[j]][0] == mc\n                    and max(job_ready[j], mach_ready[mc]) < best]\n        j = max(conflict, key=lambda x: (remaining[x], rng.random()))\n        mcj, d = jobs[j][nxt[j]]\n        s = max(job_ready[j], mach_ready[mcj])\n        job_ready[j] = mach_ready[mcj] = s + d\n        remaining[j] -= d\n        nxt[j] += 1\n        orders[mcj].append(j)\n    return orders\n\n\ndef schedule(name, jobs, time_budget, seed):\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.9 * time_budget\n    orders = _giffler_thompson(jobs, rng)\n    cmax, start, mpred = _evaluate(jobs, orders)\n    best_orders, best = [list(o) for o in orders], cmax\n    temp0 = temp = 0.01 * cmax\n    it = 0\n    while True:\n        it += 1\n        if it % 32 == 0:\n            now = time.perf_counter()\n            if now >= deadline:\n                break\n            frac = 1 - (deadline - now) / (0.9 * time_budget)\n            temp = temp0 * (0.02 / 1) ** frac    # geometric cooling from 1% to 0.02% of the makespan\n        arcs = _critical_machine_arcs(jobs, start, mpred, cmax, rng)\n        if not arcs:\n            break\n        mc, a, b = rng.choice(arcs)\n        order = orders[mc]\n        i = order.index(a)\n        order[i], order[i + 1] = order[i + 1], order[i]\n        new_cmax, new_start, new_mpred = _evaluate(jobs, orders)\n        delta = new_cmax - cmax\n        if delta <= 0 or rng.random() < math.exp(-delta / temp):\n            cmax, start, mpred = new_cmax, new_start, new_mpred\n            if cmax < best:\n                best, best_orders = cmax, [list(o) for o in orders]\n        else:\n            order[i], order[i + 1] = order[i + 1], order[i]\n    return best_orders\n"}}