Caballo adelante P48080


Statement
 

pdf   zip

thehtml

Se tiene un tablero de ajedrez de tamaño n× n. En cada casilla hay una cantidad determinada de monedas de oro. Un caballo, que empieza en la casilla inferior izquierda, puede saltar libremente por todo el tablero (siguiendo las reglas del ajedrez), pero a cada salto, el caballo debe desplazarse a una fila superior.

El caballo empieza con las monedas de la casilla inicial, y cada vez que llega a una nueva casilla, obtiene las monedas que en ella hubiera. Realizar un salto cuesta dos monedas de oro. Por tanto, el caballo debe parar si no dispone de al menos dos monedas. Sabiendo que el caballo puede decidir acabar el juego en cualquier instante (incluyendo el inicial) determinad la máxima cantidad de monedas de oro que es posible conseguir.

Entrada

La entrada está formada por un número arbitrario de casos de prueba. Cada caso de pruebas empieza con un número n en una línea, seguido de n líneas (filas) de n naturales (números positivos o cero) con el número de monedas de oro que hay en cada casilla. La casilla inferior izquierda, es decir, el número de monedas de oro con las que empieza el caballo, se corresponde con el primer número de la última línea.

Salida

Para cada caso de pruebas, escribe una línea con el máximo número de monedas de oro que puede conseguir el caballo.

Puntuación

Diez juegos de prueba con 50 casos cada uno, de tamaños n=3, 4, 6, 8, 10, 20, 40, 60, 80 y 100. Se dará 10 puntos por cada juego de pruebas resuelto.

Public test cases

  • Input

    3
1 2 3
3 2 1
1 3 5
3
1 2 3
3 2 8
1 3 5
3
1 2 3
3 2 6
2 3 5
3
8 2 3
3 2 2
2 3 5

    Output

    1
1
6
8

  • Input

    8
4 2 0 1 2 3 1 9
3 3 1 3 9 2 3 2
3 9 1 2 3 4 1 3
8 0 0 1 0 0 0 0
3 0 0 1 9 3 1 0
9 3 9 1 3 4 0 3
3 8 4 0 1 3 3 1
8 1 3 4 0 2 0 1

    Output

    27
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++