Fotoatış (Həll təhlili)

a_1 ədədi $1$-dən $n$-ə qədər dəyərlər ala bilər. a_1-in sabit dəyərində ardıcıllığın qalan ədədləri a_2, ..., a_n birmənalı şəkildə müəyyən olunur. a_1-i $1$-dən $n$-ə qədər sıra ilə yoxlayırıq, $a$ ardıcıllığını bərpa edirik və onun $1$-dən $n$-ə qədər olan ədədlərin perimutasiyası olub-olmadığını yoxlayırıq (bütün a_i-lər müxtəlif olmalı və $1$-dən $n$-ə qədər aralıqda olmalıdır). Bərpa olunmuş $a$ ardıcıllığı perimutasiya olan kimi, onu çap edirik və proqramın işini dayandırırıq.

b_i = a_i + a_{i+1} olduğuna görə, a_{i+1} = b_i - a_i və ya a_i = b_{i-1} - a_{i-1}.

Nümunə

Tutaq ki, a_1 = 3. Onda b = (4, 6, 7, 6) ardıcıllığı aşağıdakı $a$ ardıcıllığını yaradır:

a = (3, 1, 5, 2, 4) ardıcıllığı bir perimutasiyadır. Aşağıdakı münasibətlər ödənilir: 3 + 1 = 4, 1 + 5 = 6, 5 + 2 = 7 və 2 + 4 = 6.

Əgər, məsələn, a_1 = 1 seçilərsə, b = (4, 6, 7, 6) giriş ardıcıllığına əsasən aşağıdakı $a$ ardıcıllığı bərpa olunacaq:

a = (1, 3, 3, 4, 2) ardıcıllığı perimutasiya deyil.

Alqoritmin realizasiyası

İşçi massivləri elan edək. $used$ massivi $a$-nın perimutasiya olub-olmadığını yoxlamaq üçün istifadə olunacaq.

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

Giriş məlumatlarını oxuyuruq.

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

a_0 dəyərini $1$-dən $n$-ə qədər sıra ilə yoxlayırıq.

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

$a$ ardıcıllığının elementlərini a_i = b_{i-1} - a_{i-1} formuluna əsasən hesablayırıq.

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

$used$ massivini sıfırlayırıq.

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

$a$-nın perimutasiya olub-olmadığını yoxlayırıq. Bunun üçün a_i dəyərlərinin hər biri ardıcıllıqda yalnız bir dəfə rast gəlinməlidir və $1$-dən $n$-ə qədər aralıqda olmalıdır. Əgər $a$ ardıcıllığı perimutasiya deyilsə, $flag$ dəyişəni $1$-ə bərabər olur.

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

Əgər $a$ ardıcıllığı perimutasiya olarsa, onu çap edirik və proqramın işini dayandırırıq.

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

Python realizasiyası

Giriş məlumatlarını oxuyuruq.

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

İşçi massivləri elan edək. $used$ massivi $a$-nın perimutasiya olub-olmadığını yoxlamaq üçün istifadə olunacaq.

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

a_0 dəyərini $1$-dən $n$-ə qədər sıra ilə yoxlayırıq.

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

$a$ ardıcıllığının elementlərini a_i = b_{i-1} - a_{i-1} formuluna əsasən hesablayırıq.

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

$used$ massivini sıfırlayırıq.

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

$a$-nın perimutasiya olub-olmadığını yoxlayırıq. Bunun üçün a_i dəyərlərinin hər biri ardıcıllıqda yalnız bir dəfə rast gəlinməlidir və $1$-dən $n$-ə qədər aralıqda olmalıdır. Əgər $a$ ardıcıllığı perimutasiya deyilsə, $flag$ dəyişəni $1$-ə bərabər olur.

  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

Əgər $a$ ardıcıllığı perimutasiya olarsa, onu çap edirik və proqramın işini dayandırırıq.

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