View source for 1383 - Avioane

“Avioane pe hârtie” este un joc ce se joacă în doi, fiecare jucător având la dispoziţie o foaie de hârtie (de matematică) şi ceva de scris.

Pe foaia ta de matematică, ai desenat un caroiaj cu <code>N</code> linii şi <code>N</code> coloane. La un moment al jocului, în acest caroiaj sunt deja plasate <code>M</code> avioane, numerotate de la <code>1</code> la <code>M</code>. Fiecare avion e format din exact <code>10</code> celule (o celulă cabina, apoi <code>5</code> celule aripa mare, o celulă culoar şi <code>3</code> celule aripa mică). Avioanele desenate nu se suprapun şi în funcţie de modul în care sunt amplasate pot fi de <code>4</code> tipuri:

* <code>1</code> – cabina orientată spre nord;
* <code>2</code> – cabina orientată spre est.
* <code>3</code> – cabina orientată spre sud;
* <code>4</code> – cabina orientată spre vest.

Pentru a putea identifica un avion pe foaie, toate celulele acoperite de avion sunt marcate cu numărul de ordine al avionului. Poziţiile neacoperite de avioane au valoarea <code>0</code>.

Adversarul, fără a vedea foaia ta, lansează <code>L</code> lovituri. Fiecare lovitură afectează o singură celulă a caroiajului. Dacă loviturile afectează cel puţin una dintre celulele acoperite de un avion, se consideră că avionul a fost avariat. Un avion avariat este considerat avion doborât dacă a fost lovită cabina sa sau cel puțin <code>5</code> celule dintre cele <code>10</code> ale sale.

Dată fiind configuraţia caroiajului şi poziţiile loviturilor lansate de adversar, să se determine:

a. numărul total de avioane desenate în caroiaj;

b. numărul de avioane de fiecare tip;

c. numărul de avioane avariate, fără a fi doborâte;

d. numărul de avioane doborâte.

= Date de intrare =
Fişierul <code>avioane.in</code> conţine pe prima linie numerele naturale <code>N L</code>, reprezentând dimensiunea caroiajului, respectiv numărul de lovituri lansate de adversar. Pe următoarele <code>N</code> linii se vor găsi câte <code>N</code> numere naturale, reprezentând configuraţia caroiajului, conform specificaţiilor din enunţ. Pe următoarele <code>L</code> linii se află câte două numere naturale <code>X Y</code>, reprezentând linia, respectiv coloana unei celule lovite. Numerele scrise pe aceeaşi linie sunt separate prin spaţii.

= Date de ieșire =
Fişierul <code>avioane.out</code> va conţine pe prima linie numărul total de avioane de pe foaie; pe următoarele <code>4</code> linii se vor scrie <code>4</code> numere naturale, câte unul pe linie, reprezentând în ordine numărul avioanelor de tip <code>1</code>, tip <code>2</code>, tip <code>3</code> și respectiv tip <code>4</code>. Pe următoarea linie se va scrie numărul de avioane avariate, care nu au fost doborâte, iar pe ultima linie va fi scris numărul de avioane doborâte.

= Restricții și precizări =

* <code>8 ≤ N ≤ 300</code>
* <code>N/2 ≤ L ≤ 2*N</code>
* Liniile şi respectiv coloanele caroiajului sunt numerotate de la <code>1</code> la <code>N</code>.

= Exemplu: =
<code>avioane.in</code>
 8 5
 0 0 0 0 0 0 0 0 
 0 0 0 0 1 1 1 0 
 0 0 0 0 0 1 0 0 
 0 0 0 1 1 1 1 1 
 0 0 2 2 2 1 0 0 
 0 0 0 2 0 0 0 0 
 0 2 2 2 2 2 0 0 
 0 0 0 2 0 0 0 0 
 6 6
 5 3
 3 6
 7 3
 8 5
<code>avioane.out</code>
 2
 0
 0
 2
 0
 2
 0

=== Explicație ===
În matricea de <code>8x8</code> avem <code>2</code> avioane, ambele de tip <code>3</code>. Cabinele sunt în coordonatele <code>(5,6)</code> și <code>(8,4)</code>. Deci pe prima linie în fișierul de ieșire va fi <code>2</code>, iar pe următoarele <code>4</code> linii numărul avioanelor de fiecare tip: <code>0</code>, <code>0</code>, <code>2</code>, <code>0</code>, fiecare pe linie nouă.

În această reprezentare avem <code>5</code> lovituri. Cu cele <code>5</code> lovituri am reușit să lovim ambele avioane, fără a lovi cabina sau cel puțin <code>5</code> lovituri/avion. Astfel următoarele <code>2</code> valori din fișierul de ieșire sunt <code>2</code> și <code>0</code>.

În această diagramă nu mai putem adăuga un avion de tip <code>1</code> astfel pe ultima linie vom avea valoarea <code>0</code>.

<syntaxhighlight lang="python" line="1">
def process_game(N, M, avioane, L, lovituri):
    # Initializare matrice
    matrice = [[0] * N for _ in range(N)]
    
    # Plasarea avioanelor în matrice
    avion_celule = {}
    avion_tip = {}
    
    for avion in avioane:
        id, tip, linie, coloana = avion
        avion_celule[id] = []
        avion_tip[id] = tip
        
        if tip == 1:  # cabina spre nord
            coords = [(linie, coloana), (linie+1, coloana-2), (linie+1, coloana-1), (linie+1, coloana),
                      (linie+1, coloana+1), (linie+1, coloana+2), (linie+2, coloana), 
                      (linie+3, coloana-1), (linie+3, coloana), (linie+3, coloana+1)]
        elif tip == 2:  # cabina spre est
            coords = [(linie, coloana), (linie-2, coloana-1), (linie-1, coloana-1), (linie, coloana-1),
                      (linie+1, coloana-1), (linie+2, coloana-1), (linie, coloana-2), 
                      (linie-1, coloana-3), (linie, coloana-3), (linie+1, coloana-3)]
        elif tip == 3:  # cabina spre sud
            coords = [(linie, coloana), (linie-1, coloana-2), (linie-1, coloana-1), (linie-1, coloana),
                      (linie-1, coloana+1), (linie-1, coloana+2), (linie-2, coloana),
                      (linie-3, coloana-1), (linie-3, coloana), (linie-3, coloana+1)]
        elif tip == 4:  # cabina spre vest
            coords = [(linie, coloana), (linie-2, coloana+1), (linie-1, coloana+1), (linie, coloana+1),
                      (linie+1, coloana+1), (linie+2, coloana+1), (linie, coloana+2),
                      (linie-1, coloana+3), (linie, coloana+3), (linie+1, coloana+3)]
        
        for coord in coords:
            r, c = coord
            if 0 <= r < N and 0 <= c < N:
                matrice[r][c] = id
                avion_celule[id].append((r, c))
    
    # Procesarea loviturilor
    lovituri_set = set(lovituri)
    
    avioane_doborate = 0
    avioane_avariate = 0
    
    for id, celule in avion_celule.items():
        lovituri_in_celule = [celula for celula in celule if celula in lovituri_set]
        numar_lovituri = len(lovituri_in_celule)
        cabina_lovita = celule[0] in lovituri_set
        
        if numar_lovituri >= 5 or cabina_lovita:
            avioane_doborate += 1
        elif numar_lovituri > 0:
            avioane_avariate += 1
    
    # Numărarea tipurilor de avioane
    tipuri_avioane = {1: 0, 2: 0, 3: 0, 4: 0}
    for tip in avion_tip.values():
        tipuri_avioane[tip] += 1
    
    return M, tipuri_avioane, avioane_avariate, avioane_doborate

# Exemplu de utilizare
N = 10
M = 2
avioane = [
    (1, 1, 2, 2),  # avion 1, tip 1 (nord), cabina la (2, 2)
    (2, 2, 5, 5)   # avion 2, tip 2 (est), cabina la (5, 5)
]
L = 3
lovituri = [(2, 2), (5, 5), (4, 5)]

total_avioane, tipuri_avioane, avioane_avariate, avioane_doborate = process_game(N, M, avioane, L, lovituri)
print(f"Numărul total de avioane: {total_avioane}")
print(f"Numărul de avioane de fiecare tip: {tipuri_avioane}")
print(f"Numărul de avioane avariate, fără a fi doborâte: {avioane_avariate}")
print(f"Numărul de avioane doborâte: {avioane_doborate}")
</syntaxhighlight>