2012 - TSM

De la Universitas MediaWiki
Versiunea pentru tipărire nu mai este suportată și poate avea erori de randare. Vă rugăm să vă actualizați bookmarkurile browserului și să folosiți funcția implicită de tipărire a browserului.

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

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