0980 - Sir 4

Se consideră şirul de numere naturale:

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

Se grupează numerele din şir astfel încât prima grupă, numerotată cu 1, este formată din primul număr din şir (1), a doua grupă, numerotată cu 2, este formată din următoarele două numere din şir (3,5), a treia grupă, numerotată cu 3, este formată din următoarele trei numere din şir (7,9,11),…, a n-a grupă din şir, numerotată cu n, este formată din următoarele n numere din şir, 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) al câtelea număr din şir are valoarea p;

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 cu proprietatea că suma tuturor numerelor conţinute de aceasta este egală cu numărul k, dacă există o astfel de grupă.

Date de intrare

Programul citește de la tastatură, în acestă ordine, trei numere naturale p, n şi k.

Date de ieșire

Programul va afișa pe ecran, în această ordine:

• o valoare naturală reprezentând al câtelea număr din şir are valoarea p.
• 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.
• numărul grupei cu proprietatea că suma tuturor numerelor conţinute de aceasta este egală cu numărul k; dacă nu există o astfel de grupă se va scrie numărul 0

Restricții și precizări

• Numerele p, n şi k sunt naturale
• 1 ≤ p ≤ 2.000.001, p număr natural impar
• 1 ≤ n ≤ 50
• 1 ≤ k ≤ 2.000.000.000

Exemplul 1

Input:

19 5 125

Output:

10

22922

5

Explicație:

• În şir, valoarea 19 apare pe poziţia 10, aceşti 10 termeni termeni fiind: 1,3,5,7,9,11,13,15,17,19.
• Numerele din grupa a 5-a sunt scrise cu ajutorul a 1 cifră de 1, 5 cifre de 2, 1 de 3, 1 de 5, 1 de 7, 1 de 9. Ce mai mare palindrom care se poate scrie cu aceste cifre este 22922.
• Grupa 5 are suma egală cu k (21+23+25+27+29=125).

Exemplul 2

Input:

999999999999999 5 125

Output:

Constrangeri neindeplinite

Rezolvare

def is_valid_input(p, n, k):
    return (1 <= p <= 2000001) and (p % 2 == 1) and (1 <= n <= 50) and (1 <= k <= 2000000000)

p, n, k = map(int, input().split())

if not is_valid_input(p,n,k):
    print("Constrangeri neindeplinite")
    exit()

print((p + 1) // 2)

# palindrom
cifre = [0] * 10
for i in range(n * n - n + 1, n * n - n + 1 + 2 * n, 2):
    aux = i
    while aux:
        cifre[aux % 10] += 1
        aux //= 10

result = []
for i in range(9, -1, -1):
    result.extend([str(i)] * (cifre[i] // 2))
for i in range(9, -1, -1):
    if cifre[i] % 2 == 1:
        result.append(str(i))
        break
for i in range(10):
    result.extend([str(i)] * (cifre[i] // 2))

print("".join(result))
# palindrom

cbr = round(k ** (1 / 3))
if cbr ** 3 == k:
    print(cbr)
else:
    print(0)