{"problem":{"name":"G. Дворовый футбол в Самаре","description":{"content":"Каждое воскресенье Андрей вместе с друзьями играет в футбол. На каждую игру приходит одно и то же (чётное) количество человек. Когда друзья собираются, первым делом они начинают обсуждать, как им разд","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10085G"},"statements":[{"statement_type":"Markdown","content":"Каждое воскресенье Андрей вместе с друзьями играет в футбол. На каждую игру приходит одно и то же (чётное) количество человек. Когда друзья собираются, первым делом они начинают обсуждать, как им разделиться на две команды. \n\nОбычно дискуссии по поводу того, как именно разделиться, занимают очень много времени. Однажды друзьям надоело дискутировать, и они придумали следующий способ. Каждый раз случайным образом выбираются два капитана, после чего капитаны набирают игроков в свои команды. \n\nЧтобы не было новых споров и обид, капитаны по очереди выбирают по одному игроку среди тех, кто ещё не включён в какую-либо команду. Каждый капитан стремится набрать как можно более сильную команду и потому выбирает самого сильного среди ещё не выбранных игроков. Сила игрока — это целое число от 1 до 100 (как в FIFA). Сила команды вычисляется как суммарная сила всех игроков в этой команде, включая капитана. \n\nАндрею стало интересно, какой может быть минимальная разница в силе между командами. Но он очень занят подготовкой контеста по программированию, поэтому просит вас найти эту величину. \n\nНа всякий случай ещё раз напомним, что в роли капитанов могут оказаться два любых игрока, не обязательно самые сильные. \n\nВ первой строке записано единственное целое число n (2 ≤ n ≤ 400) — количество человек, пришедших на игру. Гарантируется, что n — чётное.\n\nВо второй строке записаны целые числа a1, a2, ..., an, где ai (1 ≤ ai ≤ 100) — сила i-го игрока.\n\nВыведите единственное целое число — минимально возможную разницу в силе команд.\n\n## Входные Данные\n\nВ первой строке записано единственное целое число n (2 ≤ n ≤ 400) — количество человек, пришедших на игру. Гарантируется, что n — чётное.Во второй строке записаны целые числа a1, a2, ..., an, где ai (1 ≤ ai ≤ 100) — сила i-го игрока.\n\n## Выходные Данные\n\nВыведите единственное целое число — минимально возможную разницу в силе команд.\n\n## Примеры\n\nВходные данные61 2 3 4 5 6Выходные данные1Входные данные890 93 86 65 78 81 71 86Выходные данные0\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of players, with $ n $ even and $ 2 \\leq n \\leq 400 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers representing player strengths, where $ 1 \\leq a_i \\leq 100 $.\n\n**Constraints**  \n1. $ n $ is even.  \n2. $ a_i \\in \\mathbb{Z} $, $ 1 \\leq a_i \\leq 100 $ for all $ i \\in \\{1, \\dots, n\\} $.\n\n**Objective**  \nChoose two distinct players as captains. The remaining $ n-2 $ players are distributed between the two teams in order of descending strength: at each step, the current captain selects the strongest available player.  \nMinimize the absolute difference between the total strengths of the two teams over all possible choices of two captains and the resulting greedy selection process.\n\nFormally, for every unordered pair $ \\{i, j\\} $ with $ i \\ne j $, let $ T_1 $ and $ T_2 $ be the teams formed by:  \n- Sorting $ A \\setminus \\{a_i, a_j\\} $ in descending order: $ b_1 \\geq b_2 \\geq \\dots \\geq b_{n-2} $,  \n- Assigning $ b_1 $ to the team of the captain with higher strength (or arbitrarily if equal), then alternating assignments.  \n- Adding the two captains to their respective teams.  \n\nCompute:  \n$$\n\\min_{\\substack{i,j \\in \\{1,\\dots,n\\} \\\\ i \\ne j}} \\left| \\text{sum}(T_1) - \\text{sum}(T_2) \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10085G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}