2115 - Prajituri - Revision history

Ardelean Alexandru at 14:36, 6 May 2023

2023-05-06T14:36:33Z

← Older revision		Revision as of 14:36, 6 May 2023
Line 83:		Line 83:


	def prajituri(straturi_ilinca, straturi_daria):		def prajituri(n, m, straturi_ilinca, straturi_daria):
			# Ținem cont de frecvența fiecărui element din cele două liste
	frecv_ilinca = [0] * 101		frecv_ilinca = [0] * 101
	frecv_daria = [0] * 101		frecv_daria = [0] * 101

			# Calculăm frecvența fiecărui element din cele două liste folosind lungimea listelor (n și m)
	for i in range(n):		for i in range(n):
	frecv_ilinca[straturi_ilinca[i]] += 1		frecv_ilinca[straturi_ilinca[i]] += 1
Line 93:		Line 96:
	nr, stanga, dreapta, ok = 0, -1, 0, 1		nr, stanga, dreapta, ok = 0, -1, 0, 1

			# Iterăm toate pozițiile de început posibile pentru straturi_daria în straturi_ilinca
	i = 0		i = 0
	while i <= n - m:		while i <= n - m:
	ok = 1		ok = 1
			# Verificăm dacă subșirul curent din straturi_ilinca coincide cu cu straturi_daria
	for j in range(m):		for j in range(m):
	if straturi_ilinca[i + j] != straturi_daria[j]:		if straturi_ilinca[i + j] != straturi_daria[j]:
	ok = 0		ok = 0
	break		break

			# Dacă da, actualizăm variabilele folosite pentru a calcula numărul de apariții
			# ale lui straturi_daria în straturi_ilinca
	if ok:		if ok:
	nr += 1		nr += 1
Line 105:		Line 113:
	stanga, dreapta = i, n - m - i		stanga, dreapta = i, n - m - i
	i += m		i += m
			# Dacă nu, trecem la următorul subșir din straturi_ilinca
	else:		else:
	i += 1		i += 1

			# Calculăm numărul de apariții ale lui straturi_daria în straturi_ilinca găsind numărul minim de apariții
			# ale fiecărui element din straturi_daria în straturi_ilinca
	aparitii = n		aparitii = n
	for i in range(1, 101):		for i in range(1, 101):
Line 127:		Line 138:
	else:		else:
	print("Datele de intrare corespund restricțiilor impuse.")		print("Datele de intrare corespund restricțiilor impuse.")
	prajituri(straturi_ilinca, straturi_daria)		prajituri(n, m, straturi_ilinca, straturi_daria)

	</syntaxhighlight>		</syntaxhighlight>

Ardelean Alexandru at 14:05, 29 April 2023

2023-04-29T14:05:54Z

← Older revision		Revision as of 14:05, 29 April 2023
Line 36:		Line 36:
	:6 2 2		:6 2 2
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:0 2		:0 2
	:1		:1
Line 49:		Line 50:
	:6 8		:6 8
	;Ieșire		;Ieșire
			:Datele de intrare corespund restricțiilor impuse.
	:1 7		:1 7
	:3		:3

Ardelean Alexandru at 13:46, 29 April 2023

2023-04-29T13:46:18Z

← Older revision		Revision as of 13:46, 29 April 2023
Line 81:		Line 81:


	def ~~main~~():		def prajituri(straturi_ilinca, straturi_daria):
	~~n, m = [int(x) for x in input().split()]~~
	~~straturi_ilinca = [int(x) for x in input().split()]~~
	~~straturi_daria = [int(x) for x in input().split()]~~

	~~if not conditii(n, m,~~ straturi_ilinca, straturi_daria):
	~~return print("Datele de intrare nu corespund restricțiilor impuse.")~~
	~~print("Datele de intrare corespund restricțiilor impuse.")~~

	frecv_ilinca = [0] * 101		frecv_ilinca = [0] * 101
	frecv_daria = [0] * 101		frecv_daria = [0] * 101
Line 109:		Line 101:
	nr += 1		nr += 1
	if stanga == -1:		if stanga == -1:
	stanga, dreapta = i, n-m-i		stanga, dreapta = i, n - m - i
	i += m		i += m
	else:		else:
Line 125:		Line 117:

	if __name__ == "__main__":		if __name__ == "__main__":
	~~main~~()		n, m = [int(x) for x in input().split()]
			straturi_ilinca = [int(x) for x in input().split()]
			straturi_daria = [int(x) for x in input().split()]

			if not conditii(n, m, straturi_ilinca, straturi_daria):
			print("Datele de intrare nu corespund restricțiilor impuse.")
			else:
			print("Datele de intrare corespund restricțiilor impuse.")
			prajituri(straturi_ilinca, straturi_daria)

	</syntaxhighlight>		</syntaxhighlight>

Ardelean Alexandru at 11:05, 26 March 2023

2023-03-26T11:05:33Z

← Older revision		Revision as of 11:05, 26 March 2023
Line 62:		Line 62:
	:101 0		:101 0
	;Ieșire		;Ieșire
	:~~Date~~ de intrare ~~gresite!~~		:Datele de intrare nu corespund restricțiilor impuse.

	==Rezolvare==		==Rezolvare==

Ardelean Alexandru at 10:39, 26 March 2023

2023-03-26T10:39:13Z

← Older revision		Revision as of 10:39, 26 March 2023
Line 16:		Line 16:
	Fişierul de intrare <code>prajituri.in</code> conţine pe prima linie numerele naturale <code>N M</code> reprezentând numărul de straturi din prăjitura Ilincăi, respectiv a Dariei. A doua linie a fişierului conţine, în ordine, cele <code>N</code> numere <code>a1,a2,...,aN</code>, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Ilincăi. A treia linie a fişierului conţine, în ordine, cele <code>M</code> numere <code>b1,b2,...,bM</code>, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Dariei.		Fişierul de intrare <code>prajituri.in</code> conţine pe prima linie numerele naturale <code>N M</code> reprezentând numărul de straturi din prăjitura Ilincăi, respectiv a Dariei. A doua linie a fişierului conţine, în ordine, cele <code>N</code> numere <code>a1,a2,...,aN</code>, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Ilincăi. A treia linie a fişierului conţine, în ordine, cele <code>M</code> numere <code>b1,b2,...,bM</code>, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Dariei.
	==Date de ieșire==		==Date de ieșire==
	~~Fişierul~~ de ~~ieşire <code>prajituri~~.~~out</code> va conţine pe prima linie~~ două numere, separate printr-un spaţiu, reprezentând numărul de straturi tăiate din stânga, respectiv numărul de straturi tăiate din dreapta din prăjitura Ilincăi la prima extragere, separate prin spaţiu. ~~A doua linie~~ va conţine un număr natural reprezentând numărul de prăjituri aflate pe farfurie după efectuarea tuturor extragerilor. ~~A treia linie~~ va conţine un număr natural reprezentând numărul maxim de prăjituri la fel ca prăjitura Dariei care se pot obţine din prăjitura Ilincăi dacă aceasta ar rearanja convenabil straturile prăjiturii ei.		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, separate printr-un spaţiu, reprezentând numărul de straturi tăiate din stânga, respectiv numărul de straturi tăiate din dreapta din prăjitura Ilincăi la prima extragere, separate prin spaţiu. Al treilea rând va conţine un număr natural reprezentând numărul de prăjituri aflate pe farfurie după efectuarea tuturor extragerilor. Al patrulea rând va conţine un număr natural reprezentând numărul maxim de prăjituri la fel ca prăjitura Dariei care se pot obţine din prăjitura Ilincăi dacă aceasta ar rearanja convenabil straturile prăjiturii ei.

			Î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 83:		Line 87:

	if not conditii(n, m, straturi_ilinca, straturi_daria):		if not conditii(n, m, straturi_ilinca, straturi_daria):
	return print("~~Date~~ de intrare ~~gresite!~~")		return print("Datele de intrare nu corespund restricțiilor impuse.")
			print("Datele de intrare corespund restricțiilor impuse.")

	frecv_ilinca = [0] * 101		frecv_ilinca = [0] * 101

Ardelean Alexandru: Pagină nouă: ==Cerința== Ilinca şi verişoara ei Daria, merg la un curs de gătit. Ilinca a făcut o prăjitură cu `N` straturi, iar Daria a făcut o prăjitură cu `M` straturi, straturile prăjiturilor fiind aşezate unul după altul pe orizontală şi având diverse culori. E posibil ca unele straturi din prăjitură să aibă aceeaşi culoare. Ilinca a observat că dacă ar tăia prăjitura ei la capete ar putea obţine o prăjitură la fel ca prăjitura Dar...

2023-03-21T12:27:16Z

Pagină nouă: ==Cerința== Ilinca şi verişoara ei Daria, merg la un curs de gătit. Ilinca a făcut o prăjitură cu <code>N</code> straturi, iar Daria a făcut o prăjitură cu <code>M</code> straturi, straturile prăjiturilor fiind aşezate unul după altul pe orizontală şi având diverse culori. E posibil ca unele straturi din prăjitură să aibă aceeaşi culoare. Ilinca a observat că dacă ar tăia prăjitura ei la capete ar putea obţine o prăjitură la fel ca prăjitura Dar...

New page

==Cerința==
Ilinca şi verişoara ei Daria, merg la un curs de gătit. Ilinca a făcut o prăjitură cu <code>N</code> straturi, iar Daria a făcut o prăjitură cu <code>M</code> straturi, straturile prăjiturilor fiind aşezate unul după altul pe orizontală şi având diverse culori. E posibil ca unele straturi din prăjitură să aibă aceeaşi culoare.

Ilinca a observat că dacă ar tăia prăjitura ei la capete ar putea obţine o prăjitură la fel ca prăjitura Dariei. Ilinca spune că astfel „extrage” din prăjitura ei prăjitura Dariei. La o extragere, Ilinca taie întotdeauna un număr minim de straturi din partea stângă (straturi pe care le mănâncă imediat) şi câte straturi sunt necesare în partea dreaptă pentru a obţine o prăjitură identică cu prăjitura Dariei. Prăjitura extrasă o aşază pe o farfurie şi continuă „extragerile” din bucata rămasă în partea dreaptă.

Scrieţi un program care să citească numerele naturale <code>N</code> şi <code>M</code> (reprezentând numărul de straturi din prăjitura Ilincăi respectiv Dariei) şi <code>a1,a2,...,aN</code> şi <code>b1,b2,...,bM</code> (reprezentând culorile straturilor din prăjitura Ilincăi respectiv din prăjitura Dariei) şi care să determine:

a) numărul de straturi pe care le taie Ilinca din capătul din stânga şi numărul de straturi pe care le taie din capătul din dreapta la prima extragere;

b) numărul de prăjituri identice cu prăjitura Dariei care se vor afla pe farfurie, după efectuarea tuturor extragerilor;

c) numărul maxim de prăjituri la fel ca prăjitura Dariei care pot fi obţinute din prăjitura Ilincăi dacă aceasta ar rearanja straturile prăjiturii ei într-o ordine convenabilă.

==Date de intrare==
Fişierul de intrare <code>prajituri.in</code> conţine pe prima linie numerele naturale <code>N M</code> reprezentând numărul de straturi din prăjitura Ilincăi, respectiv a Dariei. A doua linie a fişierului conţine, în ordine, cele <code>N</code> numere <code>a1,a2,...,aN</code>, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Ilincăi. A treia linie a fişierului conţine, în ordine, cele <code>M</code> numere <code>b1,b2,...,bM</code>, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Dariei.
==Date de ieșire==
Fişierul de ieşire <code>prajituri.out</code> va conţine pe prima linie două numere, separate printr-un spaţiu, reprezentând numărul de straturi tăiate din stânga, respectiv numărul de straturi tăiate din dreapta din prăjitura Ilincăi la prima extragere, separate prin spaţiu. A doua linie va conţine un număr natural reprezentând numărul de prăjituri aflate pe farfurie după efectuarea tuturor extragerilor. A treia linie va conţine un număr natural reprezentând numărul maxim de prăjituri la fel ca prăjitura Dariei care se pot obţine din prăjitura Ilincăi dacă aceasta ar rearanja convenabil straturile prăjiturii ei.

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

* <code>1 ≤ M ≤ N ≤ 10.000</code>
* <code>1 ≤ ai ≤ 100, (1 ≤ i ≤ N)</code>
* <code>1 ≤ bi ≤ 100, (1 ≤ i ≤ M)</code>
* <code>N, M, a1, a2, ..., aN, b1, b2, ..., bM sunt numere naturale;</code>
* <code>Întotdeauna se poate obţine din prăjitura Ilincăi cel puţin o prăjitură la fel ca prăjitura Dariei</code>

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

===Explicație===
Prăjitura Ilincăi are <code>5</code> straturi, iar a Dariei <code>3</code> straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga <code>0</code> straturi şi din dreapta <code>2</code> straturi, se poate obţine doar o prăjitură ca a Dariei indiferent de procedeul folosit

==Exemplu 2==
;Intrare
:10 2
:5 6 8 8 6 8 6 8 6 6
:6 8
;Ieșire
:1 7
:3
:4

===Explicație===
Prăjitura Ilincăi are <code>10</code> straturi, iar a Dariei <code>2</code> straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga <code>1</code> strat şi din dreapta <code>7</code> straturi. Prin procedeul de tăiere se pot obţine <code>3</code> prăjituri la fel ca prăjitura Dariei. Prin rearanjarea straturilor se pot obţine maxim <code>4</code> prăjituri la fel ca prăjitura Dariei.

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

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2115 Prajituri

def conditii(n, m, straturi_ilinca, straturi_daria):
if not 1 <= m <= n <= 10_000:
return False
for i in range(n):
if not 1 <= straturi_ilinca[i] <= 100:
return False
for i in range(m):
if not 1 <= straturi_daria[i] <= 100:
return False

return True

def main():
n, m = [int(x) for x in input().split()]
straturi_ilinca = [int(x) for x in input().split()]
straturi_daria = [int(x) for x in input().split()]

if not conditii(n, m, straturi_ilinca, straturi_daria):
return print("Date de intrare gresite!")

frecv_ilinca = [0] * 101
frecv_daria = [0] * 101
for i in range(n):
frecv_ilinca[straturi_ilinca[i]] += 1
for i in range(m):
frecv_daria[straturi_daria[i]] += 1

nr, stanga, dreapta, ok = 0, -1, 0, 1

i = 0
while i <= n - m:
ok = 1
for j in range(m):
if straturi_ilinca[i + j] != straturi_daria[j]:
ok = 0
break
if ok:
nr += 1
if stanga == -1:
stanga, dreapta = i, n-m-i
i += m
else:
i += 1

aparitii = n
for i in range(1, 101):
if frecv_daria[i] != 0:
aparitii = min(aparitii, frecv_ilinca[i] // frecv_daria[i])

print(f"{stanga} {dreapta}")
print(nr)
print(aparitii)

if __name__ == "__main__":
main()

</syntaxhighlight>