0976 - Sir 3

Enunt

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,... Se grupează numerele din şir astfel:

• 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ţa

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.

Exemplul 1

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.

Rezolvare

def generate_sequence(n):
    sequence = [1]
    current = 5
    for i in range(2, n + 1):
        sequence.extend(range(current, current + i))
        current += i + 1
    return sequence

def find_term(p, n):
    sequence = generate_sequence(n)
    return sequence[p - 1]

def is_palindrome(num):
    return str(num) == str(num)[::-1]

def find_largest_palindrome(numbers):
    palindromes = [int(str(num)[::-1]) for num in numbers if is_palindrome(num)]
    return max(palindromes)

def find_max_group(p, n, k):
    max_sum = 0
    max_group = 0
    sequence = generate_sequence(n)
    for i in range(1, n + 1):
        group = sequence[sum(range(i)) : sum(range(i + 1))]
        group_sum = sum(group)
        if group_sum <= k and len(group) > max_group:
            max_group = len(group)
            max_sum = group_sum
    return max_group

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

# a)
term = find_term(p, n)
print(term)

# b)
group_n = generate_sequence(n)[sum(range(n)): sum(range(n + 1))]
largest_palindrome = find_largest_palindrome(group_n)
print(largest_palindrome)

# c)
max_group = find_max_group(p, n, k)
print(max_group)