Перестановки С++

Question

у меня вопрос по одному заданию которое я не очень могу понять, оно звучит так:

Необходимо определить, существует ли перестановка длины n для заданных Si ( i=1 ,2 ,…,n−1 ) — сумм ее соседних элементов (первого и второго, второго и третьего и так далее). Если существует, то вывести любую перестановку, обладающую вышеуказанным свойством, иначе вывести −1

Вход
9
9 11 8 13
12 9 6 12

Выход 6 3 9 2 7 1 5 8 4

Я понял что сначала мы должны задать int n, и инициализировать динамический массив размера n-1, после чего ввести элементы массива, и разложить их так что бы при выходе мы получили что-то такое

Элемент1 + Элемент2 = первому числу вводимого массива

Элемент2 + Элемент3 = второму числу вводимого массива

И так далее, условно должна получится вот такая схемка

Я более менее понимаю как положить в массив элементы сумм первого массива, но не понимаю как получить в коде вот такую схему, приведенную выше, помогите пожалуйста

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int* swapN = new int[n - 1];
    int* finalArray = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> swapN[i];
    }
    for (int k = 0; k < n; k++) {
        finalArray[k] = swapN[k] + swapN[k + 1];
    }
    for (int j = 0; j < n; j++) {
        cout << finalArray[j] << endl;
    }




    delete[]finalArray;
    delete[]swapN;
}

Дополнение к заданию

В первой строке дано число n ( 3≤n≤1000 ) — количество элементов в искомой перестановке. Во второй строке даны Si для i=1,3 , 5, ... — суммы элементов искомой перестановки: первого и второго, третьего и четвертого, и так далее. В третьей строке даны Si для i=2 ,4 , 6, .. . — суммы элементов: второго и третьего, четвертого и пятого и так далее. Все Si целые и находятся в диапазоне 3≤Si≤2⋅109 .

Выведите искомую перестановку, если существует; элементы перестановки разделять одним пробелом; если таких перестановок несколько, выведите любую. Если таковой перестановки не существует, выведите −1

Answer 1

Я опишу алгоритм, а уж код набросайте сами...

Выпишем ряд сумм и ряд чисел перестановки

    S1    S2    S3    S4    ...    Sn
a0      a1    a2    a3    a4    ...    an

Пусть первое число - a0=x. Тогда второе a1 = S1-x, a2 = S2-S1+x и так далее. Словом, все выражения для ai будут представлять собой S-x или x-S, где S - некоторые значения.

Так как числа натуральные, надо просто найти все допустимые значения, для которых это натуральные числа. Надо просто найти минимальное из S в выражениях S-x, и максимальное - в x-S. И посмотреть, имеется ли такое натуральное x, которое удовлетворяет решению.

Например, для простенького ряда

    5     6     5     
x     5-x   x+1   4-x

Минимальное для первого случая - 4, т.е. 4-x >= 1, или x <= 3.
Максимальное для второго случая - -1, т.е. x+1 >= 1, или x >= 0.

Решение есть, x == 3, перестановка -

 3  2  4  1

Вот и всё. Код сами напишете?

Вот код...

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> S(n-1);
    for(int i = 0; i < n/2; ++i)     cin >> S[i*2];
    for(int i = 0; i < (n-1)/2; ++i) cin >> S[i*2+1];

    int M = S[0], m = S[1] - M,   // Первые два значения
        value = 0;
    bool minus = false;

    for(int i = 0; i < S.size(); ++i)
    {
        value = S[i] - value;

        if (minus = !minus)
        {
            if (M > value) M = value;
        }
        else
        {
            if (m > value) m = value;
        }
    }

    if (M-1 < 1 - m) cout << -1;
    else
    {
        int x = M - 1;   // Выбираем максимально возможный
        cout << x;
        for(int i = 0; i < S.size(); ++i)
            cout << " " << (x = S[i] - x);
    }
}

БЛОГ НА HUSL

Перестановки С++

Ответы (1 шт):