2012 - TSM

Enunț

TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține 4 jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei 4 prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă de joc acțiunile se petrec pe un câmp de luptă, inițial gol, iar apărătorii disting următoarele evenimente:

1 x : TH observă că Mygo a trimis pe câmpul de luptă un tanc de coeficient x și își anunță aliații.

2 K : Seba consideră că cel mai periculos tip de tanc aflat pe câmpul de luptă este cel cu al K – lea cel mai mic coeficient și îl afișează în consolă, pe un nou rând.

3 : Năstuț scrie în consolă, pe un nou rând, coeficientul cel mai mic al unui tanc aflat în momentul respectiv pe câmpul de luptă.

4 : Șcuțu trage cu tunul într-un tanc de coeficient egal cu ultimul scris de Seba în consolă și îl elimină.

Cerința

Pentru un joc cu M evenimente, simulați parcursul jocului.

Cei 4 prieteni au folosit aceste două bucăți de cod ca să poată să câștige, așa că ți le oferă și ție:

InParser

OutParser

Date de intrare

Fișierul de intrare tsm.in conține pe prima linie numărul M, reprezentând numărul de evenimente, iar pe următoarele M linii câte un eveniment, cu formatul explicat mai sus.

Date de ieșire

Fișierul de ieșire tsm.out va conține pentru fiecare eveniment de tipul 2 și 3, răspunsul lor, fiecare pe câte o linie, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ M ≤ 1.000.000
• pentru evenimentele de tip 1, 1 ≤ x ≤ 1.000.000
• se garantează că orice alt eveniment va putea fi procesat.
• între oricare 2 evenimente de tip 4 va exista cel puțin un eveniment de tip 2.

Exemplu:

tsm.in

14
1 2
1 3
3
1 2
1 1
1 1
3
1 4
2 3
2 1
4
2 1
4
3

tsm.out

2
1
3
1
1
2

Rezolvare

<syntaxhighlight lang="python3"> from heapq import heappush, heappop

def main():

   events = []  # Lista de evenimente
   tanks = []  # Coada de tancuri (heap)

   with open("tsm.in", "r") as fin, open("tsm.out", "w") as fout:
       m = int(fin.readline())  # Numărul de evenimente

       for _ in range(m):
           event = fin.readline().split()
           event_type = int(event[0])
           events.append(event)

       for event in events:
           event_type = int(event[0])

           if event_type == 1:
               tank_coeff = int(event[1])
               heappush(tanks, tank_coeff)

           elif event_type == 2:
               k = len(tanks)
               if k > 0:
                   temp_tanks = tanks.copy()
                   temp_tanks.sort()
                   fout.write(str(temp_tanks[k - int(event[1])]) + "\n")

           elif event_type == 3:
               if tanks:
                   fout.write(str(tanks[0]) + "\n")

           elif event_type == 4:
               if tanks:
                   tank_to_remove = heappop(tanks)
                   while tanks and tank_to_remove != tanks[0]:
                       tank_to_remove = heappop(tanks)

if __name__ == "__main__":

   main()

</syntaxhighlight>