2018
Сообщений: 27
15.03.2019, 18:38 3
Лучший ответ Сообщение было отмечено CyberNinjaProg как решение
Решение
Я бы мог тебе написать готовый код, но для начала просто алгоритм объясню.
Во первых, симметричность такой последовательности разобъём на 2 типа - чётная и нечётная.
Чётная последовательность делиться на две одинаковые отражённые горизонтально части. Например, "12122121".
Нечётная делиться таким же образом, только посередине есть цифра не имеющая пары. Например, "123454321".
Соответственно нам надо проверить входную последовательность на возможность создать наикратчайшую симметричную последовательность одного из двух типов.
Конкретный алгоритм следующий:
//Для чётно-симметричной последовательности
Берём половину входной последовательности (если её длина нечётная, берём с округлением в большую сторону), и начинаем по одному её элементу, от последнего и до первого, сравнивать их с элементами второй половины, но только взятых в порядке слева-направо.
То-есть, от последовательности 12122, берём 121, и сравниваем с 22: i[2] == i[3] (1 == 2).
Сравниваем так до тех пор, пока последовательность не закончиться. Тогда, оставшаяся несрАвненной последовательность цифр взятой в порядке справа налево и будет ответом (вместе с количеством этих цифр).
Если же при сравнении, цифры оказались разными, начинаем всё сначала, только с цифры на одну правее.
То-есть теперь берём уже не 121, а 1212, и делаем всё предыдущее снова. Если последовательность закончилась, то есть если мы например взяли уже 12345 от 12345, то сравнивать уже ничего не нужно, надо просто взять всю последовательность в обратном порядке - "1234554321".
//Для нечётно-симметричной последовательности
Делаем всё то же самое, что и для чётно-симметричной последовательности, только начинаем сравнивать не с цифры, следующей той, у которой мы разделили, а через одну.
То-есть, для входной последовательности 12345, берём 123 и начинаем сравнивать цифру 3 с цифрой 5, а не с цифрой 4.
Если же последовательность закончилась, берём всю последовательность кроме последней цифры в обратном порядке, это и будет ответ.
//Итог
Для того, чтобы найти правильный ответ, надо найти и чётную, и нечётную последовательности. Затем сравнить длину обоих ответов. Кратчайший ответ будет верным.
#include <iostream>
using namespace std;
int main()
{
int N;
cin >> N;
int* arr = new int[N];
for (int i(0); i < N; ++i) cin >> arr[i];
int count(N - 1);
int result = 0;
for (; count >= 0 && result < arr[count]; --count) {
if (count > 0) result += arr[count] - arr[count - 1];
}
int sum = 0;
for (int i(count + 1); i < N; ++i) sum += arr[i];
result = sum / (N - count);
if (sum > result*(N - count)) ++result;
cout << result;
}
Объяснение:
