Фотострільба (Розбір)

Число a_1 може приймати значення від $1$ до $n$. При фіксованому значенні a_1 решта чисел послідовності a_2, ..., a_n визначаються однозначно. Перебираємо a_1 від $1$ до $n$, відновлюємо послідовність $a$ і перевіряємо, чи є вона перестановкою чисел від $1$ до $n$ (усі a_i повинні бути різними і знаходитися в межах від $1$ до $n$). Як тільки відновлена послідовність $a$ буде перестановкою, виводимо її і завершуємо роботу програми.

Оскільки b_i = a_i + a_{i+1}, то a_{i+1} = b_i - a_i або a_i = b_{i-1} - a_{i-1}.

Приклад

Нехай a_1 = 3. Тоді послідовність b = (4, 6, 7, 6) породжує наступну послідовність $a$:

Послідовність a = (3, 1, 5, 2, 4) є перестановкою. Мають місце співвідношення: 3 + 1 = 4, 1 + 5 = 6, 5 + 2 = 7 і 2 + 4 = 6.

Якщо, наприклад, вибрати a_1 = 1, то за вхідною послідовністю b = (4, 6, 7, 6) буде відновлена наступна послідовність $a$:

Послідовність a = (1, 3, 3, 4, 2) не є перестановкою.

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

Оголосимо робочі масиви. Масив $used$ буде використовуватися для перевірки, чи є $a$ перестановкою.

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

Читаємо вхідні дані.

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

Перебираємо значення a_0 від $1$ до $n$.

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

Обчислюємо елементи послідовності $a$ за формулою a_i = b_{i-1} - a_{i-1}.

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

Обнуляємо масив $used$.

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

Перевіряємо, чи є $a$ перестановкою. Для цього кожне із значень a_i повинно зустрічатися в послідовності тільки один раз, і знаходитися в межах від $1$ до $n$. Змінна $flag$ встановлюється в $1$, якщо послідовність $a$ не є перестановкою.

  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;
  }

Якщо послідовність $a$ є перестановкою, то виводимо її і завершуємо роботу програми.

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

Python реалізація

Читаємо вхідні дані.

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

Оголосимо робочі масиви. Масив $used$ буде використовуватися для перевірки, чи є $a$ перестановкою.

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

Перебираємо значення a_0 від $1$ до $n$.

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

Обчислюємо елементи послідовності $a$ за формулою a_i = b_{i-1} - a_{i-1}.

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

Обнуляємо масив $used$.

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

Перевіряємо, чи є $a$ перестановкою. Для цього кожне із значень a_i повинно зустрічатися в послідовності тільки один раз, і знаходитися в межах від $1$ до $n$. Змінна $flag$ встановлюється в $1$, якщо послідовність $a$ не є перестановкою.

  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

Якщо послідовність $a$ є перестановкою, то виводимо її і завершуємо роботу програми.

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