2818 - Inserare 2 - Revision history

Sovago Rares-Andrei: /* Date de ieșire */

2023-04-29T16:41:54Z

Date de ieșire

← Older revision		Revision as of 16:41, 29 April 2023
Line 9:		Line 9:
	== Date de ieșire ==		== Date de ieșire ==
	Dacă datele sunt introduse corect, pe ecran:		Dacă datele sunt introduse corect, pe ecran:
	"Datele sunt introduse corect.",fișierul de ieșire inserare2.out va conține poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".		"Datele sunt introduse corect.",fișierul de ieșire '''inserare2.out''' va conține poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	*Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei necesare și al timpului de executare.		*Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei necesare și al timpului de executare.

Sovago Rares-Andrei at 05:33, 15 April 2023

2023-04-15T05:33:45Z

← Older revision		Revision as of 05:33, 15 April 2023
Line 98:		Line 98:

	</syntaxhighlight>		</syntaxhighlight>

			==Explicatie==
			Funcția validate_input(n, m, A, B) verifică dacă datele de intrare sunt valide, adică:

			n și m sunt numere întregi între 1 și 10^6;
			lungimea listelor A și B este respectiv n și m;
			listele A și B sunt strict crescătoare, adică fiecare element este mai mic decât elementul următor.
			Funcția returnează True dacă datele sunt valide și False în caz contrar.

			Funcția find_insertion_position(n, m, A, B) primește două liste de numere (A și B) și încearcă să găsească poziția din lista B începând de la care se poate insera lista A astfel încât lista rezultată să fie strict crescătoare.

			Pentru a face acest lucru, funcția parcurge lista B și caută primul element care este mai mare sau egal cu primul element din lista A. Apoi, parcurge lista A și caută primul element care este mai mare decât ultimul element din secțiunea anterioară din lista A care a fost deja inserată în lista B. Dacă nu există un astfel de element, atunci inserarea este imposibilă.

			Funcția returnează poziția de inserare (în formatul specificat în enunțul problemei) sau stringul "imposibil" dacă inserarea este imposibilă.

			În blocul if __name__ == '__main__': citim datele de intrare din fișierul "inserare2.in" și apoi verificăm dacă datele sunt valide folosind funcția validate_input(n, m, A, B). Dacă datele nu sunt valide, se afișează un mesaj corespunzător și se oprește execuția programului.

			Dacă datele sunt valide, se apelează funcția find_insertion_position(n, m, A, B) pentru a găsi poziția de inserare și se afișează un mesaj de confirmare a validității datelor. Apoi, rezultatul este afișat în fișierul de ieșire "inserare2.out". Observați că, în cazul în care inserarea este imposibilă, se afișează stringul "imposibil" în locul poziției de inserare.

Nagy Lenard at 20:17, 24 March 2023

2023-03-24T20:17:32Z

← Older revision		Revision as of 20:17, 24 March 2023
Line 64:		Line 64:
	# Găsește poziția din al doilea șir începând de la care poate fi inserat primul șir,		# Găsește poziția din al doilea șir începând de la care poate fi inserat primul șir,
	# astfel încât șirul obținut să fie strict crescător		# astfel încât șirul obținut să fie strict crescător
	~~pos~~ = 1		pozitie = 1
	for i in range(m):		for i in range(m):
	if B[i] >= A[0]:		if B[i] >= A[0]:
	while ~~pos~~ < n and A[~~pos~~] <= B[i]:		while pozitie < n and A[pozitie] <= B[i]:
	~~pos~~ += 1		pozitie += 1
	if ~~pos~~ == n:		if pozitie == n:
	return i + 1		return i + 1
	return "imposibil"		return "imposibil"

Nagy Lenard at 15:58, 24 March 2023

2023-03-24T15:58:00Z

← Older revision		Revision as of 15:58, 24 March 2023
Line 22:		Line 22:
	:7 10 12 20 30 40		:7 10 12 20 30 40
	; ''Ecran''		; ''Ecran''
	Datele sunt introduse corect.		:Datele sunt introduse corect.
	; ''inserare2.out''		; ''inserare2.out''
	:imposibil		:imposibil
Line 31:		Line 31:
	:5 15 25 35		:5 15 25 35
	; ''Ecra''		; ''Ecra''
	Datele sunt introduse corect.		:Datele sunt introduse corect.
	; ''inserare2.out''		; ''inserare2.out''
	imposibil		:imposibil
	===Exemplul 3===		===Exemplul 3===
	; ''inserare2.in''		; ''inserare2.in''
	5 6		:5 6
	2 4 6 8 10		:2 4 6 8 10
	1 3 5 7 9 11		:1 3 5 7 9 11
	; ''Ecran''		; ''Ecran''
	Datele nu corespund restricțiilor impuse		:Datele nu corespund restricțiilor impuse
	; ''inserare2.out''		; ''inserare2.out''
	imposibil		:imposibil

	<br>		<br>

Nagy Lenard at 15:57, 24 March 2023

2023-03-24T15:57:19Z

← Older revision		Revision as of 15:57, 24 March 2023
Line 21:		Line 21:
	:15 16 17 19		:15 16 17 19
	:7 10 12 20 30 40		:7 10 12 20 30 40
			; ''Ecran''
			Datele sunt introduse corect.
	; ''inserare2.out''		; ''inserare2.out''
	:imposibil		:imposibil
Line 28:		Line 30:
	:10 20 30		:10 20 30
	:5 15 25 35		:5 15 25 35
			; ''Ecra''
			Datele sunt introduse corect.
	; ''inserare2.out''		; ''inserare2.out''
	imposibil		imposibil
Line 35:		Line 39:
	2 4 6 8 10		2 4 6 8 10
	1 3 5 7 9 11		1 3 5 7 9 11
			; ''Ecran''
			Datele nu corespund restricțiilor impuse
	; ''inserare2.out''		; ''inserare2.out''
	imposibil		imposibil
Line 46:		Line 52:
	def validate_input(n, m, A, B):		def validate_input(n, m, A, B):
	# Verifică dacă datele de intrare corespund restricțiilor impuse		# Verifică dacă datele de intrare corespund restricțiilor impuse
	if not (1 <= n <= 106 and 1 <= m <= 106):		if not (1 <= n <= 10 6 and 1 <= m <= 10 6):
	return False		return False
	if len(A) != n or len(B) != m:		if len(A) != n or len(B) != m:
	return False		return False
	if any(A[i] >= A[i+1] for i in range(n-1)) or any(B[i] >= B[i+1] for i in range(m-1)):		if any(A[i] >= A[i + 1] for i in range(n - 1)) or any(B[i] >= B[i + 1] for i in range(m - 1)):
	return False		return False
	return True		return True


	def find_insertion_position(n, m, A, B):		def find_insertion_position(n, m, A, B):
Line 63:		Line 70:
	pos += 1		pos += 1
	if pos == n:		if pos == n:
	return i+1		return i + 1
	return "imposibil"		return "imposibil"

	~~def main()~~:
			if __name__ == '__main__':
	# Citire date de intrare		# Citire date de intrare
	with open("inserare2.in", "r") as fin:		try:
	m, n = map(int, fin.readline().split())		with open("inserare2.in", "r") as fin:
	B = list(map(int, fin.readline().split()))		m, n = map(int, fin.readline().split())
	A = list(map(int, fin.readline().split()))		B = list(map(int, fin.readline().split()))
			A = list(map(int, fin.readline().split()))
			except ValueError:
			print("Datele nu corespund restricțiilor impuse.")
			exit()

	# Validare date de intrare		# Validare date de intrare
	if not validate_input(n, m, A, B):		if not validate_input(n, m, A, B):
	print("Datele nu corespund restricțiilor impuse.")		print("Datele nu corespund restricțiilor impuse.")
	~~return~~		exit()

	# Găsire poziție de inserare și afișare rezultat		# Găsire poziție de inserare și afișare rezultat
Line 83:		Line 95:
	with open("inserare2.out", "w") as fout:		with open("inserare2.out", "w") as fout:
	fout.write(str(result) + "\n" if result != "imposibil" else "imposibil\n")		fout.write(str(result) + "\n" if result != "imposibil" else "imposibil\n")


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








	</syntaxhighlight>		</syntaxhighlight>

Sovago Rares-Andrei: Pagină nouă: == Cerinţa == Numim '''inserare''' a unui șir ''A'' într-un șir ''B'' introducerea, între două elemente ale șirului ''B'', a tuturor elementelor lui ''A'', pe poziții consecutive, în ordinea în care apar în ''A''. Se dau două șiruri cu '''n''', respectiv '''m''' elemente numere întregi ordonate strict crescător, în care numerotarea elementelor începe de la '''1'''. Se cere să se afișeze poziția din al doilea șir începând de la care poate fi inserat pr...

2023-03-23T20:41:23Z

Pagină nouă: == Cerinţa == Numim '''inserare''' a unui șir ''A'' într-un șir ''B'' introducerea, între două elemente ale șirului ''B'', a tuturor elementelor lui ''A'', pe poziții consecutive, în ordinea în care apar în ''A''. Se dau două șiruri cu '''n''', respectiv '''m''' elemente numere întregi ordonate strict crescător, în care numerotarea elementelor începe de la '''1'''. Se cere să se afișeze poziția din al doilea șir începând de la care poate fi inserat pr...

New page

== Cerinţa ==
Numim '''inserare''' a unui șir ''A'' într-un șir ''B'' introducerea, între două elemente ale șirului ''B'', a tuturor elementelor lui ''A'', pe poziții consecutive, în ordinea în care apar în ''A''.

Se dau două șiruri cu '''n''', respectiv '''m''' elemente numere întregi ordonate strict crescător, în care numerotarea elementelor începe de la '''1'''.

Se cere să se afișeze poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul '''imposibil'''.
== Date de intrare ==
Fișierul de intrare '''inserare2.in''' conține numere naturale din intervalul '''[1,10^6]''': pe prima linie numerele '''m''' și '''n''', iar pe fiecare dintre următoarele două linii câte un șir de '''m''', respectiv de '''n''' numere întregi ordonate strict crescător. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran:
"Datele sunt introduse corect.",fișierul de ieșire inserare2.out va conține poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
== Restricţii şi precizări ==
*Pentru determinarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei necesare și al timpului de executare.
*Se recomandă evitarea memorării elementelor șirului într-un tablou sau în altă structură de date similară.

== Exemple ==
===Exemplul 1===
; ''inserare2.in''
: 4 6
:15 16 17 19
:7 10 12 20 30 40
; ''inserare2.out''
:imposibil
===Exemplul 2===
; ''inserare2.in''
:3 4
:10 20 30
:5 15 25 35
; ''inserare2.out''
imposibil
===Exemplul 3===
; ''inserare2.in''
5 6
2 4 6 8 10
1 3 5 7 9 11
; ''inserare2.out''
imposibil

<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 2818 - Inserare 2
def validate_input(n, m, A, B):
# Verifică dacă datele de intrare corespund restricțiilor impuse
if not (1 <= n <= 10**6 and 1 <= m <= 10**6):
return False
if len(A) != n or len(B) != m:
return False
if any(A[i] >= A[i+1] for i in range(n-1)) or any(B[i] >= B[i+1] for i in range(m-1)):
return False
return True

def find_insertion_position(n, m, A, B):
# Găsește poziția din al doilea șir începând de la care poate fi inserat primul șir,
# astfel încât șirul obținut să fie strict crescător
pos = 1
for i in range(m):
if B[i] >= A[0]:
while pos < n and A[pos] <= B[i]:
pos += 1
if pos == n:
return i+1
return "imposibil"

def main():
# Citire date de intrare
with open("inserare2.in", "r") as fin:
m, n = map(int, fin.readline().split())
B = list(map(int, fin.readline().split()))
A = list(map(int, fin.readline().split()))

# Validare date de intrare
if not validate_input(n, m, A, B):
print("Datele nu corespund restricțiilor impuse.")
return

# Găsire poziție de inserare și afișare rezultat
result = find_insertion_position(n, m, A, B)
print("Datele sunt introduse corect.")
with open("inserare2.out", "w") as fout:
fout.write(str(result) + "\n" if result != "imposibil" else "imposibil\n")

if __name__ == "__main__":
main()

</syntaxhighlight>