欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

Codeforces Round #650 (Div. 3) B. Even Array

程序员文章站 2022-08-29 13:10:15
B. Even Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a[0…n−1] of length n which consists of non-negative integers. Note that array indices start from zero.An array i...

B. Even Array
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array a[0…n−1] of length n which consists of non-negative integers. Note that array indices start from zero.

An array is called good if the parity of each index matches the parity of the element at that index. More formally, an array is good if for all i (0≤i≤n−1) the equality imod2=a[i]mod2 holds, where xmod2 is the remainder of dividing x by 2.

For example, the arrays [0,5,2,1] and [0,17,0,3] are good, and the array [2,4,6,7] is bad, because for i=1, the parities of i and a[i] are different: imod2=1mod2=1, but a[i]mod2=4mod2=0.

In one move, you can take any two elements of the array and swap them (these elements are not necessarily adjacent).

Find the minimum number of moves in which you can make the array a good, or say that this is not possible.

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases in the test. Then t test cases follow.

Each test case starts with a line containing an integer n (1≤n≤40) — the length of the array a.

The next line contains n integers a0,a1,…,an−1 (0≤ai≤1000) — the initial array.

Output
For each test case, output a single integer — the minimum number of moves to make the given array a good, or -1 if this is not possible.

Example
input

4
4
3 2 7 6
3
3 2 6
1
7
7
4 9 2 1 18 3 0
output
2
1
-1
0
My Answer Code:

/*
	Author:Albert Tesla Wizard
	Time:2020/10/29 18:27
*/
#include<bits/stdc++.h>
using namespace std;
int verdict1(vector<int>a)
{
    int cnt=0;
    for(int i=0;i<a.size();i+=2)
    {
        if(a[i]%2!=i%2)cnt++;
    }
    return cnt;
}
int verdict2(vector<int>a)
{
    int cnt=0;
    for(int i=1;i<a.size();i+=2)
    {
        if(a[i]%2!=i%2)cnt++;
    }
    return cnt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,num;
    cin>>t;
    vector<int>ans(t);
    for(int i=0;i<t;i++)
    {
        cin>>num;
        vector<int>a(num);
        for(int j=0;j<num;j++)cin>>a[j];
        if(verdict1(a)==verdict2(a))ans[i]=verdict1(a);
        else ans[i]=-1;
    }
    for(int i=0;i<t;i++)cout<<ans[i]<<'\n';
    return 0;
}

本文地址:https://blog.csdn.net/AlberTesla/article/details/109366117