Programacion, ACM ICPC, UVa Online Judge

El link del problema es el siguiente:
120 – Stacks of Flapjacks

El problema es de Ordenamiento.
Lo que nos piden es, dada una torre de panques desordenada, ordenarla de mayor a menor, pero con una forma peculiar de ordenar.

La forma del ordenamiento consiste en colocar la espátula en una posición y girar todos los panques que se encuentren desde ese punto hasta la cima de la torre y voltear todos los panques.
En el problema no especifica un método optimo para resolver el problema, así que una de las maneras mas fácil de resolver el problema es dividirlo en 2 casos bases:

  • El panque mas grande que no este ordenado, no se encuentra hasta arriba
  • El panque mas grande que no este ordenado, se encuentra hasta arriba

Como podrán notar, al usar esos 2 casos bases, nos daremos cuenta que para ordenar cualquier panque a lo mas se necesitan 2 movimientos, colocarlo hasta arriba y voltear luego al nivel que corresponda.
Ejemplo:

Entrada:
1 2 3 5 4
Salida
2 1 2 3 0

Los movimientos para obtener la salida se pueden interpretar de la siguiente manera:
1                  5                 4                 3                 1
2  flip(2)       3   flip(1)     1   flip(2)     2   flip(3)     2
3  ——>      2   ——>     2   ——>    1   ——>    3
5                  1                 3                 4                 4
4                  4                 5                 5                 5

Si se dan cuenta, se coloca siempre el mas grande y después se voltean y se coloca en su posición correspondiente.
Hay que aclarar que hay que copiar los elementos y ordenarlos para saber que elemento no esta en su lugar.

Código en C++

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: