Во-первых, предположим, что не существует такого , чтобы . В этом случае мы можем доказать, что ответ всегда , где — общее количество креветок.

Доказательство заключается в следующем. Очевидно, что мы не можем сделать больше, чем пары. С другой стороны, мы можем в явном виде построить пары следующим алгоритмом: Пусть — все креветки, отсортированные в порядке неубывания. Тогда для каждого : (в противном случае нет креветки с целым числом , что является противоречием). Таким образом, мы можем построить пары . Таким образом, мы можем сделать пары.

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

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

Решение на 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)