Esta sesión presenta el tipo list de Python que implementa listas indexadas de tamaño dinámico y cuyo contenido puede cambiar (es decir, son mutables). También presenta el tipo tuple que implementa una colección lineal de valores, indexada, pero inmutable. Una ventaja de las listas de Python es que automáticamente ofrecen una implementación del tipo abstracto de datos pila (en inglés stack), una estructura de datos lineal lifo (del inglés last-in first-out). Usando el módulo deque, Python ofrece colas (en inglés queue), una estructura de datos lineal fifo (del inglés first-in first-out). A modo de ejemplo, un provedor de una pistola es lifo mientras que una cola de banco (donde no hay colados ni preferidos) es fifo. Esta sesión también usa una de las características más llamativas de Python: la posibilidad de definir listas por comprensión.
El problema se encuentra en la arena de programación competitiva UVa y es el siguiente:
Este problema puede ser formalizado de la siguiente manera:
b[0..n) con una permutación del conjunto {1,2,..., n}, con n>01,2,..,n como b.La notación b[0..n) la usamos para indicar que b es una variable que corresponde a una lista de n elementos indexada desde 0 hasta n-1 (es decir, el primer elemento es b[0] y el último elemento es b[n-1]).
La estrategia de solución es hacer una simulación de la situación descrita en el problema. Identificamos los siguientes tres elementos como parte de la solución:
a (note que esta lista corresponde a los valores 1,2,...,n en ese orden)station; dado que el comportamiento de la estación es lifo, esta lista en realidad será una pilabLa simulación entonces consiste en mover, uno por uno, los trenes de A a la estación. Cada vez que un tren sea ubicado en la estación (recuerden que es una pila), trataremos de moverlo a B. Si el movimiento es posible (es decir, si el tope de la pila es igual al elemento que se espera en b), entonces lo movemos y hacemos lo mismo con cada uno de los elementos al tope de la pila hasta que sea imposible (es decir, cuando la pila sea vacía o su tope no coincida con el siguiente elemento esperado en b). Dado que hemos todos los movimientos posibles cada vez que se mueve un tren de A a la estación, cuando no haya más trenes en A una de dos cosas sucederá: o la estación está vacía o tiene al menos un tren. Si la estación está vacía, entonces fue posible ordenar los trenes como deseábamos; de lo contrario no.
En Python, la estructura de datos lineal por defecto son las listas y no los arreglos. Comúnmente, los arreglos son tipos de datos básicos en cualquier lenguaje de programación: permiten almacenar una colección arbitraria de valores, es decir, se comportan como una variable multidimensional (o como un vector en álgebra lineal en un espacio de dimensión arbitraria). Para aquellas personas que alguna vez han programado, no contar con arreglos como un tipo básico suena algo raro. Sin embargo, como veremos en esta sesión, las listas en Python puede usarse como arreglos y, además, su tamaño es dinámico (en contraste con los arreglos que son de tamaño fijo), lo cual es una ventaja.
split en la sección 4.7.1 de The Python Standard Library para familiarizarse con la tokenización de cadenas.deque.En el modo interactivo de Python, siempre es posible consultar la documentación de los módulos o clases disponibles en el ambiente. Esto se hace ejecutando el comando help(...) con parámetro correspondiente al nombre del módulo o clase de interés. Por ejemplo, para averigüar sobre la documentación del tipo list, basta con ejecutar el siguiente comando en la consola de Python:
>>> help(list)Help on class list in module builtins:class list(object) | list() -> new empty list | list(iterable) -> new list initialized from iterable's items | | Methods defined here:...Al igual que con la sesión 1, primero nos ocupamos de cómo capturar los datos de la entrada estándar y cómo los imprimimos a la salida estándar. Es justo decir que la entrada de este problema tiene un formato más elaborada que la del problema anterior.
El algoritmo para leer los datos de entrdada es el siguiente:
n la cantidad vagones del caso de prueban sea diferente de 0, es decir, mientras no lleguemos al fin de los casos de pruebaa con los valores a=(1,2,...,n)l la lista de valores del siguiente renglón (esto lo hacemos tokenizando por espacios la línea de texto leída)l no es la cadena '0' es decir, mientras no se acaben las posibles permutaciones sobre las que se quiere averigüarl en ba y b usando la función solve y se imprime de acuerdo al enunciadol la lista de valores del siguiente renglón (como en 2.2)n la cantidad vagones del caso de prueba (igual que en 1)Dado que a es una tupla, estamos optando por no modificar nunca el valor del contenido de a. Por el gusto de variar, usaremos a y b como variables globales. Esto nos permite llamar la función solve sin parámetros. Dado que se debe imprimir una línea en blanco entre cada bloque de casos de prueba, se usa una variable Booleana first (es decir, first es una variable cuyos valores son True o False) para determinar si el bloque actual es el primero o no. Si no es el primero, entonces se imprime una línea en blanco; esta variable inicialmente vale True y es asignada el valor False en cada iteración del ciclo.
El código resultante para leer e imprimir es el siguiente:
from sys import stdina,b = None,Nonedef solve(): global a, b ...def main(): global a, b n = int(stdin.readline()) first = True while n!=0: if not(first): print() first = False l = stdin.readline().strip().split() a = tuple(i+1 for i in range(n)) while l[0]!='0': b = [ int(x) for x in l ] if solve(): print('Yes') else: print('No') l = stdin.readline().strip().split() n = int(stdin.readline())main()A mode de sugerencia, no avance de este punto hasta no entender la función main. Recuerde que algunos casos de prueba están en archivos al final de la página. De ser necesario, anote el código con instrucciones print para entender paso a paso cómo se ejecuta.
La solución algorítmica del problema está en la función solve. Además de las variables globales a y b, y de la pila station hay una variable entera idxb. Esta última variable será un índice sobre la lista b. El problema se resuelve en un ciclo de acuerdo con la estrategia descrita inicialmente. Inicialmente idxb es 0 y el ciclo cumple con el siguiente invariante:
ha sido posible organizar los trenes en orden b[0], b[1], ..., b[idxb-1]
Nótese que una vez terminen todas las iteraciones, si idxb es igual a n (es decir, al tamaño de a), entonces se han podido ordenar todos los vagones del tren; de lo contrario no. Esto es equivalente a decir que la estación esté vacía o no, dado que todos los vagones en A pasan a la estación y de la estación a B.
El código resultante para la función solve es el siguiente:
def solve(): global a, b station, idxb = list(),0 for t in a: station.append(t) while len(station)>0 and station[-1]==b[idxb]: station.pop() idxb += 1 return idxb==len(a) mario_test1.in y mario_test1.out para validar su implementación.a corresponde a una estructura de datos lineal, en particular, corresponde a una tupla. Sin embargo, para resolver el problema, basta con que a sea una variable de número entero. Modifique la solución del problema presentado en esta sección para que la variable a sea un número entero y no una estructura de datos lineal. Para validar su solución use los archivos rails_test1.in y rails_test1.out.patience_test1.in y patience_test1.out.cards_test1.in y cards_test1.out.