Viaje en el tiempo
Con motivo del centenario del nacimiento de Alan Turing, Marty McFly Jr. ha pedido al científico amigo de su padre, Doc Emmett Brown, que le ayude a realizar un viaje en el tiempo que le permita conocerle. Para eso, se trasladan a Cambridge, introducen en el teclado del De Lorean la fecha 5 de Junio de 1934 y viajan hasta ese día. Tras una búsqueda intensiva por las aulas del King's College, se encuentran al genio en su despacho intentando desarrollar una respuesta al Entscheidungsproblem o, en español, "problema de decisión". Alan tardaría aún dos años más en publicar sus conclusiones, basadas en la que hoy es conocida como "Máquina de Turing". Esta gran aportación del genial matemático le haría figurar como el padre de la informática moderna.
En 1934, sin embargo, Marty y Doc se encuentran a Alan en una etapa temprana de su trabajo, desarrollando una máquina muy sencilla en la que, además, parece haber algún problema de funcionamiento. Animado por el interés que muestran los recién llegados, Turing les cuenta su problema. Está tratando de crear una máquina que genere una serie numérica en la que cada número sea la suma de una constante entera al número inmediatamente anterior. Por desgracia, la máquina no está totalmente depurada, y de vez en cuando parece modificar esa constante, usando el nuevo valor a partir de ese momento para el resto de números, hasta el próximo fallo. El resultado es que las secuencias generadas por la máquina no son series numéricas correctas.
Alan muestra a los viajantes temporales el resultado de la última serie que ha calculado su máquina. Los primeros valores eran 1, 5, por lo que el resultado debería ser 1, 5, 9, 13,... Pero en realidad la respuesta de la máquina ha sido 1, 5, 7, 9, 11, es decir, a partir del valor 5, la máquina ha pasado de calcular una sucesión de término 4 a una de término 2.
La máquina no está definida para valores negativos, ni superiores a 999.999. Para la máquina, el espacio de números es circular, es decir por debajo de 0 se encuentra el 999.999, 999.998, ... y por encima de 999.999 está el 0, 1, 2, 3, etc.
En su búsqueda de la causa del problema, Turing está intentando encontrar alguna relación entre las secuencias y el número de veces que la máquina introduce un cambio en el término de la sucesión. También quiere saber cuál sería el siguiente resultado que le daría la máquina, teniendo en cuenta el último cambio de término. Esto resulta ser una ardua labor, pues las secuencias generadas por la máquina son arbitrariamente largas, y una comprobación manual es muy tediosa.
Marty y Doc le ofrecen su ayuda, sabiendo que, volviendo al futuro, esa labor podrán hacerla de manera automática gracias a los ordenadores, los tataranietos de la máquina de Turing. Planean añadir así su granito de arena al desarrollo de la informática, al igual que hizo Marty en su primera visita a 1955 con el Rock and Roll. Rodeados de un montón de cintas de Turing con secuencias de números erróneas, adelantan 78 años el temporizador del De Lorean y te buscan para que les ayudes.
Entrada
La entrada estará compuesta por un número indicando la cantidad de casos de prueba que vendrán a continuación. Cada caso de prueba consistirá en una serie de números enteros no negativos, con una de las secuencias que Turing nos ha pedido que analicemos. Todas las secuencias tendrán al menos dos números, y terminarán con un -1 adicional, que no deberá ser procesado.
Salida
Para cada caso de prueba, el programa mostrará el número de veces que la máquina ha cambiado el término de la sucesión y el siguiente número de la misma.
Entrada de ejemplo
4 1 5 7 9 11 -1 1 2 3 4 5 6 7 8 10 -1 999996 999998 0 2 4 -1 10 9 8 7 3 2 -1
Salida de ejemplo
1 13 1 12 0 6 2 1