Skip to Content
CTRL K

MIN-MEX Cut

Editorial oficial 

Explicación

Como el MEX es a lo sumo 2 cuando hay una subcadena que contiene un 0 y un 1, solo hay 3 casos posibles. Si no hay ceros, entonces el MEX es 0, ya que a todas las subcadenas les faltaría un 0. Si todos los ceros son adyacentes entre sí, podemos cortar la secuencia entera, dejando un MEX de 1. Los demás grupos, formados solo por unos, tendrían un MEX de 0. Dejando la respuesta como max(0,1)=1max(0, 1) = 1. Por último, si hay ceros y no son adyacentes entre sí, entonces debe existir una subcadena como 0,1{0, 1}, lo que da un MEX de 2.

Implementación

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

#include <algorithm>
#include <iostream>
using namespace std;
 
 
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		string s;
		cin >> s;
		// hallamos el número de ceros
		int zeros = count(s.begin(), s.end(), '0');
 
		if (zeros == 0) {
			cout << 0 << endl;  // no hay ceros, la respuesta es 0
		} else {
			// primera y última ocurrencias de un cero
			int l = s.find('0');
			int r = s.rfind('0');
			// si todos son adyacentes entre sí
			cout << ((r - l + 1 == zeros) ? 1 : 2) << endl;
		}
	}
}
import java.io.*;
 
public class MinMexCut {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(read.readLine());
		for (int i = 0; i < t; i++) {
			String s = read.readLine();
			// hallamos el número de ceros
			int zeros = s.length() - s.replace("0", "").length();
 
			if (zeros == 0) {
				System.out.println(0);  // no hay ceros, la respuesta es 0
			} else {
				// primera y última ocurrencias de un cero
				int l = s.indexOf('0');
				int r = s.lastIndexOf('0');
				// si todos son adyacentes entre sí
				System.out.println((r - l + 1 == zeros) ? 1 : 2);
			}
		}
	}
}
for _ in range(int(input())):
	s = input()
	# hallamos el número de ceros
	zeros = s.count("0")
 
	if zeros == 0:
		print(0)  # no hay ceros, la respuesta es 0
	else:
		# primera y última ocurrencias de un cero
		l = s.find("0")
		r = s.rfind("0")
		# si todos son adyacentes entre sí
		print(1 if r - l + 1 == zeros else 2)
Fundamentos