Even More Odd Photos

Solución en video

Por Melody Yu

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int group(int O, int E) {
	int diff = O - E;
	if (diff == 0) {
		return O + E;
	} else if (diff == 1) {
		return O + E - 2;
	} else if (diff == 2) {
		return E + O - 1;
	} else {
		O -= 2;
		E += 1;
	}
 
	return group(O, E);
}
 
int main() {
	int N;
	cin >> N;
 
	int oddC = 0, evenC = 0;
	for (int i = 0; i < N; i++) {
		int cow;
		cin >> cow;
		if (cow % 2 == 0) {
			evenC += 1;
		} else {
			oddC += 1;
		}
	}
 
	if (evenC > oddC) {
		cout << 2 * oddC + 1;
	} else {
		cout << group(oddC, evenC);
	}
	return 0;
}


import java.io.*;
import java.util.*;
 
public class EvenMoreOddPhotos {
	public static int group(int O, int E) {
		int diff = O - E;
		if (diff == 0) {
			return O + E;
		} else if (diff == 1) {
			return O + E - 2;
		} else if (diff == 2) {
			return E + O - 1;
		} else {
			O -= 2;
			E += 1;
		}
 
		return group(O, E);
	}
 
	public static void main(String[] args) throws IOException {
		EvenMoreOddPhotos.Kattio io = new EvenMoreOddPhotos.Kattio();
		int N = io.nextInt();
		int oddC = 0, evenC = 0;
		for (int i = 0; i < N; i++) {
			int cow = io.nextInt();
			if (cow % 2 == 0) {
				evenC += 1;
			} else {
				oddC += 1;
			}
		}
 
		if (evenC > oddC) {
			io.println(2 * oddC + 1);
		} else {
			io.println(group(oddC, evenC));
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Pista 1

¿A FJ le importan los valores reales de las vacas?

Pista 2

¿Qué nos impide poner a cada vaca en su propio grupo y dar por terminado el problema?

Respuesta a la pista 2

Si hay demasiadas vacas pares, no habrá suficientes vacas impares para alternar entre las vacas pares, y viceversa.

Pista 3

¿Cómo deberíamos particionar las vacas si hay demasiadas vacas pares? ¿Y si hay demasiadas vacas impares?

Solución

Análisis oficial (C++)

Explicación

En el mejor escenario, cada vaca está en su propio grupo, y la respuesta es $N$ . ¿Cuándo ocurre esto?

Sea $O$ la cantidad de vacas impares y $E$ la cantidad de vacas pares de la lista inicialmente. Para que cada vaca esté en su propio grupo, debemos tener $E = O$ o $E = O + 1$ .

En caso contrario, algunos grupos deben contener más de una vaca. Ahora el problema se divide en dos casos.

Si $E \gt O + 1$ , entonces hay demasiadas vacas pares. Como dos números pares suman un par, podemos tomar una vaca par como primer grupo, luego una vaca impar como siguiente grupo, y repetir esto $O$ veces. Las vacas restantes son todas pares, así que ponerlas todas en un solo grupo grande no causa problemas. En este caso, la respuesta es $2O + 1$ .

En caso contrario, debemos tener $E < O$ , así que hay demasiadas vacas impares. Como dos números impares suman un par, podemos emparejar dos vacas impares, lo que equivale a tener dos vacas impares menos y una vaca par más. Repetimos este proceso de emparejar dos vacas impares hasta que $E \ge O$ , momento en el cual podemos usar la lógica del primer caso para calcular la respuesta.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

JavaPythonC++


import java.io.*;
import java.util.*;
 
public class OddPhotos {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int odd = 0;
		int even = 0;
		int n = Integer.parseInt(in.readLine());
 
		StringTokenizer cowST = new StringTokenizer(in.readLine());
		for (int i = 0; i < n; i++) {
			int cow = Integer.parseInt(cowST.nextToken());
			if (cow % 2 == 0) {
				even++;
			} else {
				odd++;
			}
		}
 
		// Emparejar vacas impares para que no haya demasiadas.
		while (odd > even) {
			odd = odd - 2;
			// Dos vacas impares juntas equivalen a una vaca par.
			even++;
		}
		// Agrupar vacas pares para que tampoco haya demasiadas pares.
		if (even > odd + 1) { even = odd + 1; }
 
		System.out.println(even + odd);
	}
}


n = int(input())
even, odd = 0, 0
 
cows = [int(i) for i in input().split()]
for c in cows:
	if c % 2 == 0:
		even += 1
	else:
		odd += 1
 
# Emparejar vacas impares para que no haya demasiadas.
while odd > even:
	odd -= 2
	# Dos vacas impares juntas equivalen a una vaca par.
	even += 1
 
# Agrupar vacas pares para que tampoco haya demasiadas pares.
if even > odd + 1:
	even = odd + 1
 
print(even + odd)


#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	int even = 0;
	int odd = 0;
	for (int i = 0; i < n; i++) {
		int cow;
		cin >> cow;
		if (cow % 2 == 0) {
			even++;
		} else {
			odd++;
		}
	}
 
	// Emparejar vacas impares para que no haya demasiadas.
	while (odd > even) {
		odd = odd - 2;
		// Dos vacas impares juntas equivalen a una vaca par.
		even++;
	}
	// Agrupar vacas pares para que tampoco haya demasiadas pares.
	if (even > odd + 1) { even = odd + 1; }
 
	cout << odd + even << endl;
}