Pracsiu Dan (dnprx) Un număr natural se numește kpower dacă este putere a numărului natural k. O secvență kpower este un subşir de numere kpower care apar pe poziţii consecutive într-un şir.
Cerințe
Fiind dat un un număr natural k și un şir de n numere naturale, scrieți un program care rezolvă următoarele cerințe:
1. Determină cel mai mare număr kpower dintre cele n numere date.
2. Determină lungimea maximă a unei secvențe kpower.
3. Determină cea mai mare sumă ce se poate obține adunând numerele dintr-o secvență kpower de lungime maximă.
Date de intrare
Fișierul de intrare kpower.in conține pe prima linie numărul C reprezentând cerința (1, 2 sau 3), pe a doua linie numerele k și n, iar pe a treia linie un șir de n numere, numerele de pe aceeași linie fiind separate prin câte un spațiu.
Date de ieșire
Dacă cerința C = 1, atunci pe prima linie a fişierului de ieşire kpower.out se va scrie cel mai mare număr kpower găsit.
Dacă cerința C = 2, atunci pe prima linie a fişierului de ieşire kpower.out se va scrie lungimea maximă a unei secvențe kpower.
Dacă cerința C = 3, atunci pe prima linie a fişierului de ieşire kpower.out se va scrie suma maximă a unei secvențe kpower de lungime maximă.
Restricții și precizări
0 < k ≤ 91 ≤ n ≤ 1.000.000- cele
nnumere citite sunt din intervalul[0, 1012] - pentru toate datele de test, există cel puțin un număr kpower printre cele
nnumere - pentru teste valorând 20 de puncte cerinţa va fi
C = 1 - pentru teste valorând 30 de puncte cerinţa va fi
C = 2 - pentru teste valorând 40 de puncte cerinţa va fi
C = 3
Exemplul 1:
kpower.in
1 3 19 1 27 9 17 21 3 1 27 3 9 81 78 56 1 3 9 1 81 9
kpower.out
81
Explicație
k este 3, iar cel mai mare număr din șir care este putere a lui 3 este 81.
Exemplul 2:
kpower.in
2 3 19 1 27 9 17 21 3 1 27 3 9 81 78 56 1 3 9 1 81 9
kpower.out
6
Explicație
Secvențele kpower sunt cele subliniate. Lungimea maximă a unei secvențe kpower este 6.
Exemplul 3:
kpower.in
3 3 19 1 27 9 17 21 3 1 27 3 9 81 78 56 1 3 9 1 81 9
kpower.out
124
Explicație
Dintre cele două secvențe kpower de lungime maximă, cea dintâi are suma numerelor maximă: 3 + 1 + 27 + 3 + 9 + 81 = 124.