Troll-hunter P89823


Statement
 

pdf   zip

thehtml

El nuevo juego de moda es Troll-Hunter! En él, tienes que escapar de una mazmorra llena de trols. La mazmorra tiene n niveles, y el nivel i tiene i salas. Denotemos con S[i][j] la j-ésima sala del nivel i. De cada S[i][j] salen exactamente dos pasadizos unidireccionales: uno hacia S[i+1][j] y uno hacia S[i+1][j+1]. Además, cada sala S[i][j] tiene T[i][j] trols. Al comenzar el juego te encuentras en S[1][1]. Puedes escapar por cualquier sala del nivel n.

Después de jugar un poco, has descubierto que siempre puedes superar la primera sala. Después, puedes superar una nueva sala si y sólo si su número de trols no supera el número de trols de la sala acabada de visitar (los mataras con C-ESC o no, sigue leyendo). Pero un amigo te ha explicado un truco: Si aprietas Control+Escape (C-ESC para abreviar), los trols de la sala actual mueren y puedes seguir jugando. Como usar este truco a menudo haría el juego demasiado fácil, tu objectivo es passar el juego con el mínimo número de C-ESCs.

Entrada

La entrada consiste en diversos casos, sólo con naturales, cada uno con n seguida de n linias. La i-ésima linea contiene T[i][1] … T[i][i]. Suponed 2 ≤ n ≤ 1000 y 1 ≤ T[i][j] ≤ 109.

Salida

Para cada caso, escrivid el mínimo número de C-ESCs necesarios para pasar la mazmorra.

Public test cases

  • Input

    5
3
2 4
3 3 3
4 4 4 3
5 5 5 5 3

5
3
2 4
3 3 3
4 4 4 4
5 5 5 5 5

3
7
2 4
6 6 1

    Output

    1
3
0
    • Information
    Author
    Enrique Jiménez
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++