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

Задача A. Покраска суммой

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

1 секунда

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

256 мегабайт

У вас есть массив целых чисел $a_1, \ldots, a_n$ размера $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;

}