2650 - books - Revision history

Hotico Iulia Denisa: /* Restricții și precizări */

2023-11-18T15:34:36Z

Restricții și precizări

← Older revision		Revision as of 15:34, 18 November 2023
Line 18:		Line 18:

	*'''1 ≤''' a1,a2,…,an,b1,b2,…,bn '''≤ n ≤ 200.000''';		*'''1 ≤''' a1,a2,…,an,b1,b2,…,bn '''≤ n ≤ 200.000''';
	*Numerele a1,a2,…,an sunt distincte între ele;		*Numerele '''a1,a2,…,an''' sunt distincte între ele;
	*Numerele b1,b2,…,bn sunt distincte între ele.		*Numerele '''b1,b2,…,bn''' sunt distincte între ele.

	==Exemplul 1:==		==Exemplul 1:==

Hotico Iulia Denisa: /* Date de intrare */

2023-11-18T15:33:49Z

Date de intrare

← Older revision		Revision as of 15:33, 18 November 2023
Line 9:		Line 9:
	==Date de intrare==		==Date de intrare==

	Prima linie va conține numărul n, cu semnificația din enunț. Următoarea linie va conține n numere întregi, anume a1,a2,…,an. A treia linie va conține alte n numere întregi, anume b1,b2,…,bn.		Prima linie va conține numărul n, cu semnificația din enunț. Următoarea linie va conține n numere întregi, anume '''a1,a2,…,an'''. A treia linie va conține alte n numere întregi, anume '''b1,b2,…,bn'''.

	==Date de ieșire==		==Date de ieșire==

Bonte Lucas Gabriel at 15:31, 12 November 2023

2023-11-12T15:31:21Z

← Older revision		Revision as of 15:31, 12 November 2023
Line 31:		Line 31:
	;Ieșire		;Ieșire

			:Datele de intrare corespund restrictiilor impuse.
	:2 0 1		:2 0 1

Line 42:		Line 43:

	;Ieșire		;Ieșire
			:Datele de intrare corespund restrictiilor impuse.
	:3 2 0 0 0		:3 2 0 0 0

Line 52:		Line 53:
	:6 5 4 3 2 1		:6 5 4 3 2 1
	:6 5 3 4 2 1		:6 5 3 4 2 1

			;Ieșire
			:Datele de intrare corespund restrictiilor impuse.
			:1 1 2 0 1 1


			==Exemplul 4:==

			;Intrare

			:0

	;Ieșire		;Ieșire

	:~~1 1 2 0 1 1~~		:Datele de intrare nu corespund restrictiilor impuse.

	==Rezolvare==		==Rezolvare==
Line 61:		Line 73:
	<syntaxhighlight lang="python" line="1" start="1">		<syntaxhighlight lang="python" line="1" start="1">

	def muta_carti(n, a~~, b~~):		def verificare_restrictii(nr_n):
			# Functia de verificare a datelor de intrare
			if 1 <= nr_n <= 200000:
			return True
			else:
			return False


			def muta_carti(nr_n, nr_a, nr_b):
			# Verificam daca numerele sunt distincte
			if len(set(a)) != nr_n or len(set(nr_b)) != nr_n:
			return "Numerele nu sunt distincte între ele."

	# Creăm un array poz cu lungimea n + 1		# Creăm un array poz cu lungimea n + 1
	poz = [0] * (n + 1)		poz = [0] * (nr_n + 1)

	# Parcurgem array-ul a și pentru fiecare element a[i], setăm poz[a[i]] la i + 1		# Parcurgem array-ul a și pentru fiecare element a[i], setăm poz[a[i]] la i + 1
	for i in range(n):		for i in range(nr_n):
	poz[a[i]] = i + 1		poz[nr_a[i]] = i + 1

	# Inițializăm rezultatul ca un array gol		# Inițializăm rezultatul ca un array gol
Line 76:		Line 100:

	# Parcurgem array-ul b		# Parcurgem array-ul b
	for i in range(n):		for i in range(nr_n):
	# Dacă poz[b[i]] este mai mare decât max_poz, adăugăm diferența la rezultat și actualizăm max_poz		# Dacă poz[b[i]] este mai mare decât max_poz, adăugăm diferența la rezultat și actualizăm max_poz
	if poz[b[i]] > max_poz:		if poz[nr_b[i]] > max_poz:
	rez.append(poz[b[i]] - max_poz)		rez.append(poz[b[i]] - max_poz)
	max_poz = poz[b[i]]		max_poz = poz[b[i]]
Line 87:		Line 111:
	# Returnăm rezultatul		# Returnăm rezultatul
	return rez		return rez


	if __name__ == "__main__":		if __name__ == "__main__":
	# Introdu datele de intrare manual		try:
	n = int(input("Introdu numărul de cărți: "))		# Introdu datele de intrare manual
			n = int(input("Introdu numărul de cărți: "))

			# Verificam daca datele de intrare corespund restrictiilor
			if verificare_restrictii(n):
			print("Datele de intrare corespund restrictiilor impuse.")

	# Convertim string-ul de intrare într-un array de numere întregi		# Convertim string-ul de intrare într-un array de numere întregi
	a = list(map(int, input("Introdu ordinea cărților în stack: ").split()))		a = list(map(int, input("Introdu ordinea cărților în stack: ").split()))

	# Convertim string-ul de intrare într-un array de numere întregi		# Convertim string-ul de intrare într-un array de numere întregi
	b = list(map(int, input("Introdu ordinea în care vrei să muți cărțile: ").split()))		b = list(map(int, input("Introdu ordinea în care vrei să muți cărțile: ").split()))

	# Afișează rezultatul		# Afișează rezultatul
	print(muta_carti(n, a, b))		print(muta_carti(n, a, b))
			else:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			except ValueError:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			except IndexError:
			print("Datele de intrare nu corespund restrictiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>

Bonte Lucas Gabriel: Pagină nouă: Eroul nostru, Căldărușe, are un număr '''n''' de cărți pe care le are aranjate una peste cealaltă (sub forma unui '''stack'''). Cartea din vârf are valoarea '''a1''', următoarea '''a2''' și așa mai departe. Cartea de la bază are indicele '''n''' (an). '''Toate numerele sunt distincte.''' Căldărușe vrea să mute toate cărțile în ghiozdanul lui în exact '''n''' pași. În timpul pasului de ordin '''i''', el vrea să mute cartea cu numărul bi în ghiozdan. D...

2023-10-30T14:07:44Z

Pagină nouă: Eroul nostru, Căldărușe, are un număr '''n''' de cărți pe care le are aranjate una peste cealaltă (sub forma unui '''stack'''). Cartea din vârf are valoarea '''a1''', următoarea '''a2''' și așa mai departe. Cartea de la bază are indicele '''n''' (an). '''Toate numerele sunt distincte.''' Căldărușe vrea să mute toate cărțile în ghiozdanul lui în exact '''n''' pași. În timpul pasului de ordin '''i''', el vrea să mute cartea cu numărul bi în ghiozdan. D...

New page

Eroul nostru, Căldărușe, are un număr '''n''' de cărți pe care le are aranjate una peste cealaltă (sub forma unui '''stack'''). Cartea din vârf are valoarea '''a1''', următoarea '''a2''' și așa mai departe. Cartea de la bază are indicele '''n''' (an). '''Toate numerele sunt distincte.'''

Căldărușe vrea să mute toate cărțile în ghiozdanul lui în exact '''n''' pași. În timpul pasului de ordin '''i''', el vrea să mute cartea cu numărul bi în ghiozdan. Dacă această carte se află în stack, el o ia atât pe ea, cât și toate cărțile situate deasupra acesteia și le pune în ghiozdan; în caz contrar, el nu va face nimic și va trece la următorul pas. De exemplu, dacă în stack cărțile sunt aranjate în ordinea '''[1, 2, 3]''' (cartea cu numărul '''1''' este aflată în vârf) și pașii prin care Căldărușe trece sunt, în această ordine, '''[2, 1, 3]''', atunci în cadrul primului pas el va muta două cărți (1 și 2), în cadrul celui de-al doilea pas nu va face nimic (din moment ce cartea cu numărul 1 este deja în ghiozdan) și în cadrul ultimului pas va muta o singură carte (cartea cu numărul '''3''').

==Cerința==

Ajutați-l pe Căldărușe! Spuneți-i voi numărul de cărți pe care le va pune în ghiozdan în timpul fiecărui pas.

==Date de intrare==

Prima linie va conține numărul n, cu semnificația din enunț. Următoarea linie va conține n numere întregi, anume a1,a2,…,an. A treia linie va conține alte n numere întregi, anume b1,b2,…,bn.

==Date de ieșire==

Programul va afișa pe ecran '''n''' numere întregi. Elementul de ordine '''i''' ar trebui să fie egal cu numărul de cărți pe care Căldărușe le mută în ghiozdanul său în timpul pasului '''i'''.

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

*'''1 ≤''' a1,a2,…,an,b1,b2,…,bn '''≤ n ≤ 200.000''';
*Numerele a1,a2,…,an sunt distincte între ele;
*Numerele b1,b2,…,bn sunt distincte între ele.

==Exemplul 1:==

;Intrare

:3
:1 2 3
:2 1 3

;Ieșire

:2 0 1

==Exemplul 2:==

;Intrare

:5
:3 1 4 2 5
:4 5 1 3 2

;Ieșire

:3 2 0 0 0

==Exemplul 3:==

;Intrare

:6
:6 5 4 3 2 1
:6 5 3 4 2 1

;Ieșire

:1 1 2 0 1 1

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

def muta_carti(n, a, b):
# Creăm un array poz cu lungimea n + 1
poz = [0] * (n + 1)

# Parcurgem array-ul a și pentru fiecare element a[i], setăm poz[a[i]] la i + 1
for i in range(n):
poz[a[i]] = i + 1

# Inițializăm rezultatul ca un array gol
rez = []

# Inițializăm max_poz la 0
max_poz = 0

# Parcurgem array-ul b
for i in range(n):
# Dacă poz[b[i]] este mai mare decât max_poz, adăugăm diferența la rezultat și actualizăm max_poz
if poz[b[i]] > max_poz:
rez.append(poz[b[i]] - max_poz)
max_poz = poz[b[i]]
else:
# Altfel, adăugăm 0 la rezultat
rez.append(0)

# Returnăm rezultatul
return rez

if __name__ == "__main__":
# Introdu datele de intrare manual
n = int(input("Introdu numărul de cărți: "))

# Convertim string-ul de intrare într-un array de numere întregi
a = list(map(int, input("Introdu ordinea cărților în stack: ").split()))

# Convertim string-ul de intrare într-un array de numere întregi
b = list(map(int, input("Introdu ordinea în care vrei să muți cărțile: ").split()))

# Afișează rezultatul
print(muta_carti(n, a, b))

</syntaxhighlight>

==Explicație==

Primul exemplu este descris în enunț. În cel de-al doilea exemplu, în timpul primului pas, Căldărușe va muta cărțile '''[3, 1, 4]'''. După aceea, numai cărțile '''2''' și '''5''' vor rămâne în stack (cartea '''2''' fiind deasupra cărții '''5'''). În timpul celui de-al doilea pas, Căldărușe va lua și cărțile '''2''' și '''5'''. După aceea, stackul rămâne gol, și deci în timpul următorilor pași, Căldărușe nu va mai muta nicio carte.