Excavación (1) P95353


Statement
 

pdf   zip

thehtml

Cuánto más profunda sea la mina, más mineral se podrá extraer, pero mayor resulta el coste de la excavación. En este problema asumiremos que excavar el primer metro cuesta 1 euro, excavar el segundo metro 2 euros adicionales y, en general, excavar el n-ésimo metro cuesta n euros. Te pedimos que, conociendo el valor del mineral que se encuentra en cada profundidad de la mina, calcules cuántos metros deberías excavar para obtener el máximo beneficio.

Entrada

Una entrada empieza con un número N≥ 0 en una línea, seguido de N casos de prueba. Cada caso de pruebas se da en una línea, y está formado por un número k≥ 0 (la máxima profundad que es posible excavar) seguido de tres espacios, seguido de k números a1,…, ak≥ 0, donde ai es el valor, en euros, del mineral que se encuentra a i metros de la superficie. Se te asegura que N,k<100 y que todos los valores ai cumplen ai<1000.

Salida

Para cada caso de pruebas, escribe en una línea el máximo beneficio que podrías obtener y el mínimo número de metros a excavar con el que obtendrías dicho beneficio.

Public test cases
  • Input

    9
    1   0
    1   1
    1   2
    0   
    5   0 0 4 4 4
    5   2 2 2 2 2
    5   1 2 3 4 6
    5   1 2 3 4 4
    10   8 1 3 1 3 2 9 9 2 1
    

    Output

    0 0
    0 0
    1 1
    0 0
    0 0
    1 1
    1 5
    0 0
    7 1
    
  • Input

    3
    5   0 1 0 5 1
    5   0 1 3 6 11
    5   0 1 6 4 3
    

    Output

    0 0
    6 5
    1 3
    
  • Input

    0
    

    Output

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