Nacional 2012 P6 N2
Este problema en el Archivo de Enunciados:
• Archivo de Enunciados • Competencias de Argentina • Nacional • 2012 • Nivel 2Nacional 2012 P6 N2
Se tienen [math] fichas ubicadas en una fila. Una movida consiste en intercambiar dos fichas vecinas. Se deben realizar varias movidas de modo que cada ficha visite la primera y la última posición. ¿Cuál es el menor número de movidas necesarias para lograr esto?
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!
Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
You've seen how it works, now it's over to you (...)
For there's so much more to explore!
Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
-
Fran5
- Mensajes: 1125
- Registrado: Mié 21 Mar, 2012 1:57 pm
- Medallas: 22
- Nivel: Exolímpico
- Ubicación: Santa Fe
Re: Nacional 2012 P6 N2
Yo me acuerdo que en este problema me había dado una solución re flashera xD
Aunqe no me acuerde como lo hice exactamente, era algo asi
Aunqe no me acuerde como lo hice exactamente, era algo asi
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Re: Nacional 2012 P6 N2
Voy a explicar un poco mejor la cota que da Fran5, porque no está desarrollada dentro de la solución (el ejemplo sí está explicado).
Queremos ver que se necesitan al menos [math] movimientos para lograr lo pedido, y para ello contaremos la cantidad de movimientos mínima de cada ficha por separado. Luego, vamos a haber estado contando dos veces cada movimiento (una vez por cada ficha involucrada) por lo que deberemos dividir por 2 el resultado que obtengamos.
El movimiento de una ficha que inicialmente está en el lugar [math] se puede resumir como:
Si [math], se minimiza la cantidad de movimientos cuando primero va al borde con la primera posición y luego al borde con la [math]-ésima posición. Para hacer esos movimientos se requieren al menos [math] movimientos. Sumando todos los valores de [math] en este rango, tenemos que se realizaron al menos [math] movimientos (contaremos todos dos veces hasta el final de la explicación, y luego dividiremos por dos al final).
[math]
Si [math], se minimiza la cantidad de movimientos cuando primero va al borde con la [math]-ésima posición y luego al borde con la primera posición. Para hacer esos movimientos se requieren al menos [math] movimientos. Sumando todos los [math] en rango tenemos que se realizaron al menos [math] movimientos.
[math].
Ahora sumemos los dos resultados obtenidos en la división de casos, para así obtener una cota de la suma total de movimientos en las primeras dos secciones del camino de los [math].
[math]
Ahora sólo nos falta sumar las terceras secciones de los caminos de las fichas. Para ello, es conveniente no pensar en cada ficha individualmente sino pensar que la ficha que al final ocupa el lugar [math] (que no tiene que ser la que lo ocupaba al principio) tiene que haber hecho al menos [math] movimientos para llegar desde el borde más cercano a [math] hasta su posición final. Luego sumamos todo esto sobre los [math]: para los [math], el borde más cercano es el 1 y entonces se acota por [math]. Por el contrario, para los [math] el borde más cercano es el [math] y luego se acota por [math] movimientos.
Sumando sobre todos los [math] posiciones finales queda:
[math]
Así, finalmente sumamos el [math] obtenido de las dos primeras partes con el [math] de la tercera:
[math] movimientos como mínimo, pero recordemos que cada uno está contado dos veces (una vez por ficha).
Así, el menor número de movidas es [math].
Queremos ver que se necesitan al menos [math] movimientos para lograr lo pedido, y para ello contaremos la cantidad de movimientos mínima de cada ficha por separado. Luego, vamos a haber estado contando dos veces cada movimiento (una vez por cada ficha involucrada) por lo que deberemos dividir por 2 el resultado que obtengamos.
El movimiento de una ficha que inicialmente está en el lugar [math] se puede resumir como:
- Ir desde [math] a un borde para visitar uno de ellos.
- Ir desde ese borde al otro borde para recorrer todas las posiciones que faltan.
- Ir desde el otro borde a la posición final de la ficha.
Si [math], se minimiza la cantidad de movimientos cuando primero va al borde con la primera posición y luego al borde con la [math]-ésima posición. Para hacer esos movimientos se requieren al menos [math] movimientos. Sumando todos los valores de [math] en este rango, tenemos que se realizaron al menos [math] movimientos (contaremos todos dos veces hasta el final de la explicación, y luego dividiremos por dos al final).
[math]
Si [math], se minimiza la cantidad de movimientos cuando primero va al borde con la [math]-ésima posición y luego al borde con la primera posición. Para hacer esos movimientos se requieren al menos [math] movimientos. Sumando todos los [math] en rango tenemos que se realizaron al menos [math] movimientos.
[math].
Ahora sumemos los dos resultados obtenidos en la división de casos, para así obtener una cota de la suma total de movimientos en las primeras dos secciones del camino de los [math].
[math]
Ahora sólo nos falta sumar las terceras secciones de los caminos de las fichas. Para ello, es conveniente no pensar en cada ficha individualmente sino pensar que la ficha que al final ocupa el lugar [math] (que no tiene que ser la que lo ocupaba al principio) tiene que haber hecho al menos [math] movimientos para llegar desde el borde más cercano a [math] hasta su posición final. Luego sumamos todo esto sobre los [math]: para los [math], el borde más cercano es el 1 y entonces se acota por [math]. Por el contrario, para los [math] el borde más cercano es el [math] y luego se acota por [math] movimientos.
Sumando sobre todos los [math] posiciones finales queda:
[math]
Así, finalmente sumamos el [math] obtenido de las dos primeras partes con el [math] de la tercera:
[math] movimientos como mínimo, pero recordemos que cada uno está contado dos veces (una vez por ficha).
Así, el menor número de movidas es [math].
Re: Nacional 2012 P6 N2
Última edición por ¿hola? el Jue 21 Sep, 2017 11:58 am, editado 1 vez en total.
Yes, he who
-
Gianni De Rico
- Mensajes: 2222
- Registrado: Vie 16 Sep, 2016 6:58 pm
- Medallas: 19
- Nivel: Exolímpico
- Ubicación: Rosario
- Contactar:
Re: Nacional 2012 P6 N2
Che, le pifiaste un signo al final¿hola? escribió:
♪♫ do re mi función lineal ♪♫