Excavación (1) P95353
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.
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
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++