Vacas Cenadoras


Submit solution

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

Author:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Las vacas son muy necias acerca de sus compañeras de comida. Ellas se han organizado en dos grupos (convenientemente numerados 1 y 2) que insisten en comer juntas con el grupo 1 al inicio de la fila y el grupo 2 al final. El problema comienza cuando ellas se alinean en el establo para entrar al área de alimentación.

Cada vaca i lleva con ella una pequeña tarjeta en la cual está grabado D_i (1 \leq D_i \leq 2) indicando su pertenencia a un grupo alimenticio. Todo el conjunto de N (1 \leq N \leq 30 000) vacas se ha alineado para la comida pero es fácil para cualquiera ver que ellas no están agrupadas según sus tarjetas de grupo alimenticio.

El trabajo de GJ no es tan difícil. El simplemente recorre la línea de vacas cambiando su asignación de grupo alimenticio tachando el número antiguo y escribiendo uno nuevo. Haciendo eso, él crea grupos de vacas como 1112222 o 111122 en los que los grupos alimenticios de las vacas están ordenados ascendentemente. En pocas ocasiones, él podría cambiar las tarjetas de tal manera que solamente quede un grupo de vacas (por ejemplo, 1111 o 222).

GJ es tan perezoso como el vecino. El está curioso: ¿cuál es el número mínimo absoluto de tarjetas que él debe cambiar para crear un grupo apropiado de socias alimentarias? El únicamente debe cambiar los números de las tarjetas y no debe reorganizar a las vacas en la fila.

Entrada

• Línea 1: Un solo entero: N.

• Líneas 2…N+1: La línea i+1 describe la preferencia alimentaria de la vaca i con un solo entero: D_i.

Ejemplo de Entrada

7
2
1
1
1
2
2
1

Detalles de la Entrada

Siete vacas; todas menos 3 prefieren el grupo alimentario 1.

Salida

• Línea 1: Un solo entero que es el número mínimo de tarjetas que el Granjero Juan debe cambiar para asignar las vacas a grupos alimentarios como se ha descrito.

Ejemplo de Salida

2

Detalles de la Salida

Cambie las tarjetas de la primera y última vaca.


Comments

There are no comments at the moment.