B. Maximum Tree

Codeforces

IDCF10146B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Ivan is a new professor of the University of Nice Algebra Lovers (UNAL), he is going to give a data structures course, that's why he is preparing his slides and wants to draw a beautiful rooted tree. As he loves math, he has a very special array of numbers A and he wants to use each element of the array as the number of children for some level in the tree. For example, if A = [2, 1, 3] two of the possible trees he could draw are the following: Ivan wants to draw a rooted tree that has the maximum number of nodes. As he is busy with LaTeX he wants you to write a program that computes such number. The first line consists of an integer n (1 ≤ n ≤ 32), the next line contains n numbers separated by a single space, the elements of A (1 ≤ Ai ≤ 10). Print one number, the maximum number of nodes Ivan can draw. It is guaranteed that the answer fits on a 63-bits integer. The number of levels of the tree (except for the root) is the same as the number of elements in the array ## Input The first line consists of an integer n (1 ≤ n ≤ 32), the next line contains n numbers separated by a single space, the elements of A (1 ≤ Ai ≤ 10). ## Output Print one number, the maximum number of nodes Ivan can draw. It is guaranteed that the answer fits on a 63-bits integer. [samples] ## Note The number of levels of the tree (except for the root) is the same as the number of elements in the array

**Definitions** Let $ n \in \mathbb{Z} $ be the number of levels (excluding the root). Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ denotes the number of children per node at level $ i $. **Constraints** 1. $ 1 \leq n \leq 32 $ 2. $ 1 \leq a_i \leq 10 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute the maximum number of nodes in a rooted tree where: - The root is at level 0. - Each node at level $ i-1 $ has exactly $ a_i $ children (for $ i = 1, \dots, n $). The total number of nodes is: $$ 1 + \sum_{i=1}^{n} \prod_{j=1}^{i} a_j $$

API Response (JSON)

{
  "problem": {
    "name": "B. Maximum Tree",
    "description": {
      "content": "Ivan is a new professor of the University of Nice Algebra Lovers (UNAL), he is going to give a data structures course, that's why he is preparing his slides and wants to draw a beautiful rooted tree. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10146B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ivan is a new professor of the University of Nice Algebra Lovers (UNAL), he is going to give a data structures course, that's why he is preparing his slides and wants to draw a beautiful rooted tree. ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of levels (excluding the root).  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ denotes the number of ch...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments