Divide into 2 groups#11339

Divide into 2 groups (Editorial)

Note that if the numbers $n$ and $n - 3$ n - 3 are placed in one group, and $n - 1$ n - 1 and $n - 2$ n - 2 are placed in the other (so that the sum of numbers in each group is equal), the problem reduces to a similar problem of smaller size, namely, dividing the numbers $1, 2, ..., n - 4$ 1, 2, ..., n - 4 into two groups.

For $n \leq 3$ n \le 3, the numbers are divided into groups as follows:

If three numbers $1, 2, 3$ remain, they can be divided into two groups: ${1, 2}$ and ${3}$ .
If two numbers $1, 2$ remain, they can be divided into groups: ${1}$ и ${2}$ . The difference between the sums of the groups will be $1$ .
If one number $1$ remains, it can be placed in either group. The difference between the sums of the groups will be $1$ .

If the sum of all numbers from $1$ to $n$ is even, they can be divided into two groups with equal sums.

If the sum of all numbers from $1$ to $n$ is odd, they can be divided into two groups with a sum difference of $1$ .

Example

Let $n = 10$ n = 10. The numbers are placed into groups as follows:

Let $n = 11$ n = 11. The numbers are placed into groups as follows:

Algorithm implementation

Read the input value $n$ .

scanf("%d", &n);

Initialize the initial sums of the numbers in the groups, $s_{1}$ s_1 and $s_{2}$ s_2 to $0$ .

s1 = s2 = 0;

Iterate through the numbers from $n$ down to $1$ .

for (i = n; i > 0; i--)

If $s_{1} < s_{2}$ s_1 < s_2, place the number $i$ into the first group. Otherwise, place the number $i$ into the second group.

  if (s1 < s2)
  {
    s1 += i;
    a.push_back(i);
  }
  else
  {
    s2 += i;
    b.push_back(i);
  }

C++

Print the sizes of the groups.

printf("%d %d\n", a.size(), b.size());

Print the numbers of the first group.

for (i = 0; i < a.size(); i++)
  printf("%d ", a[i]);
printf("\n");

Print the numbers of the second group.

for (i = 0; i < b.size(); i++)
  printf("%d ", b[i]);
printf("\n");