Dividete in 2 gruppi (Editoriale)

Notiamo che se i numeri $n$ e n - 3 vengono inseriti in un gruppo, e n - 1 e n - 2 in un altro (la somma dei numeri in ciascun gruppo sarà uguale), allora il problema si riduce a un problema analogo di dimensione minore, ovvero alla suddivisione in gruppi dei numeri 1, 2, ..., n - 4.

Per n \le 3 distribuiamo i numeri nei gruppi nel seguente modo:

• Se restano tre numeri $1,2,3$, essi possono essere divisi in due gruppi: $\{1,2\}$ e $\{3\}$.

• Se restano due numeri $1,2$, li dividiamo nei gruppi: $\{1\}$ e $\{2\}$. La differenza delle somme dei numeri nei gruppi sarà $1$.

• Se resta un numero $1$, esso può essere inserito in uno qualsiasi dei gruppi. La differenza delle somme dei numeri nei gruppi sarà $1$.

Se la somma di tutti i numeri da $1$ a $n$ è pari, allora essi possono essere divisi in due gruppi con somma uguale.

Se la somma di tutti i numeri da $1$ a $n$ è dispari, allora essi possono essere divisi in due gruppi con una differenza delle somme pari a 1.

Esempio

Sia n = 10. I numeri vengono disposti nei gruppi nel seguente modo:

Sia n = 11. I numeri vengono disposti nei gruppi nel seguente modo:

Implementazione dell'algoritmo

Leggiamo il valore di input $n$.

scanf("%d", &n);

Impostiamo le somme iniziali dei numeri nei gruppi s_1 e s_2 uguali a $0$.

s1 = s2 = 0;

Scorriamo i numeri da $n$ a $1$ in ordine decrescente.

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

Se s_1 < s_2, allora inseriamo il numero $i$ nel primo gruppo. Altrimenti inseriamo il numero $i$ nel secondo gruppo.

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

Stampiamo le dimensioni dei gruppi.

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

Stampiamo i numeri del primo gruppo.

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

Stampiamo i numeri del secondo gruppo.

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