Rezolvare PBinfo #976

Se consideră şirul de numere naturale ai cărui primi termeni sunt, în această ordine:

1, 5, 3, 7, 9, 11, 19, 17, 15, 13, 21,...

• prima grupă, numerotată cu 1, conţine primul termen al şirului (1)
• a doua grupă, numerotată cu 2, conţine următorii doi termeni ai şirului (5,3)
• a treia grupă, numerotată cu 3, conţine următorii trei termeni ai şirului (7,9,11)
• ……………………….
• a n-a grupă din şir, numerotată cu n, conţine următorii n termeni ai şirului
  etc.

Cerinţe

Deduceţi regula după care sunt generaţi termenii şirului şi scrieţi un program care să citească numerele naturale p, n şi k şi care să determine:

a) termenul de pe poziţia p din şirul din enunţ;
b) cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele tuturor numerelor din grupa a n-a a şirului dat, nu neapărat toate aceste cifre;
c) numărul grupei ce conţine un număr maxim de termeni şi are proprietatea că suma acestor termeni este cel mult egală cu k.

Date de intrare

Programul citește de la tastatură cele trei numere, p n k.

Date de ieșire

Programul va afișa pe ecran trei numere, reprezentând, în ordine:

• termenul de pe poziţia p din şirul din enunţ;
• cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele din scrierea zecimală a tuturor termenilor din grupa a n-a a şirului dat, nu neapărat toate aceste cifre;
• pe a treia linie se va scrie numărul grupei ce conţine un număr maxim de termeni şi are proprietatea că suma acestora este cel mult egală cu k.

Restricții și precizări

• Numerele p, n şi k sunt naturale
• 1 ≤ p ≤ 1000000000
• 1 ≤ n ≤ 50
• 1 ≤ k ≤ 2000000000
• un număr natural este palindrom dacă este egal cu numărul obţinut prin scrierea cifrelor sale în ordine inversă
• Pentru rezolvarea cerinţei a) se acordă 40% din punctaj, pentru cerinţa b) 30% din punctaj şi pentru cerinţa c) 30% din punctaj.

Exemplu:

Intrare

7 5 127

Ieșire

19
22922
5

Explicație

• Primii 7 termeni ai şirului sunt: 1,5,3,7,9,11,19. Termenul căutat are valoarea 19.
• Numerele din grupa a 5-a sunt scrise cu ajutorul a cinci cifre de 2, o cifră de 3, una de 5, una de 7, una de 9. Cel mai mare palindrom care se poate scrie cu aceste cifre este 22922.
• Grupele a căror sumă este cel mult egală cu k=127 sunt: 1,2,3,4,5. Grupa cu cei mai mulţi termeni şi cu suma maximă (=125) este grupa 5.