Розділіть на 2 групи (Розбір)

Зауважимо, що якщо числа $n$ і n - 3 помістити в одну групу, а n - 1 і n - 2 помістити в іншу (сума чисел у кожній групі буде однаковою), то задача зведеться до аналогічної задачі меншої розмірності, а саме до розбиття на групи чисел 1, 2, ..., n - 4.

Для n \le 3 числа розподілимо по групах наступним чином:

• Якщо залишаються три числа $1,2,3$, то їх можна розділити на дві групи: $\{1,2\}$ і $\{3\}$.

• Якщо залишаються два числа $1,2$, то розділимо їх на групи: $\{1\}$ і $\{2\}$. Різниця сум чисел у групах становитиме $1$.

• Якщо залишається одне число $1$, то його можна помістити в будь-яку групу. Різниця сум чисел у групах становитиме $1$.

Якщо сума всіх чисел від $1$ до $n$ парна, то їх можна розділити на дві групи з однаковою сумою.

Якщо сума всіх чисел від $1$ до $n$ непарна, то їх можна розділити на дві групи з різницею сум, що дорівнює 1.

Приклад

Нехай n = 10. Числа в групи розміщуємо наступним чином:

Нехай n = 11. Числа в групи розміщуємо наступним чином:

Реалізація алгоритму

Зчитуємо вхідне значення $n$.

scanf("%d", &n);

Встановлюємо початкові суми чисел у групах s_1 і s_2 рівними $0$.

s1 = s2 = 0;

Перебираємо числа від $n$ до $1$ у порядку спадання.

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

Якщо s_1 < s_2, то заносимо число $i$ в першу групу. Інакше заносимо число $i$ в другу групу.

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

Виводимо розміри груп.

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

Виводимо числа першої групи.

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

Виводимо числа другої групи.

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