Vacas Cenadoras
Las vacas son muy necias acerca de sus compañeras de comida. Ellas se han organizado en dos grupos (convenientemente numerados y ) que insisten en comer juntas con el grupo al inicio de la fila y el grupo al final. El problema comienza cuando ellas se alinean en el establo para entrar al área de alimentación.
Cada vaca lleva con ella una pequeña tarjeta en la cual está grabado indicando su pertenencia a un grupo alimenticio. Todo el conjunto de 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 o 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, o ).
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: .
• Líneas 2…N+1: La línea describe la preferencia alimentaria de la vaca con un solo entero: .
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