{"problem":{"name":"D. Tournament Construction","description":{"content":"Ivan is reading a book about tournaments. He knows that a tournament is an oriented graph with exactly one oriented edge between each pair of vertices. The score of a vertex is the number of edges goi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF850D"},"statements":[{"statement_type":"Markdown","content":"Ivan is reading a book about tournaments. He knows that a tournament is an oriented graph with exactly one oriented edge between each pair of vertices. The score of a vertex is the number of edges going outside this vertex.\n\nYesterday Ivan learned Landau's criterion: there is tournament with scores _d_1 ≤ _d_2 ≤ ... ≤ _d__n_ if and only if for all 1 ≤ _k_ < _n_ and .\n\nNow, Ivan wanna solve following problem: given a **set** of numbers _S_ = {_a_1, _a_2, ..., _a__m_}, is there a tournament with given set of scores? I.e. is there tournament with sequence of scores _d_1, _d_2, ..., _d__n_ such that if we remove duplicates in scores, we obtain the required set {_a_1, _a_2, ..., _a__m_}?\n\nFind a tournament with **minimum** possible number of vertices.\n\n## Input\n\nThe first line contains a single integer _m_ (1 ≤ _m_ ≤ 31).\n\nThe next line contains _m_ distinct integers _a_1, _a_2, ..., _a__m_ (0 ≤ _a__i_ ≤ 30) — elements of the set _S_. It is guaranteed that all elements of the set are distinct.\n\n## Output\n\nIf there are no such tournaments, print string \"_\\=(_\" (without quotes).\n\nOtherwise, print an integer _n_ — the number of vertices in the tournament.\n\nThen print _n_ lines with _n_ characters — matrix of the tournament. The _j_\\-th element in the _i_\\-th row should be 1 if the edge between the _i_\\-th and the _j_\\-th vertices is oriented towards the _j_\\-th vertex, and 0 otherwise. The main diagonal should contain only zeros.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ivan 正在阅读一本关于锦标赛的书。他了解到，锦标赛是一个有向图，其中每对顶点之间恰好有一条有向边。一个顶点的得分是从此顶点出发的边的数量。\n\n昨天，Ivan 学习了 Landau 准则：存在一个锦标赛，其得分为 #cf_span[d1 ≤ d2 ≤ ... ≤ dn]，当且仅当对所有 #cf_span[1 ≤ k < n] 有 。\n\n现在，Ivan 想解决以下问题：给定一个 *集合* #cf_span[S = {a1, a2, ..., am}]，是否存在一个锦标赛，其得分集合恰好为该集合？即，是否存在一个得分序列 #cf_span[d1, d2, ..., dn]，使得在去除重复项后，得到的集合恰好为 #cf_span[{a1, a2, ..., am}]？\n\n请找出具有 *最小* 顶点数的锦标赛。\n\n第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 31])。\n\n第二行包含 #cf_span[m] 个互不相同的整数 #cf_span[a1, a2, ..., am] (#cf_span[0 ≤ ai ≤ 30]) —— 集合 #cf_span[S] 的元素。保证集合中所有元素互不相同。\n\n如果不存在这样的锦标赛，请输出字符串 \"_=(_\"（不含引号）。\n\n否则，输出一个整数 #cf_span[n] —— 锦标赛的顶点数。\n\n然后输出 #cf_span[n] 行，每行包含 #cf_span[n] 个字符 —— 锦标赛的邻接矩阵。第 #cf_span[i] 行的第 #cf_span[j] 个字符应为 #cf_span[1]，表示从第 #cf_span[i] 个顶点到第 #cf_span[j] 个顶点的边方向朝向第 #cf_span[j] 个顶点；否则为 #cf_span[0]。主对角线上的元素全为 0。\n\n## Input\n\n第一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 31])。第二行包含 #cf_span[m] 个互不相同的整数 #cf_span[a1, a2, ..., am] (#cf_span[0 ≤ ai ≤ 30]) —— 集合 #cf_span[S] 的元素。保证集合中所有元素互不相同。\n\n## Output\n\n如果不存在这样的锦标赛，请输出字符串 \"_=(_\"（不含引号）。否则，输出一个整数 #cf_span[n] —— 锦标赛的顶点数。然后输出 #cf_span[n] 行，每行包含 #cf_span[n] 个字符 —— 锦标赛的邻接矩阵。第 #cf_span[i] 行的第 #cf_span[j] 个字符应为 #cf_span[1]，表示从第 #cf_span[i] 个顶点到第 #cf_span[j] 个顶点的边方向朝向第 #cf_span[j] 个顶点；否则为 #cf_span[0]。主对角线上的元素全为 0。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Given a set $ S = \\{a_1, a_2, \\dots, a_m\\} $ of distinct non-negative integers, find the minimum integer $ n $ and a tournament graph on $ n $ vertices with score sequence $ (d_1, d_2, \\dots, d_n) $ such that the set of distinct scores is exactly $ S $, i.e., $ \\{d_1, d_2, \\dots, d_n\\} = S $, and if no such tournament exists, output \"_=(_\".\n\nA tournament is a complete oriented graph: for every pair $ i \\ne j $, exactly one of $ (i,j) $ or $ (j,i) $ is an edge. The score $ d_i $ of vertex $ i $ is its out-degree.\n\nLandau’s criterion: A non-decreasing sequence $ (d_1 \\le d_2 \\le \\dots \\le d_n) $ is a score sequence of a tournament if and only if:\n\n1. $ \\sum_{i=1}^k d_i \\ge \\binom{k}{2} $ for all $ 1 \\le k < n $,\n2. $ \\sum_{i=1}^n d_i = \\binom{n}{2} $.\n\n---\n\n**Formal Problem Statement:**\n\nLet $ S = \\{a_1, a_2, \\dots, a_m\\} \\subset \\mathbb{Z}_{\\ge 0} $, with $ m \\le 31 $, $ a_i \\le 30 $, all distinct.\n\nFind the minimal $ n \\in \\mathbb{Z}^+ $ such that there exists a sequence $ (d_1, d_2, \\dots, d_n) \\in \\mathbb{Z}_{\\ge 0}^n $ satisfying:\n\n- $ \\{d_1, d_2, \\dots, d_n\\} = S $ (as sets),\n- $ \\sum_{i=1}^n d_i = \\binom{n}{2} $,\n- $ \\sum_{i=1}^k d_{(i)} \\ge \\binom{k}{2} $ for all $ 1 \\le k < n $, where $ d_{(1)} \\le d_{(2)} \\le \\dots \\le d_{(n)} $ is the sorted sequence.\n\nIf no such $ n $ exists, output \"_=(_\".\n\nOtherwise, output:\n\n- $ n $\n- An $ n \\times n $ adjacency matrix $ A = (a_{ij}) $, where:\n  - $ a_{ii} = 0 $,\n  - $ a_{ij} \\in \\{0,1\\} $ for $ i \\ne j $,\n  - $ a_{ij} + a_{ji} = 1 $ for all $ i \\ne j $,\n  - $ \\sum_{j=1}^n a_{ij} = d_i $ for all $ i $.\n\n--- \n\n**Note:** The problem reduces to: over all $ n \\ge \\max(S) $, check whether there exists a multiset of $ n $ scores, using only values from $ S $, that satisfies Landau’s conditions. Find the minimal such $ n $, and construct the corresponding tournament.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF850D","tags":["constructive algorithms","dp","graphs","greedy","math"],"sample_group":[["2\n1 2","4\n0011\n1001\n0100\n0010"],["2\n0 3","6\n000111\n100011\n110001\n011001\n001101\n000000"]],"created_at":"2026-03-03 11:00:39"}}