Editing 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 <code>4</code> 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 <code>4</code> 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:

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

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

<code>3</code> : 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ă.

<code>4</code> : Ș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 <code>M</code> evenimente, simulați parcursul jocului.

Cei <code>4</code> 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 <code>tsm.in</code> conține pe prima linie numărul <code>M</code>, reprezentând numărul de evenimente, iar pe următoarele <code>M</code> linii câte un eveniment, cu formatul explicat mai sus.

= Date de ieșire =
Fișierul de ieșire <code>tsm.out</code> va conține pentru fiecare eveniment de tipul <code>2</code> și <code>3</code>, 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 =

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

= Exemplu: =
<code>tsm.in</code>
 14
 1 2
 1 3
 3
 1 2
 1 1
 1 1
 3
 1 4
 2 3
 2 1
 4
 2 1
 4
 3
<code>tsm.out</code>
 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>