Shell Game.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

Para pasar el tiempo, a Bessie la vaca y a su amiga Elsie les gusta jugar una versión de un juego que ellas vieron en la feria del condado.

Para comenzar, Bessie pone tres cajas invertidas en una mesa y pone una piedra pequeña redonda debajo de una de ellas (al menos ella piensa que es un piedra - ella encontró el objeto en el piso de uno de los pastizales). Bessie entonces procede a intercambiar pares de cajas, mientras que Elsie trata de adivinar la ubicación de la piedra.

La versión estándar del juego que las vacas vieron jugar en la feria del condado permitía que la jugadora viera la ubicación inicial de la piedra, y luego requería adivinar la ubicación final después que se completaran los intercambios.

Sin embargo, a las vacas les gusta jugar una versión donde Elsie no sabe la ubicación inicial de la piedra, y donde ella puede adivinar la ubicación de la piedra después de cada intercambio. Bessie, conociendo la respuesta correcta, le da a Elsie un puntaje al final del juego igual al número de adivinaciones correctas que ella haya hecho.

Dados los intercambios y las adivinaciones, pero no la ubicación inicial de la piedra, por favor determine el puntaje más alto que Elsie podría haber ganado.

Entrada

La primera línea de la entrada contiene un entero N (1 \leq N \leq 100) dando el número de intercambios. Cada una de las siguientes N líneas describe un paso del juego y contiene tres enteros a, b, y q, indicando que las cajas a y b son intercambiadas por Bessie, y que Elsie adivinó la caja q después que el intercambio fue hecho. Todos estos tres enteros son 1, 2, ó 3, y a \neq b.

Salida

Por favor dé como salida el número máximo de puntos que Elsie podría haber ganado.

Ejemplo de Entrada

3
1 2 1
3 2 1
1 3 1

Ejemplo de Salida

2

En este ejemplo, Elsie podría haber ganado a lo más 2 puntos. Si la piedra comenzó debajo de la caja 1, entonces ella habría adivinado exactamente una vez (su adivinación final). Si la piedra comenzó debajo de la caja 2, ellas habría adivinado correctamente dos veces (las dos primeras adivinaciones). Si la piedra comenzó en la caja 3, ella no tendría ninguna adivinación correcta.

USACO 2019 January Contest, Bronze. Problem 1. Shell Game.


Comments

There are no comments at the moment.