Vizualizare sursă pentru „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 <code>2</code>, strict mai mică decât <code>2<sup>26</sup></code>, cu o literă a alfabetului, astfel:

{| class="wikitable"
|<code>2<sup>0</sup></code>
|<code>2<sup>1</sup></code>
|<code>2<sup>2</sup></code>
|<code>2<sup>3</sup></code>
|<code>2<sup>4</sup></code>
|<code>2<sup>5</sup></code>
|<code>2<sup>6</sup></code>
|<code>2<sup>7</sup></code>
|<code>2<sup>8</sup></code>
|<code>2<sup>9</sup></code>
|<code>2<sup>10</sup></code>
|<code>2<sup>11</sup></code>
|<code>2<sup>12</sup></code>
|-
|a
|b
|c
|d
|e
|f
|g
|h
|i
|j
|k
|l
|m
|-
|<code>2<sup>13</sup></code>
|<code>2<sup>14</sup></code>
|<code>2<sup>15</sup></code>
|<code>2<sup>16</sup></code>
|<code>2<sup>17</sup></code>
|<code>2<sup>18</sup></code>
|<code>2<sup>19</sup></code>
|<code>2<sup>20</sup></code>
|<code>2<sup>21</sup></code>
|<code>2<sup>22</sup></code>
|<code>2<sup>23</sup></code>
|<code>2<sup>24</sup></code>
|<code>2<sup>25</sup></code>
|-
|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 <code>2</code>; 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 <code>100</code> printre variantele de reprezentare avem:

* <code>100 = cfg = 2<sup>2</sup>+2<sup>5</sup>+2<sup>6</sup> = 4+32+64 = 100</code>
* <code>100 = 2ab2cde2f = 2*2<sup>0</sup>+2<sup>1</sup>+2*2<sup>2</sup>+2<sup>3</sup>+24+2*2<sup>5</sup> = 2*1+2+2*4+8+16+2*32 = 100</code>
* <code>100 = 16bcg = 16*2<sup>1</sup>+2<sup>2</sup>+2<sup>6</sup> = 16*2+4+64 = 100</code>

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

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

= Date de intrare =
Fișierul de intrare <code>stele.in</code> conține pe prima linie un număr natural <code>c</code>, 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 <code>s</code>, ce reprezintă numărul care trebuie codificat.

Dacă cerinţa este 2, pe a doua linie se află un număr natural <code>g</code> reprezentând numărul de galaxii, iar pe următoarele <code>g</code> 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 <code>stele.out</code> 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 <code>s</code> (dacă cerinţa este 1) sau un număr natural în scriere zecimală ce reprezintă numărul total de stele din cele <code>g</code> galaxii (dacă cerinţa este 2).

= Restricții și precizări =

* <code>1 ≤ s ≤ 2<sup>26</sup>-1</code>
* <code>1 ≤ g ≤ 1000</code>
* Reprezentările codificate din fişierul de intrare pot avea maximum <code>420</code> caractere.
* Numărul care poate apărea în fața unei litere poate avea maximum <code>15</code> 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 <code>10<sup>18</sup></code>

= Exemplul 1 =
<code>stele.in</code>
 1
 100
<code>stele.out</code>
 cfg

=== Explicație ===
Cerința este 1. Reprezentarea numărului <code>100</code>  care respectă cerinţa este: <code>cfg = 2<sup>2</sup>+2<sup>5</sup>+2<sup>6</sup> = 4+32+64 = 100</code>

<syntaxhighlight lang="python" line="1">
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}")
</syntaxhighlight>