Simulación

Recursos
Fuente	Recurso	Notas
IUSACO	5 - Simulation	Este módulo se basa en el capítulo 5 del libro de Darren Yao

Como no hay un algoritmo formal de por medio, la intención del problema es evaluar la competencia con el lenguaje de programación elegido y el conocimiento de las estructuras de datos incorporadas. Al menos en USACO Bronce, cuando el enunciado pide el resultado final de algún proceso, o cuándo ocurre algo, suele bastar con simular el proceso de forma naive^{En programación
competitiva, «naive» se refiere a las soluciones más intuitivas o directas, y
la palabra no tiene la connotación negativa habitual. De hecho, una solución naive
puede no ser la más fácil de implementar.}.

Ejemplo 1

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Bronze	Shell Game	Fácil	Simulation	en el módulo

Solución

Podemos simular el proceso. Guardamos un arreglo que indica qué cáscara está en cada posición, y los intercambios de Bessie se simulan intercambiando elementos del arreglo. Luego contamos cuántas veces Elsie adivina cada cáscara, y el máximo de puntos que puede obtener es la cantidad máxima de veces que se adivina una misma cáscara.

C++JavaPython


#include <algorithm>
#include <cstdio>
#include <vector>
 
using std::vector;
 
int main() {
	freopen("shell.in", "r", stdin);
 
	int n;
	scanf("%d", &n);
 
	// shell_at_pos[i] guarda la etiqueta de la cáscara en la posición i
	vector<int> shell_at_pos(3);
	// Colocar las cáscaras de forma arbitraria
	for (int i = 0; i < 3; i++) { shell_at_pos[i] = i; }
 
	// counter[i] guarda cuántas veces se eligió la cáscara con etiqueta i
	vector<int> counter(3);
	for (int i = 0; i < n; i++) {
		int a, b, g;
		scanf("%d %d %d", &a, &b, &g);
		// Indexación desde cero: restar 1 a todas las posiciones
		a--, b--, g--;
 
		// Realizar el intercambio de Bessie
		std::swap(shell_at_pos[a], shell_at_pos[b]);
		// Contar cuántas veces Elsie adivina cada cáscara
		counter[shell_at_pos[g]]++;
	}
 
	freopen("shell.out", "w", stdout);
	printf("%d\n", std::max({counter[0], counter[1], counter[2]}));
}


import java.io.*;
import java.util.*;
 
public class Shell {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("shell");
 
		int n = io.nextInt();
 
		// shellAtPos[i] guarda la etiqueta de la cáscara en la posición i
		int[] shellAtPos = new int[3];
 
		// Colocar las cáscaras de forma arbitraria
		for (int i = 0; i < 3; i++) { shellAtPos[i] = i; }
 
		// counter[i] guarda cuántas veces se eligió la cáscara con
		// etiqueta i
		int[] counter = new int[3];
 
		for (int i = 0; i < n; i++) {
			// Indexación desde cero: restar 1 a todas las posiciones
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			int g = io.nextInt() - 1;
 
			// Realizar el intercambio de Bessie
			int temp = shellAtPos[b];
			shellAtPos[b] = shellAtPos[a];
			shellAtPos[a] = temp;
 
			// Contar cuántas veces Elsie adivina cada cáscara
			counter[shellAtPos[g]]++;
		}
 
		io.println(Math.max(counter[0], Math.max(counter[1], counter[2])));
		io.close();
	}
 
	// CodeSnip{Kattio}
}


read = open("shell.in")
 
n = int(read.readline())
 
# shell_at_pos[i] guarda la etiqueta de la cáscara en la posición i
# Las cáscaras se pueden colocar de forma arbitraria al inicio.
shell_at_pos = [i for i in range(3)]
 
# counter[i] guarda cuántas veces se eligió la cáscara con etiqueta i
counter = [0 for _ in range(3)]
 
for _ in range(n):
	# Indexación desde cero: restar 1 a todas las posiciones
	a, b, g = [int(i) - 1 for i in read.readline().split()]
 
	# Realizar el intercambio de Bessie
	shell_at_pos[a], shell_at_pos[b] = shell_at_pos[b], shell_at_pos[a]
 
	# Contar cuántas veces Elsie adivina cada cáscara
	counter[shell_at_pos[g]] += 1
 
print(max(counter), file=open("shell.out", "w"))

Ejemplo 2

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Bronze	Mixing Milk	Fácil	Simulation	en el módulo

Solución

Podemos simular el proceso de verter entre baldes. La cantidad de leche que se vierte del balde $i$ al balde $j$ es el mínimo entre la cantidad de leche en el balde $i$ (que es $m_i$ ) y el espacio restante en el balde $j$ (que es $c_j - m_j$ ). Basta con procesar todas estas operaciones en orden, usando un arreglo $c$ para las capacidades máximas de cada balde y un arreglo $m$ para el nivel actual de leche en cada balde, que actualizamos durante el proceso. El código de ejemplo está más abajo.

C++JavaPython


#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 3;  // La cantidad de baldes (que es 3)
const int TURN_NUM = 100;
 
int main() {
	freopen("mixmilk.in", "r", stdin);
 
	// capacity[i] es la capacidad máxima del balde i
	vector<int> capacity(N);
	// milk[i] es la cantidad actual de leche en el balde i
	vector<int> milk(N);
	for (int i = 0; i < N; i++) { scanf("%d %d", &capacity[i], &milk[i]); }
 
	for (int i = 0; i < TURN_NUM; i++) {
		int bucket1 = i % N;
		int bucket2 = (i + 1) % N;
 
		/*
		 * La cantidad de leche a verter es el mínimo entre la leche restante
		 * en el balde 1 y la capacidad disponible del balde 2
		 */
		int amt = min(milk[bucket1], capacity[bucket2] - milk[bucket2]);
 
		milk[bucket1] -= amt;
		milk[bucket2] += amt;
	}
 
	freopen("mixmilk.out", "w", stdout);
	for (int m : milk) { cout << m << '\n'; }
}


import java.io.*;
import java.util.*;
 
public class MixMilk {
	static final int N = 3;  // La cantidad de baldes (que es 3)
	static final int TURN_NUM = 100;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("mixmilk");
 
		// capacity[i] es la capacidad máxima del balde i
		int[] capacity = new int[N];
		// milk[i] es la cantidad actual de leche en el balde i
		int[] milk = new int[N];
 
		for (int i = 0; i < N; i++) {
			capacity[i] = io.nextInt();
			milk[i] = io.nextInt();
		}
 
		for (int i = 0; i < TURN_NUM; i++) {
			int bucket1 = i % N;
			int bucket2 = (i + 1) % N;
 
			/*
			 * La cantidad de leche a verter es el mínimo entre la leche restante
			 * en el balde 1 y la capacidad disponible del balde 2
			 */
			int amt = Math.min(milk[bucket1], capacity[bucket2] - milk[bucket2]);
 
			milk[bucket1] -= amt;
			milk[bucket2] += amt;
		}
 
		for (int m : milk) { io.println(m); }
		io.close();
	}
 
	// CodeSnip{Kattio}
}


N = 3  # La cantidad de baldes (que es 3)
TURN_NUM = 100
 
# capacity[i] es la capacidad máxima del balde i
capacity = [0 for _ in range(N)]
# milk[i] es la cantidad actual de leche en el balde i
milk = [0 for _ in range(N)]
with open("mixmilk.in") as read:
	for i in range(N):
		capacity[i], milk[i] = map(int, read.readline().split())
 
for i in range(TURN_NUM):
	bucket1 = i % N
	bucket2 = (i + 1) % N
 
	"""
	La cantidad de leche a verter es el mínimo entre la leche restante
	en el balde 1 y la capacidad disponible del balde 2
	"""
	amt = min(milk[bucket1], capacity[bucket2] - milk[bucket2])
 
	milk[bucket1] -= amt
	milk[bucket2] += amt
 
with open("mixmilk.out", "w") as out:
	for m in milk:
		print(m, file=out)

Problemas

Más fáciles

Fuente	Nombre	Dificultad	Tags	Solución
Bronze	The Cow-Signal	Fácil	Simulation	Solución
Bronze	★ Speeding Ticket	Fácil	Simulation	Solución
Bronze	The Lost Cow	Fácil	Simulation	Solución
Bronze	The Bovine Shuffle	Fácil	Simulation	Solución
Bronze	The Bucket List	Fácil	Simulation	Solución

Más difíciles

Fuente	Nombre	Dificultad	Tags	Solución
Bronze	Measuring Traffic	Normal	Simulation	Solución
Bronze	Circular Barn	Normal	Simulation	Solución
Bronze	★ Block Game	Normal	Simulation	Solución
Bronze	Team Tic Tac Toe	Normal	Simulation	Solución
Bronze	Mowing the Field	Normal	Simulation	Solución
Bronze	Reflection	Normal	Simulation	Solución
Old Bronze	Censoring	Difícil	Simulation	Solución
Bronze	Milk Measurement	Difícil	Simulation	Solución
Bronze	Stuck in a Rut	Muy difícil	Simulation	Solución