Cowntact Tracing

#include <bits/stdc++.h>
using namespace std;
 
void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
struct Shake {
	int t, x, y;
	bool operator<(const Shake &tmp) { return t < tmp.t; }
};
 
int main() {
	setIO("tracing");
 
	int n, t;
	string s;
	cin >> n >> t >> s;
 
	vector<Shake> shakes(t);
	vector<bool> cows_infected(n);
	unordered_set<int> possible_patient;
	int min_k = t, max_k = -1;
 
	// comprueba si el par {patient_zero, k} es consistente con los datos de apretones
	// a lo largo del tiempo
	auto is_consistent = [&](int patient_zero, int k) {
		vector<bool> tmp_infected(n);
		vector<int> num_shakes(n);
		tmp_infected[patient_zero] = true;
		for (Shake sh : shakes) {
			if (tmp_infected[sh.x]) { num_shakes[sh.x]++; }
			if (tmp_infected[sh.y]) { num_shakes[sh.y]++; }
			if (num_shakes[sh.x] <= k && tmp_infected[sh.x]) {
				tmp_infected[sh.y] = true;
			}
			if (num_shakes[sh.y] <= k && tmp_infected[sh.y]) {
				tmp_infected[sh.x] = true;
			}
		}
		for (int i = 0; i < n; i++) {
			if (tmp_infected[i] != cows_infected[i]) { return false; }
		}
		return true;
	};
 
	// marcamos las vacas infectadas
	for (int i = 0; i < n; i++) { cows_infected[i] = (s[i] == '1'); }
 
	// tomamos los datos de apretones y los ordenamos por tiempo
	for (Shake &sh : shakes) {
		cin >> sh.t >> sh.x >> sh.y;
		sh.t--, sh.x--, sh.y--;
	}
	sort(shakes.begin(), shakes.end());
 
	// comprobamos cada par posible si es consistente o no y construimos los resultados
	for (int patient_zero = 0; patient_zero < n; patient_zero++) {
		for (int k = 0; k <= t; k++) {
			if (is_consistent(patient_zero, k)) {
				possible_patient.insert(patient_zero);
				min_k = min(min_k, k);
				max_k = max(max_k, k);
			}
		}
	}
 
	cout << possible_patient.size() << " " << min_k << " "
	     << (max_k == t ? "Infinity" : to_string(max_k)) << endl;
}

import sys
 
sys.stdin = open("tracing.in", "r")
sys.stdout = open("tracing.out", "w")
 
n, t = map(int, input().split())
 
infected = [int(i) for i in input().strip()]
shakes = []
 
for _ in range(t):
	shakes.append(list(map(int, input().split())))
 
# ordenamos por el primer elemento (tiempo)
shakes.sort()
 
ans_mink = float("inf")
ans_maxk = -float("inf")
num_possible = 0
 
 
def simulate(cow_zero):
	mink = float("inf")
	maxk = -float("inf")
	for k in range(251):
		cur_infected = [False] * n
		cur_infected[cow_zero] = True
		time = [0] * n
		for i in range(len(shakes)):
			# Restamos uno para un índice indexado desde cero.
			cow1, cow2 = shakes[i][1] - 1, shakes[i][2] - 1
 
			# Si alguna de las dos vacas está infectada, aumentamos su tiempo infectada en 1
			if cur_infected[cow1]:
				time[cow1] += 1
			if cur_infected[cow2]:
				time[cow2] += 1
 
			# cow1 infecta a cow2
			if cur_infected[cow1] and not cur_infected[cow2] and time[cow1] <= k:
				cur_infected[cow2] = True
 
			# cow2 infecta a cow1
			if cur_infected[cow2] and not cur_infected[cow1] and time[cow2] <= k:
				cur_infected[cow1] = True
		"""
		¿El arreglo resultante de vacas infectadas es igual al
		que se nos dio?
		"""
		if infected == cur_infected:
			mink = min(mink, k)
			maxk = max(maxk, k)
	return [mink, maxk]
 
 
for i in range(len(infected)):
	"""
	Como las vacas infectadas siguen infectadas, solo las vacas infectadas pueden
	calificar como "vaca cero"
	"""
	if infected[i]:
		result = simulate(i)
		# Al menos un valor de K funcionó.
		if result[0] != float("inf"):
			ans_mink = min(ans_mink, result[0])
			ans_maxk = max(ans_maxk, result[1])
			num_possible += 1
 
# Funcionó para todos los valores posibles de K.
if ans_maxk == 250:
	ans_maxk = "Infinity"
 
print(num_possible, ans_mink, ans_maxk)

import java.io.*;
import java.util.*;
 
public class CowntactTracing {
	static boolean[] cowEndsInfected;
	static int n;
	static int maxT = 250;
	static int maxN = 100;
	static int[] cowX = new int[maxT + 1];
	static int[] cowY = new int[maxT + 1];
 
	// esta función simula los apretones de mano a lo largo del tiempo para ver si los datos
	// coinciden con esta elección de patient_zero y K
	static boolean consistentWithData(int patientZero, int k) {
		boolean[] infected = new boolean[maxN + 1];
		int[] numHandshakes = new int[maxN + 1];
 
		infected[patientZero] = true;
 
		for (int t = 0; t <= maxT; t++) {
			int x = cowX[t];
			int y = cowY[t];
 
			if (x > 0) {
				if (infected[x]) { numHandshakes[x]++; }
				if (infected[y]) { numHandshakes[y]++; }
				if (numHandshakes[x] <= k && infected[x]) { infected[y] = true; }
				if (numHandshakes[y] <= k && infected[y]) { infected[x] = true; }
			}
		}
 
		for (int i = 1; i <= n; i++) {
			if (infected[i] != cowEndsInfected[i]) { return false; }
		}
 
		return true;  // devolvemos true al final
	}
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("tracing");
 
		n = io.nextInt();
		int T = io.nextInt();
		String s = io.next();
 
		cowEndsInfected = new boolean[n + 1];
 
		for (int x = 1; x <= n; x++) {
			cowEndsInfected[x] =
			    (s.charAt(x - 1) == '1');  // marcamos las vacas infectadas como true
		}
 
		for (int i = 0; i < T; i++) {  // leemos la entrada y la guardamos en el arreglo
			int t = io.nextInt();
			cowX[t] = io.nextInt();
			cowY[t] = io.nextInt();
		}
 
		boolean[] possibleI = new boolean[maxN + 1];
		boolean[] possibleK = new boolean[maxT + 2];
 
		for (int i = 1; i <= n; i++) {  // recorremos cada par
			for (int k = 0; k <= 251; k++) {
				if (consistentWithData(i, k)) {
					possibleI[i] = true;
					possibleK[k] = true;
				}
			}
		}
 
		int lowerK = maxT + 1;
		int upperK = 0;
		int numPatientZero = 0;
 
		for (int k = 0; k <= maxT + 1; k++) {
			if (possibleK[k]) { upperK = k; }
		}
 
		for (int k = maxT + 1; k >= 0; k--) {
			if (possibleK[k]) { lowerK = k; }
		}
 
		for (int i = 0; i <= n; i++) {  // contamos el número de pacientes cero
			if (possibleI[i]) { numPatientZero++; }
		}
 
		io.print(numPatientZero + " " + lowerK +
		         " ");  // pacientes cero posibles, mínimo de K
		if (upperK == maxT + 1) {
			io.println("Infinity");  // infinity si K = T es posible
		} else {
			io.println(upperK);
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}