2974 - Z Zid - Revision history

Ardelean Alexandru at 14:25, 6 May 2023

2023-05-06T14:25:22Z

← Older revision		Revision as of 14:25, 6 May 2023
Line 63:		Line 63:

	def zzid(inaltime, latime, zid):		def zzid(inaltime, latime, zid):
			# Creeăm un dicționar pentru a stoca frecvența fiecărei sume de segmente de zid
	frecv_sume = {}		frecv_sume = {}
	maxim = 0		maxim = 0
			taietura = 0
	suma_curenta = 0		suma_curenta = 0
	~~taietura = 0~~

			# Iterăm peste fiecare rând de segmente de zid
	for i in range(inaltime):		for i in range(inaltime):
	n = len(zid[i])		lungime = len(zid[i])
			# Iterăm peste fiecare segment din rândul curent
	for j in range(n):		for j in range(lungime):
	b = zid[i][j]		# Adăugăm segmentul curent la suma curentă
	suma_curenta += b		segment = zid[i][j]
			suma_curenta += segment
			# Dacă suma este egală cu lățimea zidului, trecem la următorul segment
	if suma_curenta == latime:		if suma_curenta == latime:
	continue		continue
			# Dacă suma există deja în dicționar...
	if suma_curenta in frecv_sume:		if suma_curenta in frecv_sume:
			# ...incrementăm numărul de apariții
	frecv_sume[suma_curenta] += 1		frecv_sume[suma_curenta] += 1
	else:		else:
			# ...altfel, adăugăm suma în dicționar cu numărul de apariții 1
	frecv_sume[suma_curenta] = 1		frecv_sume[suma_curenta] = 1
			# Dacă numărul de apariții al sumei curente din dicționar este mai mare decât numărul maxim de apariții,
			# actualizăm numărul maxim de apariții și tăietura corespunzătoare
	if frecv_sume[suma_curenta] > maxim:		if frecv_sume[suma_curenta] > maxim:
	maxim = frecv_sume[suma_curenta]		maxim = frecv_sume[suma_curenta]
	taietura = suma_curenta		taietura = suma_curenta
			# Dacă numărul de apariții al sumei curente din dicționar este egal cu numărul maxim de apariții și
			# tăietura curentă este mai aproape de lățimea dorită a zidului decât tăietura anterioară, actualizăm
			# tăietura corespunzătoare
	if frecv_sume[suma_curenta] == maxim and abs(latime - taietura - taietura) > abs(latime - suma_curenta - suma_curenta):		if frecv_sume[suma_curenta] == maxim and abs(latime - taietura - taietura) > abs(latime - suma_curenta - suma_curenta):
	taietura = suma_curenta		taietura = suma_curenta
			# Resetăm suma curentă pentru următorul rând
	suma_curenta = 0		suma_curenta = 0

			# Printăm numărul minim de rânduri care trebuie tăiate și tăietura corespunzătoare
	print(f"{inaltime-maxim} {abs(taietura-latime+taietura)}")		print(f"{inaltime-maxim} {abs(taietura-latime+taietura)}")

Ardelean Alexandru at 14:07, 29 April 2023

2023-04-29T14:07:00Z

← Older revision		Revision as of 14:07, 29 April 2023
Line 30:		Line 30:
	:3 2 3 5		:3 2 3 5
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:1 0		:1 0

Ardelean Alexandru at 13:51, 29 April 2023

2023-04-29T13:51:15Z

← Older revision		Revision as of 13:51, 29 April 2023
Line 61:		Line 61:


	def ~~taierie_diferenta~~(inaltime, latime, zid):		def zzid(inaltime, latime, zid):
	frecv_sume = {}		frecv_sume = {}
	maxim = 0		maxim = 0
Line 86:		Line 86:
	suma_curenta = 0		suma_curenta = 0

	~~return~~ f"{inaltime-maxim} {abs(taietura-latime+taietura)}"		print(f"{inaltime-maxim} {abs(taietura-latime+taietura)}")


	~~def main()~~:		if __name__ == "__main__":
	inaltime, latime = [int(x) for x in input().split()]		inaltime, latime = [int(x) for x in input().split()]

Line 99:		Line 99:

	if not conditii(inaltime, latime, zid):		if not conditii(inaltime, latime, zid):
	~~return~~ print("Datele de intrare nu corespund restricțiilor impuse.")		print("Datele de intrare nu corespund restricțiilor impuse.")
	print("Datele de intrare corespund restricțiilor impuse.")		else:
			print("Datele de intrare corespund restricțiilor impuse.")
	~~print(taierie_diferenta~~(inaltime, latime, zid))		zzid(inaltime, latime, zid)


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

	</syntaxhighlight>		</syntaxhighlight>

Ardelean Alexandru at 11:07, 26 March 2023

2023-03-26T11:07:22Z

← Older revision		Revision as of 11:07, 26 March 2023
Line 42:		Line 42:
	:3 2 5 5		:3 2 5 5
	;Ieșire		;Ieșire
	:~~Date~~ de intrare ~~gresite!~~		:Datele de intrare nu corespund restricțiilor impuse.

	==Rezolvare==		==Rezolvare==

Ardelean Alexandru at 10:46, 26 March 2023

2023-03-26T10:46:05Z

← Older revision		Revision as of 10:46, 26 March 2023
Line 7:		Line 7:
	Fișierul de intrare <code>zzid.in</code> conține pe prima linie numerele <code>H</code> și <code>W</code>. Pe fiecare din următoarele <code>H</code> linii va fi descris un rând al zidului în felul următor: un număr <code>Ni</code>, reprezentând numărul de cărămizi de pe rândul <code>i</code>, urmat de <code>Ni</code> numere, reprezentând lățimea cărămizilor de pe rândul <code>i</code>, în ordinea în care apar. Suma lățimilor cărămizilor de pe fiecare rând este egală cu <code>W</code>. Toate numerele din fișierul de intrare sunt naturale.		Fișierul de intrare <code>zzid.in</code> conține pe prima linie numerele <code>H</code> și <code>W</code>. Pe fiecare din următoarele <code>H</code> linii va fi descris un rând al zidului în felul următor: un număr <code>Ni</code>, reprezentând numărul de cărămizi de pe rândul <code>i</code>, urmat de <code>Ni</code> numere, reprezentând lățimea cărămizilor de pe rândul <code>i</code>, în ordinea în care apar. Suma lățimilor cărămizilor de pe fiecare rând este egală cu <code>W</code>. Toate numerele din fișierul de intrare sunt naturale.
	==Date de ieșire==		==Date de ieșire==
	~~Fișierul~~ de ~~ieșire <code>zzid~~.~~out</code> conține o singură linie cu~~ două numere naturale separate printr-un spațiu: numărul minim necesar de cărămizi ce trebuie tăiate astfel încât să se taie zidul în două bucăți, respectiv diferența minimă dintre cele două lățimi ale zidurilor.		Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

			Pe următorul rând se vor afișa două numere naturale separate printr-un spațiu: numărul minim necesar de cărămizi ce trebuie tăiate astfel încât să se taie zidul în două bucăți, respectiv diferența minimă dintre cele două lățimi ale zidurilor.

			În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

	==Restricții și precizări==		==Restricții și precizări==
Line 95:		Line 99:

	if not conditii(inaltime, latime, zid):		if not conditii(inaltime, latime, zid):
	return print("~~Date~~ de intrare ~~gresite!~~")		return print("Datele de intrare nu corespund restricțiilor impuse.")
			print("Datele de intrare corespund restricțiilor impuse.")

	print(taierie_diferenta(inaltime, latime, zid))		print(taierie_diferenta(inaltime, latime, zid))

Ardelean Alexandru: Pagină nouă: ==Cerința== Fie un zid perfect dreptunghiular de înălțime `H` și lățime `W`, format din cărămizi de înălțime `1` și lățime variabilă, lipite între ele. Să se taie acest zid pe verticală astfel încât numărul de cărămizi ce trebuie tăiate să fie minim. În cazul în care există mai multe astfel de locuri unde poate fi tăiat zidul, se dorește ca diferența lățimilor celor două bucăți obținute să fie cât mai m...

2023-03-22T06:57:06Z

Pagină nouă: ==Cerința== Fie un zid perfect dreptunghiular de înălțime <code>H</code> și lățime <code>W</code>, format din cărămizi de înălțime <code>1</code> și lățime variabilă, lipite între ele. Să se taie acest zid pe verticală astfel încât numărul de cărămizi ce trebuie tăiate să fie minim. În cazul în care există mai multe astfel de locuri unde poate fi tăiat zidul, se dorește ca diferența lățimilor celor două bucăți obținute să fie cât mai m...

New page

==Cerința==
Fie un zid perfect dreptunghiular de înălțime <code>H</code> și lățime <code>W</code>, format din cărămizi de înălțime <code>1</code> și lățime variabilă, lipite între ele.

Să se taie acest zid pe verticală astfel încât numărul de cărămizi ce trebuie tăiate să fie minim. În cazul în care există mai multe astfel de locuri unde poate fi tăiat zidul, se dorește ca diferența lățimilor celor două bucăți obținute să fie cât mai mică.

==Date de intrare==
Fișierul de intrare <code>zzid.in</code> conține pe prima linie numerele <code>H</code> și <code>W</code>. Pe fiecare din următoarele <code>H</code> linii va fi descris un rând al zidului în felul următor: un număr <code>Ni</code>, reprezentând numărul de cărămizi de pe rândul <code>i</code>, urmat de <code>Ni</code> numere, reprezentând lățimea cărămizilor de pe rândul <code>i</code>, în ordinea în care apar. Suma lățimilor cărămizilor de pe fiecare rând este egală cu <code>W</code>. Toate numerele din fișierul de intrare sunt naturale.
==Date de ieșire==
Fișierul de ieșire <code>zzid.out</code> conține o singură linie cu două numere naturale separate printr-un spațiu: numărul minim necesar de cărămizi ce trebuie tăiate astfel încât să se taie zidul în două bucăți, respectiv diferența minimă dintre cele două lățimi ale zidurilor.

==Restricții și precizări==

* <code>2 ≤ W ≤ 1.000.000.000</code>
* <code>2 ≤ H ≤ 100.000</code>

* Sunt maximum <code>1.000.000</code> cărămizi
* Pentru <code>30%</code> din teste <code>H</code> si <code>W</code> sunt mai mici decât <code>1000</code>
* Pentru alte <code>20%</code> din teste <code>H ≤ 1000</code>
* Zidul nu poate fi rotit

==Exemplu 1==
;Intrare
:3 10
:1 10
:2 5 5
:3 2 3 5
;Ieșire
:1 0

===Explicație===
Zidul se poate tăia fix la jumătate, și doar cărămida de pe primul rând trebuie tăiată.

==Exemplu 2==
;Intrare
:3 10
:1 10
:2 5 0
:3 2 5 5
;Ieșire
:Date de intrare gresite!

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2974 Z Zid
def conditii(inaltime, latime, zid):
if not 2 <= latime <= 1_000_000_000:
return False

if not 2 <= inaltime <= 100_000:
return False

for rand in range(len(zid)):
if not sum(zid[rand]) == latime:
return False

return True

def taierie_diferenta(inaltime, latime, zid):
frecv_sume = {}
maxim = 0
suma_curenta = 0
taietura = 0

for i in range(inaltime):
n = len(zid[i])

for j in range(n):
b = zid[i][j]
suma_curenta += b
if suma_curenta == latime:
continue
if suma_curenta in frecv_sume:
frecv_sume[suma_curenta] += 1
else:
frecv_sume[suma_curenta] = 1
if frecv_sume[suma_curenta] > maxim:
maxim = frecv_sume[suma_curenta]
taietura = suma_curenta
if frecv_sume[suma_curenta] == maxim and abs(latime - taietura - taietura) > abs(latime - suma_curenta - suma_curenta):
taietura = suma_curenta
suma_curenta = 0

return f"{inaltime-maxim} {abs(taietura-latime+taietura)}"

def main():
inaltime, latime = [int(x) for x in input().split()]

zid = []

for i in range(inaltime):
latimi = [int(x) for x in input().split()[1:]]
zid.append(latimi)

if not conditii(inaltime, latime, zid):
return print("Date de intrare gresite!")

print(taierie_diferenta(inaltime, latime, zid))

if __name__ == "__main__":
main()

</syntaxhighlight>