3707 - forta1 - Revision history

Sovago Rares-Andrei: /* Cerința */

2023-04-29T16:19:38Z

Cerința

← Older revision		Revision as of 16:19, 29 April 2023
Line 2:		Line 2:

	Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1).		Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1).
	Se dă un șir cu n elemente numere naturale. Să se sorteze elementele din șir în ordine crescătoare a forței, iar acele elemente care au aceeași forță să apară în ordine inversă decât apăreau inițial în șir.		Se dă un șir cu '''n''' elemente numere naturale. Să se sorteze elementele din șir în ordine crescătoare a forței, iar acele elemente care au aceeași forță să apară în ordine inversă decât apăreau inițial în șir.

	== Date de intrare ==		== Date de intrare ==

Sovago Rares-Andrei: /* Rezolvare */

2023-04-08T08:05:42Z

Rezolvare

← Older revision		Revision as of 08:05, 8 April 2023
Line 47:		Line 47:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 3707 - forta1		# 3707 - forta1
	def ~~validare_date~~(n, v, distincte=False):		def valideaza_date(numar_elemente, valori, distincte=False):
	if n <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10**18 for x in v):		if numar_elemente <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10**18 for x in valori):
	return False		return False
	if distincte and len(set(v)) != n:		if distincte and len(set(valori)) != numar_elemente:
	return False		return False
	return True		return True


	def ~~rezolvare_problema~~(n, v):		def rezolva_problema(numar_elemente, valori):
	class Forta:		class Forta:
	def __init__(self, ~~val~~, fr, ~~poz~~):		def __init__(self, valoare, frecventa, pozitie):
	self.~~val~~ = ~~val~~		self.valoare = valoare
	self.fr = fr		self.frecventa = frecventa
	self.~~poz~~ = ~~poz~~		self.pozitie = pozitie

	def ~~contor~~(~~nr1~~, ~~nr2~~):		def numara_cifre_comune(numar1, numar2):
	~~fr1~~, ~~fr2~~, ~~cnt~~ = [0] * 10, [0] * 10, 0		frecventa1, frecventa2, numar_comun = [0] * 10, [0] * 10, 0
	while ~~nr1~~:		while numar1:
	~~fr1~~[~~nr1~~ % 10] += 1		frecventa1[numar1 % 10] += 1
	~~nr1~~ //= 10		numar1 //= 10
	while ~~nr2~~:		while numar2:
	~~fr2~~[~~nr2~~ % 10] += 1		frecventa2[numar2 % 10] += 1
	~~nr2~~ //= 10		numar2 //= 10
	for i in range(10):		for i in range(10):
	if ~~fr1~~[i] and ~~fr2~~[i]:		if frecventa1[i] and frecventa2[i]:
	~~cnt~~ += min(~~fr1~~[i], ~~fr2~~[i])		numar_comun += min(frecventa1[i], frecventa2[i])
	return ~~cnt~~		return numar_comun

	~~v_forta~~ = [Forta(~~val~~=v[i], fr=0, ~~poz~~=i) for i in range(n)]		valori_forta = [Forta(valoare=valori[i], frecventa=0, pozitie=i) for i in range(numar_elemente)]
	for i in range(n - 1):		for i in range(numar_elemente - 1):
	for j in range(i + 1, n):		for j in range(i + 1, numar_elemente):
	sm = ~~contor~~(~~v_forta~~[i].~~val~~, ~~v_forta~~[j].~~val~~)		numar_cifre_comune = numara_cifre_comune(valori_forta[i].valoare, valori_forta[j].valoare)
	~~v_forta~~[i].fr += sm		valori_forta[i].frecventa += numar_cifre_comune
	~~v_forta~~[j].fr += sm		valori_forta[j].frecventa += numar_cifre_comune

	for i in range(n - 1):		for i in range(numar_elemente - 1):
	for j in range(i + 1, n):		for j in range(i + 1, numar_elemente):
	if ~~v_forta~~[i].fr > ~~v_forta~~[j].fr:		if valori_forta[i].frecventa > valori_forta[j].frecventa:
	~~v_forta~~[i], ~~v_forta~~[j] = ~~v_forta~~[j], ~~v_forta~~[i]		valori_forta[i], valori_forta[j] = valori_forta[j], valori_forta[i]
	elif ~~v_forta~~[i].fr == ~~v_forta~~[j].fr:		elif valori_forta[i].frecventa == valori_forta[j].frecventa:
	if ~~v_forta~~[i].~~poz~~ < ~~v_forta~~[j].~~poz~~:		if valori_forta[i].pozitie < valori_forta[j].pozitie:
	~~v_forta~~[i], ~~v_forta~~[j] = ~~v_forta~~[j], ~~v_forta~~[i]		valori_forta[i], valori_forta[j] = valori_forta[j], valori_forta[i]

	return [forta.~~val~~ for forta in ~~v_forta~~]		return [forta.valoare for forta in valori_forta]


	if __name__ == "__main__":		if __name__ == "__main__":
	with open("forta.in", "r") as ~~fin~~:		with open("forta.in", "r") as fisier_intrare:
	n = int(~~fin~~.readline())		numar_elemente = int(fisier_intrare.readline())
	v = list(map(int, ~~fin~~.readline().split()))		valori = list(map(int, fisier_intrare.readline().split()))

	if not ~~validare_date~~(n, v, distincte=True):		if not valideaza_date(numar_elemente, valori, distincte=True):
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	exit(0)		exit(0)

	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	rezultat = ~~rezolvare_problema~~(n, v)		rezultat = rezolva_problema(numar_elemente, valori)
	~~with open("forta.out", "w") as fout:~~
	~~fout.write(" ".join(map(str, rezultat)))~~

Nagy Lenard at 20:01, 7 April 2023

2023-04-07T20:01:39Z

← Older revision		Revision as of 20:01, 7 April 2023
Line 34:		Line 34:
	:11 7 5 3 2		:11 7 5 3 2
	===Exemplul 3===		===Exemplul 3===
	; ''forta.in'		; ''forta.in''
	:4		:4
	:-3 2 3 5		:-3 2 3 5

Nagy Lenard: Anularea modificării 3064 făcute de Nagy Lenard (Discuție)

2023-04-07T19:57:58Z

Anularea modificării 3064 făcute de Nagy Lenard (Discuție)

← Older revision		Revision as of 19:57, 7 April 2023
Line 34:		Line 34:
	:11 7 5 3 2		:11 7 5 3 2
	===Exemplul 3===		===Exemplul 3===
	; ''forta.in''		; ''forta.in'
	:4		:4
	:-3 2 3 5		:-3 2 3 5
Line 47:		Line 47:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 3707 - forta1		# 3707 - forta1
	def validare_date(~~numar_elemente~~, ~~valori~~, distincte=False):		def validare_date(n, v, distincte=False):
	if ~~numar_elemente~~ <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10 ** 18 for x in ~~valori~~):		if n <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10**18 for x in v):
	return False		return False
	if distincte and len(set(~~valori~~)) != ~~numar_elemente~~:		if distincte and len(set(v)) != n:
	return False		return False
	return True		return True


	def rezolvare_problema(~~numar_elemente~~, ~~valori~~):		def rezolvare_problema(n, v):
	class Forta:		class Forta:
	def __init__(self, ~~valoare~~, ~~frecventa~~, ~~pozitie~~):		def __init__(self, val, fr, poz):
	self.~~valoare~~ = ~~valoare~~		self.val = val
	self.~~frecventa~~ = ~~frecventa~~		self.fr = fr
	self.~~pozitie~~ = ~~pozitie~~		self.poz = poz

	def contor(nr1, nr2):		def contor(nr1, nr2):
	~~frecventa1~~, ~~frecventa2~~, cnt = [0] * 10, [0] * 10, 0		fr1, fr2, cnt = [0] * 10, [0] * 10, 0
	while nr1:		while nr1:
	~~frecventa1~~[nr1 % 10] += 1		fr1[nr1 % 10] += 1
	nr1 //= 10		nr1 //= 10
	while nr2:		while nr2:
	~~frecventa2~~[nr2 % 10] += 1		fr2[nr2 % 10] += 1
	nr2 //= 10		nr2 //= 10
	for i in range(10):		for i in range(10):
	if ~~frecventa1~~[i] and ~~frecventa2~~[i]:		if fr1[i] and fr2[i]:
	cnt += min(~~frecventa1~~[i], ~~frecventa2~~[i])		cnt += min(fr1[i], fr2[i])
	return cnt		return cnt

	~~forte~~ = [Forta(~~valoare~~=~~valori~~[i], ~~frecventa~~=0, ~~pozitie~~=i) for i in range(~~numar_elemente~~)]		v_forta = [Forta(val=v[i], fr=0, poz=i) for i in range(n)]
	for i in range(~~numar_elemente~~ - 1):		for i in range(n - 1):
	for j in range(i + 1, ~~numar_elemente~~):		for j in range(i + 1, n):
	~~suma_comuna~~ = contor(~~forte~~[i].~~valoare~~, ~~forte~~[j].~~valoare~~)		sm = contor(v_forta[i].val, v_forta[j].val)
	~~forte~~[i].~~frecventa~~ += ~~suma_comuna~~		v_forta[i].fr += sm
	~~forte~~[j].~~frecventa~~ += ~~suma_comuna~~		v_forta[j].fr += sm

	for i in range(~~numar_elemente~~ - 1):		for i in range(n - 1):
	for j in range(i + 1, ~~numar_elemente~~):		for j in range(i + 1, n):
	if ~~forte~~[i].~~frecventa~~ > ~~forte~~[j].~~frecventa~~:		if v_forta[i].fr > v_forta[j].fr:
	~~forte~~[i], ~~forte~~[j] = ~~forte~~[j], ~~forte~~[i]		v_forta[i], v_forta[j] = v_forta[j], v_forta[i]
	elif ~~forte~~[i].~~frecventa~~ == ~~forte~~[j].~~frecventa~~:		elif v_forta[i].fr == v_forta[j].fr:
	if ~~forte~~[i].~~pozitie~~ < ~~forte~~[j].~~pozitie~~:		if v_forta[i].poz < v_forta[j].poz:
	~~forte~~[i], ~~forte~~[j] = ~~forte~~[j], ~~forte~~[i]		v_forta[i], v_forta[j] = v_forta[j], v_forta[i]

	return [forta.~~valoare~~ for forta in ~~forte~~]		return [forta.val for forta in v_forta]


	if __name__ == "__main__":		if __name__ == "__main__":
	with open("forta.in", "r") as fin:		with open("forta.in", "r") as fin:
	~~numar_elemente~~ = int(fin.readline())		n = int(fin.readline())
	~~valori~~ = list(map(int, fin.readline().split()))		v = list(map(int, fin.readline().split()))

	if not validare_date(~~numar_elemente~~, ~~valori~~, distincte=True):		if not validare_date(n, v, distincte=True):
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	exit(0)		exit(0)

	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	rezultat = rezolvare_problema(~~numar_elemente~~, ~~valori~~)		rezultat = rezolvare_problema(n, v)
	with open("forta.out", "w") as fout:		with open("forta.out", "w") as fout:
	fout.write(" ".join(map(str, rezultat)))		fout.write(" ".join(map(str, rezultat)))

Nagy Lenard at 19:54, 7 April 2023

2023-04-07T19:54:48Z

← Older revision		Revision as of 19:54, 7 April 2023
Line 34:		Line 34:
	:11 7 5 3 2		:11 7 5 3 2
	===Exemplul 3===		===Exemplul 3===
	; ''forta.in'		; ''forta.in''
	:4		:4
	:-3 2 3 5		:-3 2 3 5
Line 47:		Line 47:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 3707 - forta1		# 3707 - forta1
	def validare_date(n, v, distincte=False):		def validare_date(numar_elemente, valori, distincte=False):
	if n <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10**18 for x in v):		if numar_elemente <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10 ** 18 for x in valori):
	return False		return False
	if distincte and len(set(v)) != n:		if distincte and len(set(valori)) != numar_elemente:
	return False		return False
	return True		return True


	def rezolvare_problema(n, v):		def rezolvare_problema(numar_elemente, valori):
	class Forta:		class Forta:
	def __init__(self, ~~val~~, fr, ~~poz~~):		def __init__(self, valoare, frecventa, pozitie):
	self.~~val~~ = ~~val~~		self.valoare = valoare
	self.fr = fr		self.frecventa = frecventa
	self.~~poz~~ = ~~poz~~		self.pozitie = pozitie

	def contor(nr1, nr2):		def contor(nr1, nr2):
	~~fr1~~, ~~fr2~~, cnt = [0] * 10, [0] * 10, 0		frecventa1, frecventa2, cnt = [0] * 10, [0] * 10, 0
	while nr1:		while nr1:
	~~fr1~~[nr1 % 10] += 1		frecventa1[nr1 % 10] += 1
	nr1 //= 10		nr1 //= 10
	while nr2:		while nr2:
	~~fr2~~[nr2 % 10] += 1		frecventa2[nr2 % 10] += 1
	nr2 //= 10		nr2 //= 10
	for i in range(10):		for i in range(10):
	if ~~fr1~~[i] and ~~fr2~~[i]:		if frecventa1[i] and frecventa2[i]:
	cnt += min(~~fr1~~[i], ~~fr2~~[i])		cnt += min(frecventa1[i], frecventa2[i])
	return cnt		return cnt

	~~v_forta~~ = [Forta(~~val~~=v[i], fr=0, ~~poz~~=i) for i in range(n)]		forte = [Forta(valoare=valori[i], frecventa=0, pozitie=i) for i in range(numar_elemente)]
	for i in range(n - 1):		for i in range(numar_elemente - 1):
	for j in range(i + 1, n):		for j in range(i + 1, numar_elemente):
	sm = contor(~~v_forta~~[i].~~val~~, ~~v_forta~~[j].~~val~~)		suma_comuna = contor(forte[i].valoare, forte[j].valoare)
	~~v_forta~~[i].fr += sm		forte[i].frecventa += suma_comuna
	~~v_forta~~[j].fr += sm		forte[j].frecventa += suma_comuna

	for i in range(n - 1):		for i in range(numar_elemente - 1):
	for j in range(i + 1, n):		for j in range(i + 1, numar_elemente):
	if ~~v_forta~~[i].fr > ~~v_forta~~[j].fr:		if forte[i].frecventa > forte[j].frecventa:
	~~v_forta~~[i], ~~v_forta~~[j] = ~~v_forta~~[j], ~~v_forta~~[i]		forte[i], forte[j] = forte[j], forte[i]
	elif ~~v_forta~~[i].fr == ~~v_forta~~[j].fr:		elif forte[i].frecventa == forte[j].frecventa:
	if ~~v_forta~~[i].~~poz~~ < ~~v_forta~~[j].~~poz~~:		if forte[i].pozitie < forte[j].pozitie:
	~~v_forta~~[i], ~~v_forta~~[j] = ~~v_forta~~[j], ~~v_forta~~[i]		forte[i], forte[j] = forte[j], forte[i]

	return [forta.~~val~~ for forta in ~~v_forta~~]		return [forta.valoare for forta in forte]


	if __name__ == "__main__":		if __name__ == "__main__":
	with open("forta.in", "r") as fin:		with open("forta.in", "r") as fin:
	n = int(fin.readline())		numar_elemente = int(fin.readline())
	v = list(map(int, fin.readline().split()))		valori = list(map(int, fin.readline().split()))

	if not validare_date(n, v, distincte=True):		if not validare_date(numar_elemente, valori, distincte=True):
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	exit(0)		exit(0)

	print("Datele sunt introduse corect.")		print("Datele sunt introduse corect.")
	rezultat = rezolvare_problema(n, v)		rezultat = rezolvare_problema(numar_elemente, valori)
	with open("forta.out", "w") as fout:		with open("forta.out", "w") as fout:
	fout.write(" ".join(map(str, rezultat)))		fout.write(" ".join(map(str, rezultat)))

Sovago Rares-Andrei: Pagină nouă: ==Cerința== Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1). Se dă un șir cu n elemente numere naturale. Să se sorteze elemente...

2023-04-07T18:16:39Z

Pagină nouă: ==Cerința== Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1). Se dă un șir cu n elemente numere naturale. Să se sorteze elemente...

New page

==Cerința==

Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1).
Se dă un șir cu n elemente numere naturale. Să se sorteze elementele din șir în ordine crescătoare a forței, iar acele elemente care au aceeași forță să apară în ordine inversă decât apăreau inițial în șir.
== Date de intrare ==

Fișierul de intrare '''forta.in''' conține pe prima linie n, numărul de elemente din șir, iar pe a doua linie n numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

== Date de ieșire ==

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire '''forta.out''' va conține pe prima linie, separate prin câte un spațiu, elementele șirului în ordinea cerută. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

== Restricţii şi precizări ==
*1 ≤ n ≤ 1000
*elementele șirului sunt numere naturale mai mici sau egale cu 1018
*pentru teste în valoare de 30 de puncte elementele șirului vor avea forțe distincte
== Exemple ==
===Exemplul 1===
; ''forta.in''
:4
:123 121 12314 1234
; ''ecran''
:Datele sunt introduse corect.
; ''forta.out''
:121 123 1234 12314

===Exemplul 2===
; ''forta.in''
:5
:2 3 5 7 11
; ''ecran''
:Datele sunt introduse corect.
; ''forta.out''
:11 7 5 3 2
===Exemplul 3===
; ''forta.in'
:4
:-3 2 3 5
; ''ecran''
:Datele nu corespund restricțiilor impuse.
; ''forta.out''
:
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 3707 - forta1
def validare_date(n, v, distincte=False):
if n <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10**18 for x in v):
return False
if distincte and len(set(v)) != n:
return False
return True

def rezolvare_problema(n, v):
class Forta:
def __init__(self, val, fr, poz):
self.val = val
self.fr = fr
self.poz = poz

def contor(nr1, nr2):
fr1, fr2, cnt = [0] * 10, [0] * 10, 0
while nr1:
fr1[nr1 % 10] += 1
nr1 //= 10
while nr2:
fr2[nr2 % 10] += 1
nr2 //= 10
for i in range(10):
if fr1[i] and fr2[i]:
cnt += min(fr1[i], fr2[i])
return cnt

v_forta = [Forta(val=v[i], fr=0, poz=i) for i in range(n)]
for i in range(n - 1):
for j in range(i + 1, n):
sm = contor(v_forta[i].val, v_forta[j].val)
v_forta[i].fr += sm
v_forta[j].fr += sm

for i in range(n - 1):
for j in range(i + 1, n):
if v_forta[i].fr > v_forta[j].fr:
v_forta[i], v_forta[j] = v_forta[j], v_forta[i]
elif v_forta[i].fr == v_forta[j].fr:
if v_forta[i].poz < v_forta[j].poz:
v_forta[i], v_forta[j] = v_forta[j], v_forta[i]

return [forta.val for forta in v_forta]

if __name__ == "__main__":
with open("forta.in", "r") as fin:
n = int(fin.readline())
v = list(map(int, fin.readline().split()))

if not validare_date(n, v, distincte=True):
print("Datele nu corespund restricțiilor impuse.")
exit(0)

print("Datele sunt introduse corect.")
rezultat = rezolvare_problema(n, v)
with open("forta.out", "w") as fout:
fout.write(" ".join(map(str, rezultat)))

</syntaxhighlight>

==Explicatie==

validare_date(n, v, distincte=False): Această funcție primește două argumente de intrare, numărul n și lista de numere întregi v, și returnează True dacă acestea sunt valide și False altfel. Verificările includ verificarea ca n să fie un număr întreg pozitiv și ca fiecare element din lista v să fie un număr întreg pozitiv mai mic sau egal cu 10^18. Argumentul opțional distincte specifică dacă toate elementele din lista v trebuie să fie distincte sau nu.

rezolvare_problema(n, v): Această funcție primește două argumente de intrare, numărul n și lista de numere întregi v, și rezolvă problema descrisă în enunțul problemei. Funcția construiește o listă de obiecte Forta pentru fiecare element din lista v, fiecare obiect conținând valoarea elementului val, numărul de perechi de cifre comune cu alte numere din listă fr, și poziția sa în lista poz. Apoi, funcția calculează numărul de perechi de cifre comune pentru fiecare pereche posibilă de numere din listă și actualizează câmpul fr pentru fiecare obiect Forta. La final, lista de obiecte Forta este sortată în ordinea descrescătoare a valorii fr și a poziției poz, și valorile val ale obiectelor sunt extrase într-o listă separată, care este returnată de funcție.

main(): Această funcție este punctul de intrare în program și se ocupă de citirea datelor din fișierul de intrare, apelarea funcției validare_date() pentru a verifica dacă datele sunt valide, apelarea funcției rezolvare_problema() pentru a rezolva problema descrisă în enunțul problemei și afișarea rezultatului în fișierul de ieșire. Dacă datele nu sunt valide, programul se va termina cu exit(0).