Решение задачи Ахахахахахахахаха с Codeforces

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


У Александры есть массив a четной длины, состоящий из чисел 0 и 1. Элементы массива пронумерованы от 1 до n. Она хочет удалить из него не более n2 элементов (где n — его длина) таким образом, чтобы знакопеременная сумма массива была равна 0 (т.е. a1−a2+a3−a4+…=0). Иными словами, Александра хочет, чтобы сумма всех элементов на нечетных позициях была равна сумме всех элементов на четных позициях. Элементы, которые вы удаляете, не обязаны быть последовательными.

К примеру, если у нее был массив a=[1,0,1,0,0,0], и она удалила 2-й и 4-й элементы, то a станет равным [1,1,0,0] и его знакопеременная сумма будет равна 1−1+0−0=0.

Помогите ей!

Код

#include <bits/stdc++.h>

using namespace std;
void solve(){
    int n, t;
    cin >> n;
    vector<int> a(2);
    for(int i = 0; i < n; ++i){
        cin >> t;
        a[t]++;
    }
    if(a[0] >= n/2){
        cout << n/2 << endl;
        for(int i = 0; i < n/2; ++i)
            cout << 0 << " ";
    }
     else if(a[1] >= n/2)
        if((n/2) % 2 == 0){
            cout << n/2 << endl;
            for(int i = 0; i < n/2; ++i)
                cout << 1 << " ";
        }
        else{
            cout << n/2 + 1 << endl;
            for(int i = 0; i <= n/2; ++i)
                cout << 1 << " ";
        }

    cout << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

         

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



Комментарии

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