Shuffler P57352

Dispones de dos pilas no vacías de cartas, de las cuales conoces los números y el orden en que aparecen. Tu robot debe mezclar las cartas: a cada paso, escogerá una carta de una de las dos pilas, y la apilará en la pila resultado. Tu objetivo es ordenar las cartas tanto como te sea posible. En concreto, se desea minimizar la suma de los cuadrados de la diferencia entre los valores de cartas consecutivas tales que la carta de debajo sea mayor que la carta de arriba. En este problema representaremos las pilas de cartas por secuencias de números, apiladas de izquierda (cima) a derecha (base). Por ejemplo, la primera carta que se podría extraer de la pila

es el 2; además, esta pila tiene tres pares de cartas desordenadas, el 10-8, el 8-7, y el 11-5, que dan lugar al “valor de desorden” 2²+1²+6²=41.

Escribe un programa que, a partir de las dos pilas, descubra cuál es el mínimo valor de desorden que es posible conseguir.

Entrada

Una entrada contiene un número indeterminado de casos de prueba. Cada caso de prueba está formado por dos líneas, una por pila. Una pila es una secuencia de números entre el 1 y el 1000, separados por espacios. El número 0 marca el final de la pila y no debe contarse como carta. Dos casos de prueba consecutivos se separan por una línea en blanco.

Salida

Para cada caso de pruebas, escribe en una línea el mínimo valor de desorden que es posible conseguir.

Puntuación

• Test1:  40 Puntos 

  Resolver 100 casos donde ninguna pila tiene más de 10 cartas.

• Test2:  30 Puntos 

  Resolver 10 casos donde ninguna pila tiene más de 100 cartas.

• Test3:  30 Puntos 

  Resolver 10 casos donde ninguna pila tiene más de 500 cartas.