Решение задачи Таня и конфеты с Codeforces

Без пояснения   Просмотров: 66


У Тани есть n конфет, пронумерованных от 1 до n. i-я конфета весит ai.

Она планирует съесть ровно n−1 конфету и отдать оставшуюся конфету своему папе. Таня ест конфеты в порядке увеличения их номеров, ровно по одной конфете каждый день.

Ваша задача — найти количество таких конфет i (назовем эти конфеты хорошими), что если папа получит i-ю конфету, то сумма весов конфет, которые Таня съест в четные дни, будет равна сумме весов конфет, которые Таня съест в нечетные дни. Заметим, что сначала она отдает конфету, а потом начинает есть оставшиеся конфеты одну за другой.

Например, n=4, а веса равны [1,4,3,3]. Рассмотрим все возможны варианты дать папе конфету:

Таня дает 1-ю конфету папе (a1=1), остались конфеты [4,3,3]. Она съест a2=4 в первый день, a3=3 во второй день, a4=3 в третий день. Таким образом, в нечетные дни она съест 4+3=7, а в четные дни она съест 3. Так как 7≠3, этот вариант не должен быть учтен в ответе (эта конфета не является хорошей).
Таня дает 2-ю конфету папе (a2=4), остались конфеты [1,3,3]. Она съест a1=1 в первый день, a3=3 во второй день, a4=3 в третий день. Таким образом, в нечетные дни она съест 1+3=4, а в четные дни она съест 3. Так как 4≠3, этот вариант не должен быть учтен в ответе (эта конфета не является хорошей).
Таня дает 3-ю конфету папе (a3=3), остались конфеты [1,4,3]. Она съест a1=1 в первый день, a2=4 во второй день, a4=3 в третий день. Таким образом, в нечетные дни она съест 1+3=4, а в четные дни она съест 4. Так как 4=4, этот случай должен быть учтен в ответе (эта конфета является хорошей).
Таня дает 4-ю конфету папе (a4=3), остались конфеты [1,4,3]. Она съест a1=1 в первый день, a2=4 во второй день, a3=3 в третий день. Таким образом, в нечетные дни она съест 1+3=4, а в четные дни она съест 4. Так как 4=4, этот случай должен быть учтен в ответе (эта конфета является хорошей).
Суммарно здесь есть 2 случая, которые должны быть учтены (эти конфеты являются хорошими), таким образом, ответ равен 2.

Код

#include <iostream>
using namespace std;
int n,a[200001],st[2],dr[2],r;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        dr[i%2]+=a[i];
    }
    for(int i=1; i<=n; i++)
    {
        st[(i-1)%2]+=a[i-1];
        dr[i%2]-=a[i];
        if(st[0]+dr[1]==st[1]+dr[0])
            r++;
    }
    cout<<r;
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться