C. Dividing the numbers

Codeforces

IDCF899C

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgraphsmath

English · Original

Chinese · Translation

Formal · Original

Petya has _n_ integers: 1, 2, 3, ..., _n_. He wants to split these integers in **two non-empty** groups in such a way that the absolute difference of sums of integers in each group is as small as possible. Help Petya to split the integers. Each of _n_ integers should be exactly in one group. ## Input The first line contains a single integer _n_ (2 ≤ _n_ ≤ 60 000) — the number of integers Petya has. ## Output Print the smallest possible absolute difference in the first line. In the second line print the size of the first group, followed by the integers in that group. You can print these integers in arbitrary order. If there are multiple answers, print any of them. [samples] ## Note In the first example you have to put integers 1 and 4 in the first group, and 2 and 3 in the second. This way the sum in each group is 5, and the absolute difference is 0. In the second example there are only two integers, and since both groups should be non-empty, you have to put one integer in the first group and one in the second. This way the absolute difference of sums of integers in each group is 1.

Petya 有 #cf_span[n] 个整数：#cf_span[1, 2, 3, ..., n]。他希望将这些整数划分为 *两个非空* 组，使得每组整数之和的绝对差尽可能小。请帮助 Petya 划分这些整数。每个 #cf_span[n] 个整数必须恰好属于一个组。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 60 000]) —— Petya 拥有的整数个数。第一行输出可能的最小绝对差。第二行输出第一组的大小，后跟该组中的整数。你可以按任意顺序输出这些整数。如果有多个答案，输出任意一个即可。在第一个例子中，你需要将整数 #cf_span[1] 和 #cf_span[4] 放入第一组，将 #cf_span[2] 和 #cf_span[3] 放入第二组。这样每组的和都是 #cf_span[5]，绝对差为 #cf_span[0]。在第二个例子中，只有两个整数，且两组都必须非空，因此你必须将一个整数放入第一组，另一个放入第二组。这样每组整数之和的绝对差为 #cf_span[1]。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 60 000]) —— Petya 拥有的整数个数。 ## Output 第一行输出可能的最小绝对差。第二行输出第一组的大小，后跟该组中的整数。你可以按任意顺序输出这些整数。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个例子中，你需要将整数 #cf_span[1] 和 #cf_span[4] 放入第一组，将 #cf_span[2] 和 #cf_span[3] 放入第二组。这样每组的和都是 #cf_span[5]，绝对差为 #cf_span[0]。在第二个例子中，只有两个整数，且两组都必须非空，因此你必须将一个整数放入第一组，另一个放入第二组。这样每组整数之和的绝对差为 #cf_span[1]。

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 60{,}000 $. Let $ S = \{1, 2, \dots, n\} $, and let $ T = \sum_{i=1}^n i = \frac{n(n+1)}{2} $. **Constraints** Partition $ S $ into two non-empty disjoint subsets $ A $ and $ B $ such that $ A \cup B = S $ and $ A \cap B = \emptyset $. **Objective** Minimize $ \left| \sum_{a \in A} a - \sum_{b \in B} b \right| = \left| 2 \sum_{a \in A} a - T \right| $. Output: - The minimal absolute difference. - A subset $ A \subseteq S $, $ \emptyset \subset A \subset S $, achieving this minimum, along with $ |A| $ and the elements of $ A $.

Samples

Input #1

Output #1

0
2 1 4

Input #2

Output #2

1
1 1

API Response (JSON)

{
  "problem": {
    "name": "C. Dividing the numbers",
    "description": {
      "content": "Petya has _n_ integers: 1, 2, 3, ..., _n_. He wants to split these integers in **two non-empty** groups in such a way that the absolute difference of sums of integers in each group is as small as poss",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF899C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya has _n_ integers: 1, 2, 3, ..., _n_. He wants to split these integers in **two non-empty** groups in such a way that the absolute difference of sums of integers in each group is as small as poss...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 有 #cf_span[n] 个整数：#cf_span[1, 2, 3, ..., n]。他希望将这些整数划分为 *两个非空* 组，使得每组整数之和的绝对差尽可能小。\n\n请帮助 Petya 划分这些整数。每个 #cf_span[n] 个整数必须恰好属于一个组。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 60 000]) —— Petya 拥有的整数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 60{,}000 $.  \nLet $ S = \\{1, 2, \\dots, n\\} $, and let $ T = \\sum_{i=1}^n i = \\frac{n(n+1)}{2} $.  \n\n**Constraints**  \nPartition $ S $ in...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments