A. Santa Claus and Candies

Codeforces

IDCF753A

Time1000ms

Memory256MB

Difficulty—

dpgreedymath

English · Original

Chinese · Translation

Formal · Original

Santa Claus has _n_ candies, he dreams to give them as gifts to children. What is the maximal number of children for whose he can give candies if Santa Claus want each kid should get _distinct_ positive integer number of candies. Santa Class wants to give all _n_ candies he has. ## Input The only line contains positive integer number _n_ (1 ≤ _n_ ≤ 1000) — number of candies Santa Claus has. ## Output Print to the first line integer number _k_ — maximal number of kids which can get candies. Print to the second line _k_ _distinct_ integer numbers: number of candies for each of _k_ kid. The sum of _k_ printed numbers should be exactly _n_. If there are many solutions, print any of them. [samples]

[{"iden":"statement","content":"圣诞老人有 #cf_span[n] 颗糖果，他梦想将这些糖果作为礼物送给孩子们。\n\n如果圣诞老人希望每个孩子都得到 _不同_ 的正整数数量的糖果，并且他想把所有 #cf_span[n] 颗糖果都分完，那么最多能送给多少个孩子？\n\n输入仅一行，包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）——圣诞老人拥有的糖果数量。\n\n请在第一行输出一个整数 #cf_span[k] —— 能够获得糖果的最大孩子数量。\n\n请在第二行输出 #cf_span[k] 个 _不同_ 的整数：每个孩子获得的糖果数量。这 #cf_span[k] 个数的总和必须恰好等于 #cf_span[n]。\n\n如果有多种解决方案，输出任意一种即可。\n\n"},{"iden":"input","content":"输入仅一行，包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）——圣诞老人拥有的糖果数量。"},{"iden":"output","content":"请在第一行输出一个整数 #cf_span[k] —— 能够获得糖果的最大孩子数量。请在第二行输出 #cf_span[k] 个 _不同_ 的整数：每个孩子获得的糖果数量。这 #cf_span[k] 个数的总和必须恰好等于 #cf_span[n]。如果有多种解决方案，输出任意一种即可。"},{"iden":"examples","content":"输入\n5\n输出\n2\n2 3\n\n输入\n9\n输出\n3\n3 5 1\n\n输入\n2\n输出\n1\n2 "}] ```json [{"iden":"statement","content":"圣诞老人有 #cf_span[n] 颗糖果，他梦想将这些糖果作为礼物送给孩子们。\n\n如果圣诞老人希望每个孩子都得到 _不同_ 的正整数数量的糖果，并且他想把所有 #cf_span[n] 颗糖果都分完，那么最多能送给多少个孩子？\n\n输入仅一行，包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）——圣诞老人拥有的糖果数量。\n\n请在第一行输出一个整数 #cf_span[k] —— 能够获得糖果的最大孩子数量。\n\n请在第二行输出 #cf_span[k] 个 _不同_ 的整数：每个孩子获得的糖果数量。这 #cf_span[k] 个数的总和必须恰好等于 #cf_span[n]。\n\n如果有多种解决方案，输出任意一种即可。\n\n"},{"iden":"input","content":"输入仅一行，包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）——圣诞老人拥有的糖果数量。"},{"iden":"output","content":"请在第一行输出一个整数 #cf_span[k] —— 能够获得糖果的最大孩子数量。请在第二行输出 #cf_span[k] 个 _不同_ 的整数：每个孩子获得的糖果数量。这 #cf_span[k] 个数的总和必须恰好等于 #cf_span[n]。如果有多种解决方案，输出任意一种即可。"},{"iden":"examples","content":"输入\n5\n输出\n2\n2 3\n\n输入\n9\n输出\n3\n3 5 1\n\n输入\n2\n输出\n1\n2 "}]} ```

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the total number of candies, with $ 1 \leq n \leq 1000 $. **Objective** Find the maximum integer $ k \in \mathbb{Z}^+ $ and a set of $ k $ distinct positive integers $ \{a_1, a_2, \dots, a_k\} $ such that: $$ \sum_{i=1}^k a_i = n $$ and $ k $ is maximized. **Constraints** - $ a_i \in \mathbb{Z}^+ $ for all $ i \in \{1, \dots, k\} $ - $ a_i \ne a_j $ for all $ i \ne j $ **Optimal Strategy** To maximize $ k $, choose the smallest $ k $ distinct positive integers: $ 1, 2, 3, \dots, k $, whose sum is $ \frac{k(k+1)}{2} $. Find the largest $ k $ such that $ \frac{k(k+1)}{2} \leq n $. Let $ S = \sum_{i=1}^k i = \frac{k(k+1)}{2} $. If $ S < n $, distribute the excess $ n - S $ by adding it to the largest element: $ a_k \leftarrow a_k + (n - S) $. This preserves distinctness and maximizes $ k $.

Samples

Input #1

Output #1

2
2 3

Input #2

Output #2

3
3 5 1

Input #3

Output #3

1
2

API Response (JSON)

{
  "problem": {
    "name": "A. Santa Claus and Candies",
    "description": {
      "content": "Santa Claus has _n_ candies, he dreams to give them as gifts to children. What is the maximal number of children for whose he can give candies if Santa Claus want each kid should get _distinct_ posit",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF753A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Santa Claus has _n_ candies, he dreams to give them as gifts to children.\n\nWhat is the maximal number of children for whose he can give candies if Santa Claus want each kid should get _distinct_ posit...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"圣诞老人有 #cf_span[n] 颗糖果，他梦想将这些糖果作为礼物送给孩子们。\\n\\n如果圣诞老人希望每个孩子都得到 _不同_ 的正整数数量的糖果，并且他想把所有 #cf_span[n] 颗糖果都分完，那么最多能送给多少个孩子？\\n\\n输入仅一行，包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the total number of candies, with $ 1 \\leq n \\leq 1000 $.  \n\n**Objective**  \nFind the maximum integer $ k \\in \\mathbb{Z}^+ $ and a set of $ k $ distinct...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments