Descripción
Se te proporciona un arreglo A[0…N−1] de longitud N, que consta de números enteros no negativos. Ten en cuenta que los índices del arreglo comienzan desde cero.
Un arreglo se considera BUENO si la paridad de cada índice coincide con la paridad del elemento en ese índice. De manera más formal, un arreglo es BUENO si para todos los i (0≤i≤n−1) se mantiene la igualdad:
i mod 2 = A[i] mod 2
donde x mod 2 es el resto de dividir x por 2.
Por ejemplo, los arreglos [0,5,2,1] y [0,17,0,3] son buenos,
y el arreglo [2,4,6,7] es malo, porque para i=1, las paridades de i y a[i] son diferentes:
i mod 2 = 1 mod 2 = 1, pero A[i] mod 2 = 4 mod 2 = 0.
En un solo movimiento, puedes tomar dos elementos cualesquiera del arreglo e intercambiarlos (estos elementos no son necesariamente adyacentes).
Encuentra el número mínimo de movimientos en los que puede hacer que el arreglo sea uno bueno, o decir que esto no es posible.
Un arreglo se considera BUENO si la paridad de cada índice coincide con la paridad del elemento en ese índice. De manera más formal, un arreglo es BUENO si para todos los i (0≤i≤n−1) se mantiene la igualdad:
i mod 2 = A[i] mod 2
donde x mod 2 es el resto de dividir x por 2.
Por ejemplo, los arreglos [0,5,2,1] y [0,17,0,3] son buenos,
y el arreglo [2,4,6,7] es malo, porque para i=1, las paridades de i y a[i] son diferentes:
i mod 2 = 1 mod 2 = 1, pero A[i] mod 2 = 4 mod 2 = 0.
En un solo movimiento, puedes tomar dos elementos cualesquiera del arreglo e intercambiarlos (estos elementos no son necesariamente adyacentes).
Encuentra el número mínimo de movimientos en los que puede hacer que el arreglo sea uno bueno, o decir que esto no es posible.
Entrada
La primera línea contiene un único número entero K (1≤K≤1000) — el número de casos de prueba en la prueba.
A continuación se presentan K líneas que corresponden a los casos de prueba. Cada caso de prueba comienza con una línea que contiene un número entero N (1≤N≤40) - la longitud del arreglo A.
La siguiente línea contiene N enteros A0,A1,…,An−1 (0≤Ai≤1000) - el arreglo inicial.
A continuación se presentan K líneas que corresponden a los casos de prueba. Cada caso de prueba comienza con una línea que contiene un número entero N (1≤N≤40) - la longitud del arreglo A.
La siguiente línea contiene N enteros A0,A1,…,An−1 (0≤Ai≤1000) - el arreglo inicial.
Salida
Para cada caso de prueba, escribe un único número entero: el número mínimo de movimientos para hacer que el arreglo dado sea uno BUENO, o -1 si esto no es posible.
Ejemplo Entrada
2 4 3 2 7 6 3 3 2 6
Ejemplo Salida
2 1
Ayuda
En el caso de prueba, en el primer movimiento, puedes intercambiar los elementos con índices 0 y 1, y en el segundo movimiento, puedes intercambiar los elementos con índices 2 y 3.