4-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Есеп A. Қосындымен бояу

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Сізде $n$ бүтін саннан тұратын $a_1, \ldots, a_n$ массиві бар. Бастапқыда массивтегі әрбір сан ақ түске боялған. Бір операцияда сіз:

1. Үш $(a_i, a_j, a_k)$ ақ санды таңдайсыз ($1 <= i, j, k <= n$, $i \neq j$, $i \neq k$, $j \neq k$).
2. Егер $a_i + a_j$ мәні $a_k$ мәнінен үлкен болса, $a_k$ санын қара түске бояйсыз.

Бұл әрекетті мүмкіндігінше қайталауға міндеттісіз. Процесс барысында кейбір сандар қара түске боялады, ал қалғандары ақ болып қалады. Процестің ең соныңдағы мүмкін болатын бояулардың санын санау қажет.

Формат входного файла

Бірінші жолда бір бүтін $n$ саны — массив өлшемі бар ($3 <= n <= 10^5$). Екінші жолда $n$ бүтін сан $a_1, \ldots, a_n$ ($-10^9 <= a_i <= 10^9$) бар.

Формат выходного файла

Бір бүтін санды басып шығарыңыз — мүмкін соңғы бояулар саны. Берілген шектеулер бойынша жауап ешқашан $10^{18}$ мәнінен аспайтынын көрсетуге болады.

Примеры:

Вход

3
2 2 5

Ответ

2

Вход

4
-3 1 2 2

Ответ

3

( Temirlan Baibolov )

Комментарий/решение

Для решения задачи можно воспользоваться следующим алгоритмом:

Посчитать количество чисел, которые могут быть окрашены в черный цвет (то есть имеют два белых соседа), и обозначить их количество как k.

Рассмотреть все возможные варианты раскраски таких чисел (их будет 2^k).

Для каждой раскраски произвести операции, как указано в условии, и получить конечную раскраску.

Подсчитать количество уникальных конечных раскрасок и вывести ответ.

Реализация алгоритма на языке Python может выглядеть следующим образом:

n = int(input())

a = list(map(int, input().split()))

k = 0

for i in range(1, n-1):

if a[i-1] < a[i] and a[i] > a[i+1]:

k += 1

result = set()

for i in range(2**k):

new_a = a[:]

for j in range(k):

if i & (1 << j):

new_a[j+1] = -new_a[j+1]

for j in range(1, n-1):

if new_a[j-1] < new_a[j] and new_a[j] > new_a[j+1]:

new_a[j] = -new_a[j]

result.add(tuple(new_a))

print(len(result))

Первый цикл подсчитывает количество чисел, которые могут быть окрашены в черный цвет, и обозначает их количество как k. Второй цикл перебирает все возможные варианты раскраски таких чисел, применяет операции, как указано в условии, и получает конечную раскраску. Затем подсчитывается количество уникальных конечных раскрасок и выводится ответ.

В данной реализации используется множество result для хранения уникальных раскрасок в виде кортежей.

Ответ на С++

#include <iostream>

#include <vector>

#include <set>

using namespace std;

int main() {

int n;

cin >> n;

vector<int> a(n);

for (int i = 0; i < n; i++) {

cin >> a[i];

}

int k = 0;

for (int i = 1; i < n - 1; i++) {

if (a[i - 1] < a[i] && a[i] > a[i + 1]) {

k += 1;

}

}

set<vector<int>> result;

for (int i = 0; i < (1 << k); i++) {

vector<int> new_a = a;

for (int j = 0; j < k; j++) {

if (i & (1 << j)) {

new_a[j + 1] = -new_a[j + 1];

}

}

for (int j = 1; j < n - 1; j++) {

if (new_a[j - 1] < new_a[j] && new_a[j] > new_a[j + 1]) {

new_a[j] = -new_a[j];

}

}

result.insert(new_a);

}

cout << result.size() << endl;

return 0;

}