Obres V78601
Les reformes al pis del professor Oak duren més que l’obra de la Seu. En part, perquè el que es construeix un dia es pot destruir l’endemà. Intrigat per aquest fenomen, el professor ha mesurat les millores de cada dia, i se n’ha adonat que tenen forma cíclica.
Si mesurem amb “punts” l’estat del pis, i suposant que inicialment (dia 0) té 0 punts, podria passar que el cicle sigui de mida quatre: el primer dia el pis guanya 10 punts, l’endemà en perd 3, l’endemà en guanya 2, l’endemà en perd 5, i i el cicle (+10, −3, +2, −5) torna a començar per sempre. L’evolució dels punts del pis en aquest cas seria 0, 10, 7, 9, 4, 14, 11, 13, 8, 18, 15, 17, 12, …
Suposant que es faran obres sense parar, a partir de quin dia el pis mai baixarà de p punts? Amb l’exemple anterior amb p = 11, la resposta seria 9, corresponent al dia amb 18 punts.
Entrada
L’entrada consisteix en diversos casos, cadascun amb p, la mida del cicle n, i els n valors del cicle. Podeu suposar 1 ≤ p ≤ 108, 1 ≤ n ≤ 105, que tots els valors del cicle es troben entre −105 i 105, i que la suma d’aquests valors és estrictament positiva.
Sortida
Per a cada cas, escriviu el primer dia a partir del qual l’estat del pis mai baixarà dels p punts.
Puntuació
- Cas A: 40% Punts
Casos on tant n com la resposta són com a molt 100, com els de l’exemple d’entrada 1.
- Cas B: 30% Punts
Casos on n és com a molt 1000.
- Cas C: 30% Punts
Casos de tot tipus.
Input
11 4 10 -3 2 -5 37 3 -23 63 -10 38 3 -23 63 -10 1 3 0 0 10000 42 1 1 1 4 -3 -2 -1 7
Output
9 5 8 3 42 28
Input
100000000 10 -1 0 0 0 0 0 0 0 0 2
Output
1000000010
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++