Editing 3198 - Optimize

Programul de mai jos citește din fișierul '''input.txt''' un vector de elemente întregi și construiește în memorie (apoi scrie în fișierul '''output.txt''') un vector care conține aceleași elemente, doar că având toate elementele egale cu '''0'' la final. Ordinea celorlalte elemente se păstrează.
Programul dă întotdeuna rezultatul corect, însă este ineficient din punctul de vedere al timpului de execuție.
== Cerința ==
Rolul vostru este acela de a optimiza programul, astfel încât acesta să se execute în limita de timp indicată în enunț, pentru un vector de cel mult 1 milion de elemente. Limita de memorie trebuie, de asemenea, respectată. În acest sens, este permisă modificarea (oricât de radicală) a funcției '''nule'''. Orice modificare în afara corpului acestei funcții va conduce la respingerea soluței.
== Date de intrare ==
Fișierul de intrare '''input.txt''' conține pe prima linie numărul '''n''', iar pe a doua linie '''n''' numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire '''output.txt''' va conține pe prima linie numărul '''n''', iar pe a doua linie elementele vectorului generat.
== Restricții și precizări ==
* '''1 ≤ n ≤ 1.000.000'''
== Important ==
Soluţia propusă va conţine doar definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce la erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.
== Exemplul 1 ==
; input.txt
: 10
: 0 3 8 0 0 3 8 7 0 10
; output.txt
: Datele introduse corespund restricțiilor impuse.
: 10
: 3 8 3 8 7 10 0 0 0 0
== Exemplul 2 ==
; input.txt
: 1000001
: 0 1 2 3 4 5 6 7 8 9 10
; output.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def validare(n, v):
    if n < 1 or n > 1000000:
        raise ValueError("Datele introduse nu corespund restricțiilor impuse.")
    if len(v) != n:
        raise IndexError("Datele introduse nu corespund restricțiilor impuse.")
    print("Datele introduse corespund restricțiilor impuse.")


def nule(v):
    size = len(v)
    for i in range(size - 1):
        swaped = False
        for j in range(size - i - 1):
            if v[j] == 0:
                v[j], v[j+1] = v[j+1], v[j]
                swaped = True
        if not swaped:
            break


def main():
    input_filename = "input.txt"
    output_filename = "output.txt"
    # Read vector from input file
    try:
        with open(input_filename, 'r') as input_file:
            size = int(input_file.readline())
            v = list(map(int, input_file.readline().split()))
            validare(size, v)
    except IOError:
        print(f"Failed to open {input_filename}")
        exit(-1)
    except (ValueError, IndexError) as e:
        print(e)
        exit(-1)
    # Call nule() function
    nule(v)
    # Print vector to output file
    try:
        with open(output_filename, 'w') as output_file:
            output_file.write(str(size) + '\n')
            output_file.write(' '.join(map(str, v)) + '\n')
    except IOError:
        print(f"Failed to open {output_filename}")
        exit(-1)


if __name__ == "__main__":
    main()

</syntaxhighlight>