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 N linii şi N coloane. La un moment al jocului, în acest caroiaj sunt deja plasate M avioane, numerotate de la 1 la M. Fiecare avion e format din exact 10 celule (o celulă cabina, apoi 5 celule aripa mare, o celulă culoar şi 3 celule aripa mică). Avioanele desenate nu se suprapun şi în funcţie de modul în care sunt amplasate pot fi de 4 tipuri:
1– cabina orientată spre nord;2– cabina orientată spre est.3– cabina orientată spre sud;4– 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 0.
Adversarul, fără a vedea foaia ta, lansează L 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 5 celule dintre cele 10 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[edit | edit source]
Fişierul avioane.in conţine pe prima linie numerele naturale N L, reprezentând dimensiunea caroiajului, respectiv numărul de lovituri lansate de adversar. Pe următoarele N linii se vor găsi câte N numere naturale, reprezentând configuraţia caroiajului, conform specificaţiilor din enunţ. Pe următoarele L linii se află câte două numere naturale X Y, reprezentând linia, respectiv coloana unei celule lovite. Numerele scrise pe aceeaşi linie sunt separate prin spaţii.
Date de ieșire[edit | edit source]
Fişierul avioane.out va conţine pe prima linie numărul total de avioane de pe foaie; pe următoarele 4 linii se vor scrie 4 numere naturale, câte unul pe linie, reprezentând în ordine numărul avioanelor de tip 1, tip 2, tip 3 și respectiv tip 4. 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[edit | edit source]
8 ≤ N ≤ 300N/2 ≤ L ≤ 2*N- Liniile şi respectiv coloanele caroiajului sunt numerotate de la
1laN.
Exemplu:[edit | edit source]
avioane.in
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
avioane.out
2 0 0 2 0 2 0
Explicație[edit | edit source]
În matricea de 8x8 avem 2 avioane, ambele de tip 3. Cabinele sunt în coordonatele (5,6) și (8,4). Deci pe prima linie în fișierul de ieșire va fi 2, iar pe următoarele 4 linii numărul avioanelor de fiecare tip: 0, 0, 2, 0, fiecare pe linie nouă.
În această reprezentare avem 5 lovituri. Cu cele 5 lovituri am reușit să lovim ambele avioane, fără a lovi cabina sau cel puțin 5 lovituri/avion. Astfel următoarele 2 valori din fișierul de ieșire sunt 2 și 0.
În această diagramă nu mai putem adăuga un avion de tip 1 astfel pe ultima linie vom avea valoarea 0.
<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>