26.04 Прочие прототипы

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

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

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

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

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

def solve_python(n, a):
    ans = 0
    for i in range(n - 1):
        ans += a[i] // 2
        if a[i] % 2 and a[i + 1] != 0:
            ans += 1
            a[i + 1] -= 1
    ans += a[n - 1] // 2
    return ans

f = open(’26.txt’)
n = int(f.readline())
a = [int(i) for i in f]
print(solve_python(n, a))