Задача к ЕГЭ по информатике на тему «прочие прототипы» №5

У Креветкоеда большая коллекция креветок разных размеров. Каждая креветка имеет размер равный целому числу от $1$ до $N$ (не более $2 ⋅106$ ) включительно. У него есть $Ai$ (каждое не более $103$ ) креветок размера $i$ . Две креветки могут образовать пару, если абсолютное значение разности их размеров составляет не более $1$ . Креветкоед хочет создать максимальное количество пар из своих креветок при условии, что ни одна креветка не должна использоваться в нескольких парах. Найдите максимальное количество пар, которые он может создать и съесть.

В первой строке файла $26.txt$ вам дано число $N$ , а в следующих $N$ строках того же файла $N$ целых чисел $Ai.$

Во-первых, предположим, что не существует такого $i$ , чтобы $Ai = 0$ . В этом случае мы можем доказать, что ответ всегда $S∕∕2$ , где $S$ — общее количество креветок.

Доказательство заключается в следующем. Очевидно, что мы не можем сделать больше, чем $S∕∕2$ пары. С другой стороны, мы можем в явном виде построить $S∕∕2$ пары следующим алгоритмом: Пусть $x1,...,xS$ — все креветки, отсортированные в порядке неубывания. Тогда для каждого $i$ : $xi+1 − xi ≤ 1$ (в противном случае нет креветки с целым числом $xi + 1$ , что является противоречием). Таким образом, мы можем построить $S∕∕2$ пары $(x1,x2),(x3,x4),...$ . Таким образом, мы можем сделать $S∕∕2$ пары.

Когда $Ai = 0$ для некоторого $i$ , вы не можете использовать карты с целым числом $i$ , поэтому вы можете разделить последовательность на $i$ , и для каждой части вы можете решить задачу независимо (ответ — сумма этих независимых задач).

На самом деле можно даже не делать сплит по $0$ . Достаточно лишь посмотреть при рассмотрении креветок размера $i$ , не осталась ли у вас ровно $1$ креветка размера $i− 1$ . Следовательно, вы можете разделить последовательность $Ai$ , по $0$ , и для каждой части вычислить половину (с округлением дробной части в меньшую сторону) суммы, и ответом будет сумма этих чисел. Асимптотика решения $O (N )$ .

Решение на C++

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    long long ans = 0;
    ans += a[0] / 2; a[0] -= 2 * ans;
    for(int i = 1; i < n; ++i){
        if(a[i - 1] > 0){
            if(a[i] > 0){
                --a[i];
                ++ans;
            }
        }
        ans += a[i] / 2;
        a[i] -= a[i] / 2 * 2;
    }
    cout << ans << ’n’;
}

Решение на Python

f = open("26.txt")
n = int(f.readline())
a = [int(f.readline()) for _ in range(n)]
ans = 0
for i in range(n - 1):
    if a[i] >= a[i + 1]:
        ans += a[i + 1]
        a[i] -= a[i + 1]
        a[i + 1] = 0
        ans += a[i] // 2
        a[i] = a[i] % 2
    else:
        ans += a[i]
        a[i + 1] -= a[i]
        a[i] = 0
        ans += a[i + 1] // 2
        a[i + 1] = a[i + 1] % 2
print(ans)

Ответ: 24995271