2818 - Inserare 2: Diferență între versiuni
(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...) |
Fără descriere a modificării |
||
Linia 21: | Linia 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 | ||
Linia 28: | Linia 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 | ||
Linia 35: | Linia 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 | ||
Linia 46: | Linia 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 <= 10**6 and 1 <= m <= 10**6): | 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): | ||
Linia 63: | Linia 70: | ||
pos += 1 | pos += 1 | ||
if pos == n: | if pos == n: | ||
return i+1 | return i + 1 | ||
return "imposibil" | return "imposibil" | ||
if __name__ == '__main__': | |||
# Citire date de intrare | # Citire date de intrare | ||
with open("inserare2.in", "r") as fin: | try: | ||
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())) | |||
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.") | ||
exit() | |||
# Găsire poziție de inserare și afișare rezultat | # Găsire poziție de inserare și afișare rezultat | ||
Linia 83: | Linia 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") | ||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea de la data 24 martie 2023 15:57
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
- Ecran
Datele sunt introduse corect.
- inserare2.out
- imposibil
Exemplul 2
- inserare2.in
- 3 4
- 10 20 30
- 5 15 25 35
- Ecra
Datele sunt introduse corect.
- inserare2.out
imposibil
Exemplul 3
- inserare2.in
5 6 2 4 6 8 10 1 3 5 7 9 11
- Ecran
Datele nu corespund restricțiilor impuse
- inserare2.out
imposibil
Rezolvare
# 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"
if __name__ == '__main__':
# Citire date de intrare
try:
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()))
except ValueError:
print("Datele nu corespund restricțiilor impuse.")
exit()
# Validare date de intrare
if not validate_input(n, m, A, B):
print("Datele nu corespund restricțiilor impuse.")
exit()
# 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")