A. Random Fightings

Codeforces

IDCF10088A

Time4000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

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”. He 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. Since gang leader will get 60% of the gang’s net income, all of them want that position. Alex (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: A 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. The 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. He 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). As Nodar’s personal programming assistant he asked you to write a program that would determine for each gangster, his probability of becoming the boss. The 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. For 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. You should print exactly 6 decimal places (even if zeroes). ## Input The 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. ## Output For 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. [samples] ## Note You should print exactly 6 decimal places (even if zeroes).

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ denote the size of the array. - Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ be a multiset of non-negative integers. **Constraints** 1. $ 1 \le T \le 10 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le n_k \le 10^3 $ - $ 0 \le a_{k,i} \le 10^6 $ for all $ i \in \{1, \dots, n_k\} $ **Objective** For 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: $$ \text{Beauty}(P) = \sum_{i=1}^{n_k-1} |p_i - p_{i+1}| $$ That is, maximize the sum of absolute differences between consecutive elements in any permutation of $ A_k $.

API Response (JSON)

{
  "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 t...",
      "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_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments