Solução Informática Inciante - Semana 57

Solução por Leonardo Paes

A observação mais importante é que:

Uma chave com id ímpar só pode ser usada para abrir um baú com id par.
Uma chave com id par só pode ser usada para abrir um baú com id ímpar.

Seja:

$c_{0}, c_{1}$
$k_{0}, k_{1}$ $c_{0}, c_{1}$ $c_{0}, c_{1}$

Com $c_{0}$ baús de id par e $k_{1}$ chaves de id ímpar, você pode destrancar no máximo $min(c_{0}, k_{1})$ baús.

Com $c_{1}$ baús de id ímpar e $k_{0}$ chaves de id par, você pode destrancar no máximo $min(c_{1}, k_{0})$ baús.

Então, a resposta final é $min(c_{0}, k_{1}) + min(c_{1}, k_{0})$ .

Complexidade: $\mathcal{O}(n+m)$ .

	#include <bits/stdc++.h>

	using namespace std;

	int main(){
	int n, m;

	cin >> n >> m;

	vector<int> a(n), b(m);

	for(int i = 0; i < n; ++i){
	cin >> a[i];
	}

	for(int i = 0; i < m; i++){
	cin >> b[i];
	}

	int c0 = 0, c1 = 0;

	for(int i = 0; i < n; i++){
	if (a[i]%2 == 0){
	c0++;
	}
	else{
	c1++;
	}
	}

	int k0 = 0, k1 = 0;

	for(int i = 0; i < m; i++){
	if (b[i]%2 == 0){
	k0++;
	}
	else{
	k1++;
	}
	}

	int ans = min(c1, k0) + min(c0, k1);

	cout << ans << endl;

	return 0;
	}

view raw

Você é Curioso?.cpp

hosted with ❤ by GitHub