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

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

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")

</syntaxhighlight>