Troll-hunter P89823


Statement
 

pdf   zip

thehtml

El nou joc de moda és Troll-Hunter! En aquest joc, s’ha d’escapar d’una masmorra plena de trols. La masmorra té n nivells, i el nivell ii sales. Denotem amb S[i][j] la j-èsima sala del nivell i. De cada S[i][j] surten exactament dos pasadissos unidireccionals: un cap a S[i+1][j] i un cap a S[i+1][j+1]. A més, cada sala S[i][j] té T[i][j] trols. En començar el joc et trobes a S[1][1]. Et pots escapar per qualsevol sala del nivell n.

Després de jugar una mica, has descobert que sempre pots superar la primera sala. Després, pots superar una nova sala si i només si el seu nombre de trols no supera el nombre de trols de la sala acabada de visitar (els matessis amb C-ESC o no, segueix llegint). Però un amic t’ha explicat un truc: Si prems Control+Escape (C-ESC per abreujar), els trols de la sala actual moren i pots seguir jugant. Com utilitzar aquest truc sovint faria el joc massa fàcil, el teu objectiu és passar el joc usant el mínim de nombre de C-ESCs.

Entrada

L’entrada consisteix en diversos casos, només amb naturals, cadascun amb n seguida de n ‍línies. La i-èsima línia conté T[i][1] … T[i][i]. Suposeu 2 ≤ n ≤ 1000 i 1 ≤ T[i][j] ≤ 109.

Sortida

Per a cada cas, escriviu el mínim nombre de C-ESCs que calen per passar la masmorra.

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
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++