A. Splits

Codeforces

IDCF964A

Time1000ms

Memory256MB

Difficulty—

math

English · Original

Chinese · Translation

Formal · Original

Let's define a split of $n$ as a nonincreasing sequence of positive integers, the sum of which is $n$. For example, the following sequences are splits of $8$: $[4, 4]$, $[3, 3, 2]$, $[2, 2, 1, 1, 1, 1]$, $[5, 2, 1]$. The following sequences aren't splits of $8$: $[1, 7]$, $[5, 4]$, $[11, -3]$, $[1, 1, 4, 1, 1]$. The weight of a split is the number of elements in the split that are equal to the first element. For example, the weight of the split $[1, 1, 1, 1, 1]$ is $5$, the weight of the split $[5, 5, 3, 3, 3]$ is $2$ and the weight of the split $[9]$ equals $1$. For a given $n$, find out the number of different weights of its splits. ## Input The first line contains one integer $n$ ($1 \leq n \leq 10^9$). ## Output Output one integer — the answer to the problem. [samples] ## Note In the first sample, there are following possible weights of splits of $7$: Weight 1: \[$\textbf 7$\] Weight 2: \[$\textbf 3$, $\textbf 3$, 1\] Weight 3: \[$\textbf 2$, $\textbf 2$, $\textbf 2$, 1\] Weight 7: \[$\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$, $\textbf 1$\]

定义 $n$ 的一个划分是一个非递增的正整数序列，其元素之和为 $n$。例如，以下序列都是 $8$ 的划分：$[ 4, 4 ]$，$[ 3, 3, 2 ]$，$[ 2, 2, 1, 1, 1, 1 ]$，$[ 5, 2, 1 ]$。以下序列不是 $8$ 的划分：$[ 1, 7 ]$，$[ 5, 4 ]$，$[ 11, -3 ]$，$[ 1, 1, 4, 1, 1 ]$。一个划分的权重是等于该序列第一个元素的元素个数。例如，划分 $[ 1, 1, 1, 1, 1 ]$ 的权重是 $5$，划分 $[ 5, 5, 3, 3, 3 ]$ 的权重是 $2$，划分 $[ 9 ]$ 的权重是 $1$。对于给定的 $n$，求其所有划分中不同权重的个数。第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^9$）。输出一个整数——问题的答案。在第一个样例中，$7$ 的划分可能具有以下权重：权重 1：[$textbf(7)$] 权重 2：[$textbf(3)$, $textbf(3)$, 1] 权重 3：[$textbf(2)$, $textbf(2)$, $textbf(2)$, 1] 权重 7：[$textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$] ## Input 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^9$）。 ## Output 输出一个整数——问题的答案。 [samples] ## Note 在第一个样例中，$7$ 的划分可能具有以下权重：权重 1：[$textbf(7)$] 权重 2：[$textbf(3)$, $textbf(3)$, 1] 权重 3：[$textbf(2)$, $textbf(2)$, $textbf(2)$, 1] 权重 7：[$textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$, $textbf(1)$]

**Definitions** Let $ n \in \mathbb{Z}^+ $. A *split* of $ n $ is a nonincreasing sequence of positive integers $ (a_1, a_2, \dots, a_k) $ such that $ \sum_{i=1}^k a_i = n $. The *weight* of a split is defined as the number of times the first element $ a_1 $ appears consecutively at the start of the sequence, i.e., $$ \text{weight} = \max \left\{ j \in \mathbb{Z}^+ \mid a_1 = a_2 = \cdots = a_j \right\}. $$ **Objective** Find the number of distinct weights among all possible splits of $ n $. **Constraints** $ 1 \le n \le 10^9 $

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Splits",
    "description": {
      "content": "Let's define a split of $n$ as a nonincreasing sequence of positive integers, the sum of which is $n$. For example, the following sequences are splits of $8$: $[4, 4]$, $[3, 3, 2]$, $[2, 2, 1, 1, 1, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF964A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let's define a split of $n$ as a nonincreasing sequence of positive integers, the sum of which is $n$.\n\nFor example, the following sequences are splits of $8$: $[4, 4]$, $[3, 3, 2]$, $[2, 2, 1, 1, 1, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "定义 $n$ 的一个划分是一个非递增的正整数序列，其元素之和为 $n$。\n\n例如，以下序列都是 $8$ 的划分：$[ 4, 4 ]$，$[ 3, 3, 2 ]$，$[ 2, 2, 1, 1, 1, 1 ]$，$[ 5, 2, 1 ]$。\n\n以下序列不是 $8$ 的划分：$[ 1, 7 ]$，$[ 5, 4 ]$，$[ 11, -3 ]$，$[ 1, 1, 4, 1, 1 ]$。\n\n一个划分的权重是...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $. A *split* of $ n $ is a nonincreasing sequence of positive integers $ (a_1, a_2, \\dots, a_k) $ such that $ \\sum_{i=1}^k a_i = n $.  \n\nThe *weight* of a sp...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments