Foto di gruppo (Editoriale)

Il numero a_1 può assumere valori da $1$ a $n$. Per un valore fissato di a_1, i restanti numeri della sequenza a_2, ..., a_n sono determinati univocamente. Scorriamo a_1 da $1$ a $n$, ricostruiamo la sequenza $a$ e verifichiamo se essa è una permutazione dei numeri da $1$ a $n$ (tutti gli a_i devono essere diversi e trovarsi nell'intervallo da $1$ a $n$). Non appena la sequenza $a$ ricostruita risulta essere una permutazione, la stampiamo e terminiamo l'esecuzione del programma.

Poiché b_i = a_i + a_{i+1}, allora a_{i+1} = b_i - a_i oppure a_i = b_{i-1} - a_{i-1}.

Esempio

Sia a_1 = 3. Allora la sequenza b = (4, 6, 7, 6) genera la seguente sequenza $a$:

La sequenza a = (3, 1, 5, 2, 4) è una permutazione. Valgono le relazioni: 3 + 1 = 4, 1 + 5 = 6, 5 + 2 = 7 e 2 + 4 = 6.

Se, ad esempio, si scegliesse a_1 = 1, allora dalla sequenza di ingresso b = (4, 6, 7, 6) verrebbe ricostruita la seguente sequenza $a$:

La sequenza a = (1, 3, 3, 4, 2) non è una permutazione.

Implementazione dell'algoritmo

Dichiariamo gli array di lavoro. L'array $used$ verrà utilizzato per verificare se $a$ è una permutazione.

#define MAX 1001
int a[MAX], b[MAX], used[MAX];

Leggiamo i dati di input.

scanf("%d", \&n);
for (i = 0; i < n - 1; i++)
  scanf("%d", \&b[i]);

Scorriamo il valore di a_0 da $1$ a $n$.

for (a0 = 1; a0 <= n; a0++)
{
  a[0] = a0;

Calcoliamo gli elementi della sequenza $a$ secondo la formula a_i = b_{i-1} - a_{i-1}.

  for (i = 1; i < n; i++)
    a[i] = b[i - 1] - a[i - 1];

Azzeriamo l'array $used$.

  for (i = 1; i <= n; i++) used[i] = 0;

Verifichiamo se $a$ è una permutazione. Per far ciò, ciascuno dei valori a_i deve comparire nella sequenza una sola volta e trovarsi nell'intervallo da $1$ a $n$. La variabile $flag$ viene impostata a $1$ se la sequenza $a$ non è una permutazione.

  flag = 0;
  for (i = 0; i < n; i++)
  {
    if (a[i] < 1 || a[i] > n || used[a[i]])
    {
      flag = 1;
      break;
    }
    used[a[i]] = 1;
  }

Se la sequenza $a$ è una permutazione, la stampiamo e terminiamo l'esecuzione del programma.

  if (flag == 0)
  {
    for (i = 0; i < n; i++)
      printf("%d ", a[i]);
    printf("\n");
    return 0;
  }
}

Implementazione in Python

Leggiamo i dati di input.

n = int(input())
b = list(map(int, input().split()))

Dichiariamo gli array di lavoro. L'array $used$ verrà utilizzato per verificare se $a$ è una permutazione.

a = [0] * n
used = [0] * (n + 1)

Scorriamo il valore di a_0 da $1$ a $n$.

for a0 in range(1, n + 1):
  a[0] = a0

Calcoliamo gli elementi della sequenza $a$ secondo la formula a_i = b_{i-1} - a_{i-1}.

  for i in range(1, n):
    a[i] = b[i - 1] - a[i - 1]

Azzeriamo l'array $used$.

  for i in range(1, n + 1):
    used[i] = 0

Verifichiamo se $a$ è una permutazione. Per far ciò, ciascuno dei valori a_i deve comparire nella sequenza una sola volta e trovarsi nell'intervallo da $1$ a $n$. La variabile $flag$ viene impostata a $1$ se la sequenza $a$ non è una permutazione.

  flag = 0
  for i in range(n):
    if a[i] < 1 or a[i] > n or used[a[i]]:
      flag = 1
      break
    used[a[i]] = 1

Se la sequenza $a$ è una permutazione, la stampiamo e terminiamo l'esecuzione del programma.

  if flag == 0:
    print(*a)
    break