Editing 2818 - Inserare 2

== 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>