Editing 1598 - Coada1

Se consideră '''C''' o coadă de numere naturale, iniţial vidă. Se definesc două tipuri de operaţii.

Operaţia '''1''' : '''push X''', adaugă elementul '''X''' în coadă. Dacă '''X''' există deja în coadă, se scot toate elementele din coadă, pana la întâlnirea lui, inclusiv '''X'''.
Exemplu: '''C: 2 4 5 1 6'''
'''Push 5'''
'''C: 1 6 5 ( s-au scos 2, 4, 5).'''

Operaţia '''2''': '''query X''', cere afişarea poziţiei elementului '''X''' în coada '''C'''. Dacă elementul nu există în coadă, se afişează '''-1'''.
Exemplu: '''C: 2 5 1 3 7'''
'''Query 1'''
'''Răspuns: 3'''

==Cerința==

Dându-se '''M''', reprezentând numărul de operaţii şi cele '''M''' operaţii, să se răspundă la operaţiile de tip '''query'''.

==Date de intrare==

Fișierul de intrare '''coada1.in''' conține:

*Pe prima linie numărul natural '''M''';
*Pe următoarele '''M''' linii, câte un string şi câte un număr natural, de forma '''tip_operaţie x''', reprezentând tipul operaţiei şi numărul '''X'''.

==Date de ieșire==

Fișierul de ieșire '''coada1.out''' va conține:

*Răspunsurile pentru operaţiile de tip '''query''', câte unul pe linie.

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

*'''1 ≤ M ≤ 50.000'''
*'''1 ≤ X ≤ 1.000'''

==Exemplu:==

;coada1.in

:10
:push 3
:push 6
:push 8
:push 2
:query 6
:push 6
:query 4
:push 6
:push 7
:query 6

;coada1.out

:2
:-1
:1

==Explicație==

Înaintea primei întrebări, coada arată asa: '''3 6 8 2''', deci '''6''' apare pe poziţia '''2'''.
Înaintea celei de-a doua întrebări, coada arată asa: '''8 2 6''', deci '''4''' nu apare.
Înaintea ultimei întrebări, coada arată asa: '''6 7''', deci '''6''' apare pe poziţia '''1'''.


==Rezolvare==

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

# Definim funcția 'solve' care primește numărul de operații 'M' și o listă de operații
def solve(M, operations):
    # Inițializăm coada ca o listă goală
    queue = []
    # Inițializăm lista de rezultate ca o listă goală
    output = []
    # Parcurgem fiecare operație
    for operation in operations:
        # Dacă operația este 'push'
        if operation[0] == 'push':
            # Extragem valoarea 'x'
            x = operation[1]
            # Dacă 'x' se află deja în coadă
            if x in queue:
                # Eliminăm toate elementele din coadă până la 'x', inclusiv 'x'
                queue = queue[queue.index(x)+1:]
            # Adăugăm 'x' la sfârșitul cozii
            queue.append(x)
        # Dacă operația este 'query'
        elif operation[0] == 'query':
            # Extragem valoarea 'x'
            x = operation[1]
            # Dacă 'x' se află în coadă
            if x in queue:
                # Adăugăm poziția lui 'x' în coadă la rezultate
                output.append(queue.index(x) + 1)
            else:
                # Dacă 'x' nu se află în coadă, adăugăm -1 la rezultate
                output.append(-1)
    # Returnăm lista de rezultate
    return output

# Definim numărul de operații și lista de operații
M = 10
operations = [
    ['push', 3],
    ['push', 6],
    ['push', 8],
    ['push', 2],
    ['query', 6],
    ['push', 6],
    ['query', 4],
    ['push', 6],
    ['push', 7],
    ['query', 6]
]

# Apelăm funcția 'solve' cu numărul de operații și lista de operații
results = solve(M, operations)

# Deschidem fișierul 'coada1.out' pentru scriere
with open('coada1.out', 'w') as f:
    # Scriem fiecare rezultat pe câte o linie nouă în fișier
    for result in results:
        f.write(str(result) + '\n')

</syntaxhighlight>