2225 - complementar - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-04T20:45:27Z

Date de ieșire

← Older revision		Revision as of 20:45, 4 May 2023
Line 9:		Line 9:
	==Date de ieșire==		==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.		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 ("Input valid" ~~sau~~ "Input în afara limitelor" ~~în funcție de datele introduse)~~.		În acest caz în consolă se va afișa un mesaj de validare a datelor "Input valid". În caz contrar pe consolă se va afișa mesajul "Input în afara limitelor".

	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ n ≤ 200 000		* 1 ≤ n ≤ 200 000

Cata at 06:24, 3 May 2023

2023-05-03T06:24:26Z

← Older revision		Revision as of 06:24, 3 May 2023
Line 9:		Line 9:
	==Date de ieșire==		==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.		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.		În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau "Input în afara limitelor" în funcție de datele introduse).
	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ n ≤ 200 000		* 1 ≤ n ≤ 200 000
Line 82:		Line 82:
	f.write(str(ans) + '\n')		f.write(str(ans) + '\n')

	~~def main()~~:		if __name__ == '__main__':
	n, m = read_input()		n, m = read_input()
	if not validate_input(n, m):		if not validate_input(n, m):
	print("Input ~~values are out of bounds!~~")		print("Input în afara limitelor")
	return		return
	else:		else:
	print("~~Valid input~~")		print("Input valid")
	model = compute_model(m)		model = compute_model(m)
	p = read_data(n)		p = read_data(n)
	ans = compute_answer(p, model)		ans = compute_answer(p, model)
	write_output(ans)		write_output(ans)


	~~if __name__ == '__main__':~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

Cata at 07:32, 28 April 2023

2023-04-28T07:32:33Z

← Older revision		Revision as of 07:32, 28 April 2023
Line 9:		Line 9:
	==Date de ieșire==		==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.		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==		==Restricții și precizări==
	* 1 ≤ n ≤ 200 000		* 1 ≤ n ≤ 200 000
	* 4 ≤ m ≤ 30		* 4 ≤ m ≤ 30
	==Exemplu==		==Exemplu==
	complementar.in		; complementar.in
			: 5 6
	5 6		: 101001
	101001		: 010110
	010110		: 010110
	010110		: 111111
	111111		: 000000
	000000		; complementar.out
	complementar.out		: 3
			; Consolă
	3		: Valid input
	==Explicație==		==Explicație==
	Cele trei perechi de linii complementare sunt (1,2), (1,3) și (4,5).		Cele trei perechi de linii complementare sunt (1,2), (1,3) și (4,5).
Line 87:		Line 87:
	print("Input values are out of bounds!")		print("Input values are out of bounds!")
	return		return
			else:
			print("Valid input")
	model = compute_model(m)		model = compute_model(m)
	p = read_data(n)		p = read_data(n)

Cata: Pagină nouă: 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 lin...

2023-04-20T15:39:05Z

Pagină nouă: 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 lin...

New page

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.

==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
==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
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().