2225 - complementar

Se consideră o matrice binară cu n linii și m coloane. Spunem că două linii L1, L2 din matrice sunt complementare dacă a[L1][j] ≠ a[L2][j], pentru orice j=1..m (adică acolo unde pe linia L1 este 0, pe linia L2 este 1 și invers).

Cerința

Să se determine numărul de perechi de linii (L1, L2) cu L1 < L2 cu proprietatea că sunt complementare.

Date de intrare

Fișierul de intrare complementar.in conține pe prima linie numerele n și m. Pe următoarele n linii, fără spații între ele, sunt câte m de valori binare.

Date de ieșire

Fișierul de ieșire complementar.out va conține un singur număr natural reprezentând numărul perechi de linii complementare. În consolă se va afișa un mesaj de validare a datelor.

Restricții și precizări

• 1 ≤ n ≤ 200 000
• 4 ≤ m ≤ 30

Exemplu

complementar.in

5 6

101001

010110

010110

111111

000000

complementar.out

3

Consolă

Valid input

Explicație

Cele trei perechi de linii complementare sunt (1,2), (1,3) și (4,5).

Rezolvare

<syntaxhighlight lang="python"> def read_input():

   with open('complementar.in', 'r') as f:
       n, m = map(int, f.readline().split())
   return n, m

def validate_input(n, m):

   if not (1 <= n <= 200000):
       return False
   if not (4 <= m <= 30):
       return False
   return True

def compute_model(m):

   model = 0
   for i in range(m):
       model += (1 << i)
   return model

def parse_binary(s):

   x = 0
   exponent = 0
   for j in range(len(s) - 1, -1, -1):
       if s[j] == '1':
           x += (1 << exponent)
       exponent += 1
   return x

def read_data(n):

   p = {}
   with open('complementar.in', 'r') as f:
       f.readline() # ignore first line
       for i in range(n):
           s = f.readline().strip()
           x = parse_binary(s)
           if x not in p:
               p[x] = 0
           p[x] += 1
   return p

def compute_answer(p, model):

   ans = 0
   for e in p:
       y = (model ^ e)
       if y in p:
           ans += p[e] * p[y]
           p[y] = 0
   return ans

def write_output(ans):

   with open('complementar.out', 'w') as f:
       f.write(str(ans) + '\n')

def main():

   n, m = read_input()
   if not validate_input(n, m):
       print("Input values are out of bounds!")
       return
   else:
       print("Valid input")
   model = compute_model(m)
   p = read_data(n)
   ans = compute_answer(p, model)
   write_output(ans)

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicație cod

Acest cod este un program Python care citește date de intrare din fișierul 'complementar.in', validează aceste date, apoi citește date suplimentare și calculează un răspuns, pe care îl scrie în fișierul 'complementar.out'.

Funcția read_input() citește primele două valori din fișierul de intrare și le returnează ca o tuplă.

Funcția validate_input() primește cele două valori citite de funcția read_input() și verifică dacă sunt în limitele specificate. Dacă nu, funcția returnează False, altfel returnează True.

Funcția compute_model() primește o valoare m și calculează un model folosind un loop for care construiește o valoare binară formată din m cifre de 1.

Funcția parse_binary() primește o valoare binară sub forma unui șir de caractere și o convertește într-o valoare întreagă.

Funcția read_data() citește datele suplimentare din fișierul de intrare și le stochează într-un dicționar, numărul de apariții ale fiecărei valori binare fiind valoarea asociată cu cheia binară în dicționar.

Funcția compute_answer() primește dicționarul creat de funcția read_data() și modelul calculat de funcția compute_model(), calculează complementul fiecărei valori din dicționar și verifică dacă complementul este prezent în dicționar. Dacă este prezent, funcția calculează produsul numărului de apariții ale valorii inițiale și complementare și îl adaugă la răspuns. Funcția returnează răspunsul.

Funcția write_output() primește răspunsul și îl scrie în fișierul de ieșire 'complementar.out'.

Funcția main() este funcția principală care apelează celelalte funcții pentru a citi datele de intrare, valida datele, calcula răspunsul și scrie răspunsul în fișierul de ieșire. Dacă datele de intrare nu sunt valide, funcția afișează un mesaj de eroare și returnează.

Instrucțiunea if name == 'main': verifică dacă acest script este executat ca un program independent și, dacă este așa, apelează funcția main().