Rezolvare PBinfo #4581

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 ≤ 9
• 1 ≤ n ≤ 1.000.000
• cele n numere citite sunt din intervalul [0, 1012]
• pentru toate datele de test, există cel puțin un număr kpower printre cele n numere
• 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.