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

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

1. 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]

]

1. Apelăm funcția 'solve' cu numărul de operații și lista de operații

results = solve(M, operations)

1. 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>