D. Balloons

Codeforces

IDCF10185D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

In many contests, balloons are used to indicate to contestants the general state of the contest. Each time a team solves a problem, a balloon of a specific color is sent to the team and attached on or near their machine. As the contest progresses, the contest floor gradually fills up with a multi-colored display showing how various teams are doing in the contest. Consider a contest of n problems in which each problem is attached to a specific balloon color. You will be able to see the balloon color of a problem in the contest floor if at least one team solved it during the contest. You are given the number of accepted solutions on each problem. Your task is to count how many different colors you will be able to see. Can you? The first line contains an integer T (1 ≤ T ≤ 1000), in which T is the number of test cases. The first line of each test case contains an integer n (1 ≤ n ≤ 20), in which n is the number of problems in the contest. Then a line follows containing n integers p1, p2, ..., pk (0 ≤ pi ≤ 100), in which pi is the number of accepted solutions on the ith problem. For each test case, print a single line containing the number different colors will you be able to see in the contest's floor. ## Input The first line contains an integer T (1 ≤ T ≤ 1000), in which T is the number of test cases.The first line of each test case contains an integer n (1 ≤ n ≤ 20), in which n is the number of problems in the contest. Then a line follows containing n integers p1, p2, ..., pk (0 ≤ pi ≤ 100), in which pi is the number of accepted solutions on the ith problem. ## Output For each test case, print a single line containing the number different colors will you be able to see in the contest's floor. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of queries. For each query $ i \in \{1, \dots, n\} $, let $ s_i \in \mathbb{Z}_{\geq 0} $ denote the amount of Pokédollars Ash has. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 0 \leq s_i \leq 10^{18} $ for all $ i \in \{1, \dots, n\} $ **Objective** For each $ s_i $, find the maximum integer $ k \in \mathbb{Z}_{\geq 0} $ such that: $$ \sum_{j=1}^{k} j \leq s_i $$ That is, $$ \frac{k(k+1)}{2} \leq s_i $$ Solve for the largest such $ k $.

API Response (JSON)

{
  "problem": {
    "name": "D. Balloons",
    "description": {
      "content": "In many contests, balloons are used to indicate to contestants the general state of the contest. Each time a team solves a problem, a balloon of a specific color is sent to the team and attached on or",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10185D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In many contests, balloons are used to indicate to contestants the general state of the contest. Each time a team solves a problem, a balloon of a specific color is sent to the team and attached on or...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of queries.  \nFor each query $ i \\in \\{1, \\dots, n\\} $, let $ s_i \\in \\mathbb{Z}_{\\geq 0} $ denote the amount of Pokédollars Ash has.\n\n**Constr...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments