G. World Mug (B)

Codeforces

IDCF10179G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The organizers of the tournament wish to ensure a great amount of fun for the fans, for that, they have decided to rearrange the teams such that more goals in the tournament are scored. Can you help out by calculating the maximum number of goals that could be scored if the teams were rearranged optimally? The first line of input contains one integer n (2 ≤ n ≤ 218), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...). The second line contains n *distinct* integers, the ith integer is si (1 ≤ si ≤ 109), the strength of the ith team. On a single line, print the maximum number of goals that could be scored in the tournament if the teams were rearranged to maximize that number. ## Input The first line of input contains one integer n (2 ≤ n ≤ 218), the number of teams participating in the tournament. It is guaranteed that the number of teams is a power of two (i.e., 2, 4, 8, 16, ...).The second line contains n *distinct* integers, the ith integer is si (1 ≤ si ≤ 109), the strength of the ith team. ## Output On a single line, print the maximum number of goals that could be scored in the tournament if the teams were rearranged to maximize that number. [samples]

**Definitions** Let $ n = 2^k $ for some $ k \in \mathbb{Z}^+ $, the number of teams. Let $ S = \{s_1, s_2, \dots, s_n\} $ be a set of distinct positive integers representing team strengths. **Constraints** 1. $ 2 \leq n \leq 218 $ and $ n $ is a power of two. 2. $ 1 \leq s_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $. 3. All $ s_i $ are distinct. **Objective** Maximize the total number of goals scored in a single-elimination tournament, where in each match between two teams, the number of goals scored equals the **maximum** of the two teams' strengths. Compute the maximum possible total goals over all possible initial bracket arrangements.

API Response (JSON)

{
  "problem": {
    "name": "G. World Mug (B)",
    "description": {
      "content": "The organizers of the tournament wish to ensure a great amount of fun for the fans, for that, they have decided to rearrange the teams such that more goals in the tournament are scored. Can you help ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10179G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The organizers of the tournament wish to ensure a great amount of fun for the fans, for that, they have decided to rearrange the teams such that more goals in the tournament are scored.\n\nCan you help ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n = 2^k $ for some $ k \\in \\mathbb{Z}^+ $, the number of teams.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a set of distinct positive integers representing team strengths.\n\n**Co...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments