1706 - Stele

Pasionată de astronomie, Teodora dorește să țină evidența numărului de stele din galaxii. Pentru a face lucrurile mai interesante, ea codifică aceste numere într-un sistem propriu, transformându-le într-o înșiruire de litere și cifre după algoritmul următor:

• notează fiecare putere a lui 2, strict mai mică decât 226, cu o literă a alfabetului, astfel:

20	21	22	23	24	25	26	27	28	29	210	211	212
a	b	c	d	e	f	g	h	i	j	k	l	m
213	214	215	216	217	218	219	220	221	222	223	224	225
n	o	p	q	r	s	t	u	v	w	x	y	z

• reprezintă fiecare număr ca un șir de cifre și litere obținut din scrierea acelui număr ca sumă de puteri ale lui 2; dacă o putere este folosită de mai multe ori în descompunerea numărului atunci ea va fi precedată în șir de numărul de utilizări.

Un număr poate fi reprezentat astfel în mai multe moduri. De exemplu, pentru numărul 100 printre variantele de reprezentare avem:

• 100 = cfg = 22+25+26 = 4+32+64 = 100
• 100 = 2ab2cde2f = 2*20+21+2*22+23+24+2*25 = 2*1+2+2*4+8+16+2*32 = 100
• 100 = 16bcg = 16*21+22+26 = 16*2+4+64 = 100

Cerința

Scrieți un program care rezolvă următoarele cerinţe:

1. cunoscând s numărul de stele dintr-o galaxie, determină o reprezentare codificată a acestui număr formată doar din litere mici distincte ordonate alfabetic;
2. cunoscând g, reprezentând numărul de galaxii și g numere în scriere codificată, reprezentând numărul de stele din fiecare galaxie, determină scrierea zecimală a numărului total de stele din cele g galaxii.

Date de intrare

Fișierul de intrare stele.in conține pe prima linie un număr natural c, reprezentând cerinţa care trebuie rezolvată (1 sau 2). Dacă cerinţa este 1, pe a doua linie se află un număr natural s, ce reprezintă numărul care trebuie codificat.

Dacă cerinţa este 2, pe a doua linie se află un număr natural g reprezentând numărul de galaxii, iar pe următoarele g linii câte un șir de caractere reprezentând numărul de stele dintr-o galaxie, codificat folosind algoritmul descris mai sus.

Date de ieșire

Fișierul de ieșire stele.out va conţine o singură linie pe care va fi scris un șir de litere mici distincte, ordonate alfabetic, reprezentând scrierea codificată a numărului s (dacă cerinţa este 1) sau un număr natural în scriere zecimală ce reprezintă numărul total de stele din cele g galaxii (dacă cerinţa este 2).

Restricții și precizări

• 1 ≤ s ≤ 226-1
• 1 ≤ g ≤ 1000
• Reprezentările codificate din fişierul de intrare pot avea maximum 420 caractere.
• Numărul care poate apărea în fața unei litere poate avea maximum 15 cifre.
• Pentru teste valorând 30% din punctaj cerinţa este 1.
• Pentru teste corespunzătoare cerinţei 2 valorând 20% din punctaj valoarea obținută nu depășește 1018

Exemplul 1

stele.in

1
100

stele.out

cfg

Explicație

Cerința este 1. Reprezentarea numărului 100 care respectă cerinţa este: cfg = 22+25+26 = 4+32+64 = 100

def num_to_code(s):
    powers_of_2 = [
        1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,
        16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432
    ]
    letters = "abcdefghijklmnopqrstuvwxyz"
    
    result = []
    i = len(powers_of_2) - 1
    while s > 0:
        if s >= powers_of_2[i]:
            result.append(letters[i])
            s -= powers_of_2[i]
        i -= 1
    
    return ''.join(sorted(result))

def code_to_num(code):
    letters = "abcdefghijklmnopqrstuvwxyz"
    powers_of_2 = {
        letter: 2 ** i for i, letter in enumerate(letters)
    }
    
    total = 0
    for char in code:
        total += powers_of_2[char]
    
    return total

def total_stars_in_galaxies(galaxies):
    total_stars = 0
    for galaxy in galaxies:
        total_stars += code_to_num(galaxy)
    return total_stars

# Exemple de utilizare
s = 100
code_representation = num_to_code(s)
print(f"Reprezentarea codificată a numărului {s}: {code_representation}")

g = 3
galaxies = ["cfg", "bcd", "ace"]
total_stars = total_stars_in_galaxies(galaxies)
print(f"Numărul total de stele din {g} galaxii: {total_stars}")