Un număr natural se numește kpower dacă este putere a numărului natural . O secvență kpower este un subşir de numere kpower care apar pe poziţii consecutive într-un şir.
Cerinţă
Fiind dat un un număr natural și un şir de numere naturale, scrieți un program care rezolvă următoarele cerințe:
- Determină cel mai mare număr kpower dintre cele numere date.
- Determină lungimea maximă a unei secvențe kpower.
- 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 reprezentând cerința (, sau ), pe a doua linie numerele și , iar pe a treia linie un șir de numere, numerele de pe aceeași linie fiind separate prin câte un spațiu.
Date de ieşire
Dacă cerința , 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 , 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 , 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
- Cele numere citite sunt din intervalul .
- Pentru toate datele de test, există cel puțin un număr kpower printre cele numere.
- Pentru teste valorând de puncte, .
- Pentru teste valorând de puncte, .
- Pentru teste valorând de puncte, .
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
este , iar cel mai mare număr din șir care este putere a lui este .
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 din șir sunt , și . Lungimea maximă a unei secvențe kpower este .
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ă: .