{"problem":{"name":"A. Random Fightings","description":{"content":"Nodar is a very famous gangster in Euroland, he has hundreds of friends but only N of them are gangsters like him, after his many successful heists in Linearland, Squareland and Cubeland, he decided t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10088A"},"statements":[{"statement_type":"Markdown","content":"Nodar is a very famous gangster in Euroland, he has hundreds of friends but only N of them are gangsters like him, after his many successful heists in Linearland, Squareland and Cubeland, he decided to form a new gang called “The Nodar ACMers”. \n\nHe invited his N gangster friends and formed the gang very quickly, but all of his N friends are professional gangsters, and they’re very greedy. \n\nSince gang leader will get 60% of the gang’s net income, all of them want that position. \n\nAlex (Nodar's best friend) has 173 IQ points so he foresaw the bloodshed that will happen if each new leader is assassinated, so he devised a master plan to save his gang from all that terror thus having the freedom to terrorize the citizens of Euroland, and he said “Chess determines the skills of the true leader”, and then Nodar gave each of his friends a unique number from 1 to n, Nodar will host n - 1 matches, in each match the following will happen: \n\nA pair of the remaining gangsters will be chosen at random ( the likelihood of choosing all pairs is uniform) The loser will be kicked out of the competition. \n\nThe remaining gangster will become the unquestioned boss of the gang, and will probably arrange Nodar’s “Accidental” death if he didn’t like him, Thus Nodar started to collect more information about his gang. \n\nHe found out that the probability of gangster i beating gangster j is Aij, it is guaranteed that Aij = 1 - Aji (Gangsters don’t believe in draws). \n\nAs Nodar’s personal programming assistant he asked you to write a program that would determine for each gangster, his probability of becoming the boss.\n\nThe first line of the input contans one integer T , the number of testcases. \n\nThe first line of each testcase contains an integer N (1 ≤  N ≤  20) — the number of gang members. \n\nThen there follows N lines with N real numbers each — matrix A. \n\nAij (0  ≤  Aij ≤  1) — the probability that gangster with index i beats gangster with index j. It's guaranteed that the main diagonal contains zeros only , and for other elements the following is true: Aij  =  1  -  Aji.\n\nFor each test case print a single line containing \"Case t:\" (without the quotes) where t is the test case number (starting from 1) followed by a single space, followed by n space-separated real numbers with exactly 6 decimal places. \n\nNumber with index i should be equal to the probability that gangster with number i will win to be the leader of gang.\n\nYou should print exactly 6 decimal places (even if zeroes).\n\n## Input\n\nThe first line of the input contans one integer T , the number of testcases. The first line of each testcase contains an integer N (1 ≤  N ≤  20) — the number of gang members. Then there follows N lines with N real numbers each — matrix A. Aij (0  ≤  Aij ≤  1) — the probability that gangster with index i beats gangster with index j. It's guaranteed that the main diagonal contains zeros only , and for other elements the following is true: Aij  =  1  -  Aji.\n\n## Output\n\nFor each test case print a single line containing \"Case t:\" (without the quotes) where t is the test case number (starting from 1) followed by a single space, followed by n space-separated real numbers with exactly 6 decimal places. Number with index i should be equal to the probability that gangster with number i will win to be the leader of gang.\n\n[samples]\n\n## Note\n\nYou should print exactly 6 decimal places (even if zeroes).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the size of the array.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a multiset of non-negative integers.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 10^3 $  \n   - $ 0 \\le a_{k,i} \\le 10^6 $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n\n**Objective**  \nFor each test case $ k $, find the maximum value of the beauty over all permutations $ P = (p_1, p_2, \\dots, p_{n_k}) $ of $ A_k $, where the beauty is defined as:  \n$$\n\\text{Beauty}(P) = \\sum_{i=1}^{n_k-1} |p_i - p_{i+1}|\n$$  \nThat is, maximize the sum of absolute differences between consecutive elements in any permutation of $ A_k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10088A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}