Pretorneo de las Ciudades - Nivel Juvenil - Problema 3
Este problema en el Archivo de Enunciados:
• Archivo de Enunciados • Competencias de Argentina • Pretorneo de las Ciudades • Única Ronda 2020 • Nivel Juvenil-
Turko Arias
- Mensajes: 591
- Registrado: Lun 28 Nov, 2011 11:39 am
- Medallas: 17
- Nivel: Ñandú
- Ubicación: La Plata, Provincia de Buenos Aires
Pretorneo de las Ciudades - Nivel Juvenil - Problema 3
Se tienen $100$ fichas, numeradas de $1$ a $100$, en una fila. Hay dos movidas lícitas:
Intercambiar dos fichas adyacentes (que estén una al lado de la otra), que cuesta un dólar.
Intercambiar dos fichas que tienen exactamente $3$ fichas entre medio, que es gratis.
Determinar la menor cantidad de dólares necesaria para reordenar las $100$ fichas en el orden inverso al que tenían al comienzo.
Intercambiar dos fichas adyacentes (que estén una al lado de la otra), que cuesta un dólar.
Intercambiar dos fichas que tienen exactamente $3$ fichas entre medio, que es gratis.
Determinar la menor cantidad de dólares necesaria para reordenar las $100$ fichas en el orden inverso al que tenían al comienzo.
Fundamentalista del Aire Acondicionado
Y todo el orgullo de ser bien bilardista
Y todo el orgullo de ser bien bilardista
-
- Mensajes: 35
- Registrado: Dom 23 Jun, 2019 7:45 pm
- Medallas: 1
- Nivel: 2
Re: Pretorneo de las Ciudades - Nivel Juvenil - Problema 3
Simplifiqué el problema, junto con la idea de maximizar los intercambios con 3 intermedios, y sólo usar el intercambio adyacente para lograr llegar al otro extremo. Empezando por el uno, luego con el dos y así sucesivamente, una vez que se llega a la mitad la otra mitad se ordena automáticamente.
Luego si el procedimiento se aplica a 100 no varía el costo por mover a uno por dolar cada número, siendo sólo necesario movilizar la mitad de los números, por tanto se necesitan 50 dolares como mínimo. Adjunto imagen donde los que están en color verdes son movimientos gratis a futuro, y los amarillos los de costo 1 dolar.
Luego si el procedimiento se aplica a 100 no varía el costo por mover a uno por dolar cada número, siendo sólo necesario movilizar la mitad de los números, por tanto se necesitan 50 dolares como mínimo. Adjunto imagen donde los que están en color verdes son movimientos gratis a futuro, y los amarillos los de costo 1 dolar.