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 coada1in.txt 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 coada1out.txt 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

Exemplul 1:

coada1in.txt

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

coada1out.txt

Datele de intrare corespund restrictiilor impuse
2
-1
1

Exemplul 2:

coada1in.txt

coada1

coada1out.txt

Datele de intrare nu corespund restrictiilor impuse

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

def validare(m, operatii):  # funcția de validare a datelor de intrare
    if m < 1 or m > 50000:
        raise ValueError
    for operatie in operatii:
        if operatie[0] not in ['push', 'query']:
            raise ValueError
        x = operatie[1]
        if x < 1 or x > 1000:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


def solve(operatii):  # funcția de rezolvare
    queue = []
    output = []
    for operatie in operatii:
        if operatie[0] == 'push':
            x = operatie[1]
            if x in queue:
                queue = queue[queue.index(x)+1:]
            queue.append(x)
        elif operatie[0] == 'query':
            x = operatie[1]
            if x in queue:
                output.append(queue.index(x) + 1)
            else:
                output.append(-1)
    return output


if __name__ == '__main__':
    file_in = open("coada1in.txt", "r")  # declararea fisierelor
    file_out = open("coada1out.txt", "w")  # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        M = int(file_in.readline())
        operations = []
        for _ in range(M):
            operation = file_in.readline().split()
            operation[1] = int(operation[1])
            operations.append(operation)

        validare(M, operations)  # apelul funcției de validare
        results = solve(operations)  # apelul funcției de rezolvare

        for result in results:
            file_out.write(str(result) + '\n')

    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")