2560 - Bits

Enunț

Se dă un număr natural N.

Cerință

Determinați valoarea unor anumiți biți din reprezentarea sa în baza 2.

Date de intrare

Fișierul de intrare bits.in conține pe prima linie două numere naturale N și Q separate prin spațiu. Pe linia a doua se află Q numere naturale separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." Fișierul de ieșire bits.out conține pe prima linie Q valori, neseparate prin spațiu, reprezentând, în ordine, răspunsurile la întrebări. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 0 ≤ N ≤ 2^63-1
• 1 ≤ Q ≤ 63
• valorile de pe a doua linie a fișierului de intrare sunt distincte și cuprinse între 0 și 62 (inclusiv)
• biții se numerotează începând cu poziția 0 (cel mai puțin semnificativ)
• numărul N este reprezentat pe 64 de biți

Exemplul 1

bits.in

12 4

2 0 3 20

bits.out

1010

Ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse."

Explicație

Reprezentarea internă a valorii 12 este 000...0001100. Biții de pe pozițiile 0 și 20 au valoarea 0 iar cei de pe pozițiile 2 și 3 au valoarea 1.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1">

def validate_input(n, q, queries):

   """
   Verifică dacă datele de intrare respectă condițiile problemei.
   """
   if not 0 <= n <= 2**63 - 1:
       return False
   if not 1 <= q <= 63:
       return False
   if len(queries) != q:
       return False
   if any(query < 0 or query > 62 for query in queries):
       return False
   return True

def get_bits(n, queries):

   """
   Returnează valorile biților specificați din reprezentarea în baza 2 a lui n.
   """
   binary_n = bin(n)[2:].zfill(64)
   results = []
   for query in queries:
       bit_value = binary_n[-query-1]
       results.append(bit_value)
   return .join(results)

if __name__ == '__main__':

   with open('bits.in', 'r') as f_in, open('bits.out', 'w') as f_out:
       n, q = map(int, f_in.readline().split())
       queries = list(map(int, f_in.readline().split()))
       if not validate_input(n, q, queries):
           f_out.write('Invalid input')
       else:
           result = get_bits(n, queries)
           f_out.write(result)

</syntaxhighlight>

Explicatie

Funcția validate_input verifică dacă datele de intrare respectă restricțiile problemei. Dacă nu sunt respectate, se returnează False. Altfel, se returnează True.

Funcția get_bits primește numărul n și lista de întrebări queries. Transformă n în reprezentarea sa în baza 2 sub formă de șir de caractere și extrage biții specificați din listă. Rezultatul este returnat sub formă de șir de caractere.

Blocul main începe prin deschiderea fișierelor de intrare și de ieșire. Pe prima linie din fișierul de intrare se citesc valorile n și q, iar pe a doua linie se citesc întrebările. Se validează datele de intrare prin apelul funcției validate_input. Dacă datele nu sunt valide, se afișează în fișierul de ieșire mesajul "Invalid input". Altfel, se apelează funcția get_bits și se scrie rezultatul în fișierul de ieșire.