Tècniques d'entrenament (1) P52820


Statement
 

pdf   zip

thehtml

En els entrenaments de programació de la UPC hi ha xocolatines, coques, panellets, torrons, magdalenes... Per què calen? Quan un estudiant intenta resoldre un problema, la seva autoestima puja o baixa en funció de si ho aconsegueix. Si l’autoestima baixa per sota d’un llindar de resistència mental −R, l’estudiant deixa d’entrenar i se’n va plorant. Per evitar-ho, el professor Oak la pot pujar tant com vulgui repartint galetes (cada galeta suma un). Curiosament, a vegades es produeix el fenomen oposat: alguns estudiants amb massa autoestima (per sobre de R), es creuen molt bons i deixen d’entrenar. Per evitar aquests casos, unes quantes fuetejades fan baixar l’autoestima (cada cop de fuet resta un).

Coneixent quin increment d’autoestima provocarà cada problema en un estudiant fixat, quina és la mínima resistència mental R que cal que tingui perquè no marxi de l’entrenament, si s’escull de forma òptima la quantitat de galetes o de cops de fuet que cal donar-li abans de resoldre cada problema?

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de problemes n, seguit, en l’ordre que s’intentaran resoldre els problemes, dels n increments xi d’autoestima que provoquen cadascun. Suposeu 1 ≤ n ≤ 104, i que els xi són enters entre −104 i 104.

Sortida

Per a cada cas, escriviu la mínima resistència mental R que ha de tenir l’estudiant. Suposeu que la seva autoestima inicial és zero.

Public test cases
  • Input

    3  0 0 0
    1 -6
    1  5
    2  1 -2
    2  -2 1
    4  1 1 1 1
    3  20 -70 -40
    

    Output

    0
    3
    3
    1
    1
    1
    35
    
  • Information
    Author
    Maria Bauzà i Ferran Alet
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++