Editing 1033 - Elicop

Un teren de fotbal este folosit pentru aterizarea elicopterelor. Gazonul de pe stadion este parcelat în pătrăţele de aceeaşi dimensiune, cu laturile paralele cu marginile terenului. Liniile cu pătrăţele de gazon sunt numerotate de sus în jos cu numerele <code>1</code>, <code>2</code>, …, <code>m</code>, iar coloanele cu pătrăţele de gazon sunt numerotate de la stânga la dreapta cu numerele <code>1</code>, <code>2</code>, …, <code>n</code>. Din cauza tipului diferit de iarbă se ştie care dintre pătrăţele de gazon  sunt afectate sau nu de umbră. Acest lucru este precizat printr-un tablou bidimensional a cu <code>m</code> linii şi <code>n</code> coloane, cu elemente <code>0</code> şi <code>1</code> (<code>a<sup>ij</sup></code> <code>= 0</code> înseamnă că pătrăţelul aflat pe linia <code>i</code> şi coloana <code>j</code> este afectat de umbră, iar  <code>a<sup>ij</sup></code> <code>= 1</code> înseamnă că pătrăţelul aflat pe linia <code>i</code> şi coloana <code>j</code> nu este afectat de umbră).  Fiecare elicopter are <code>3</code> roţi pe care se sprijină. Roţile fiecărui elicopter determină un triunghi dreptunghic isoscel. Elicopterele aterizează, astfel încât triunghiurile formate să fie cu catetele paralele cu marginile terenului. În exemplul următor avem patru elicoptere.

Pentru a preciza poziţia unui elicopter pe teren este suficient să cunoaştem linia şi coloana vărfurilor ipotenuzei şi poziţia vârfului deasupra (codificată prin <code>1</code>) sau dedesubtul ipotenuzei (codificată prin <code>-1</code>). Pentru exemplu, elicopterul din stânga sus este dat prin <code>(1,1)</code>, <code>(3,3)</code> şi <code>-1</code>, cel din dreapta sus prin <code>(1,9)</code>, <code>(5,5)</code> şi <code>1</code>, cel din stânga jos prin <code>(5,1)</code>, <code>(6,2)</code> şi <code>1</code>, iar cel din dreapta jos prin <code>(5,9)</code>, <code>(6,8)</code> şi <code>1</code>.

Un elicopter se consideră că a aterizat ''greşit'', dacă triunghiul format sub el (definit mai sus) are mai mult de jumătate din pătrăţele afectate de umbră.

Administratorul terenului de fotbal doreşte să determine numărul <code>N1</code> de elicoptere, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat ''greşit'' în ordine crescătoare: <code>e<sub>1</sub></code>, <code>e<sub>2</sub></code>, …, <code>e<sub>N2</sub></code>, ştiind că există <code>k</code> elicoptere codificate prin numerele <code>1</code>, <code>2</code>, …, <code>k</code>.

= Cerința =
Scrieţi un program care să determine, pentru fişierul cu datele din enunţ: numărul de elicoptere <code>N1</code>, care nu afectează nici un pătrăţel din teren şi numerele de ordine al elicopterelor, care au aterizat ''greşit'' în ordine crescătoare, precedate de numărul lor <code>N2</code>.

= Date de intrare =
Fișierul de intrare <code>elicop.in</code> conține pe prima linie două numere naturale <code>m</code> şi <code>n</code>, separate printr-un spaţiu, cu semnificaţia din enunţ. Următoarele <code>m</code> linii conţin câte <code>n</code> numere <code>0</code> sau <code>1</code>, separate prin câte un spaţiu cu semnificaţia <code>0</code> – pătrăţel de gazon care este afectat de umbră, respectiv <code>1</code>- pătrăţel care nu este afectat de umbră. Pe linia <code>m+2</code> se află numărul de elicoptere <code>k</code>, iar pe următoarele <code>k</code> linii (în ordinea codificării lor <code>1</code>, <code>2</code>, …, <code>k</code>) câte cinci numere separate prin cate un spaţiu, pentru liniile şi coloanele ipotenuzelor şi poziţia vârfului (<code>1</code> sau <code>-1</code>), triunghiurilor dreptunghice asociate elicopterelor: 

<code>L1 C1 L2 C2 p</code>.

= Date de ieșire =
Fișierul de ieșire <code>elicop.out</code> va conține două linii: prima linie numărul <code>N1</code> de elicoptere, care nu afectează nici un pătrăţel din teren, a doua linie cu numerele naturale <code>N2</code>, <code>e<sub>1</sub></code>, <code>e<sub>2</sub></code>, …, <code>e<sub>N2</sub></code> separate prin câte un spaţiu, în ordine crescătoare.

= Restricții și precizări =

* <code>2 ≤ m,n ≤ 100</code>; <code>1 ≤ k ≤ 40</code>
* Nu există suprapuneri de triunghiuri asociate la două elicoptere. Triunghiurile asociate elicopterelor conţin cel puţin trei pătrăţele.

= Exemplu: =
<code>elicop.in</code>
 7 9
 1 1 1 1 1 1 1 1 1
 0 0 0 0 1 1 1 1 0
 0 0 1 0 1 1 1 0 0
 1 1 1 0 1 1 0 1 1
 0 0 1 1 1 1 0 1 1
 1 1 1 1 1 1 0 1 1
 1 1 1 1 1 1 0 0 1
 4
 1 1 3 3 -1
 1 9 5 5 1
 5 1 6 2 1
 5 9 6 8 1 
<code>elicop.out</code>
 2
 2 1 3

= Explicație =
Elicopterele <code>2</code> şi <code>4</code> nu afectează niciun pătrăţel de gazon.

Elicopterele <code>1</code> şi <code>3</code> afectează fiecare mai mult de jumătate din numărul pătrăţelelor asociate triunghiurilor dreptunghice şi deci aterizează greşit. Elicopterul <code>1</code> face umbră la <code>6</code> pătrăţele, din care afectate sunt <code>4</code>.

Elicopterul <code>3</code> face umbră la <code>3</code> pătrăţele, din care afectate sunt două.

<syntaxhighlight lang="python" line="1">
def citire_date(nume_fisier):
    with open(nume_fisier, 'r') as f:
        m, n = map(int, f.readline().split())
        a = [list(map(int, f.readline().split())) for _ in range(m)]
        k = int(f.readline())
        elicoptere = []
        for _ in range(k):
            lin1, col1, lin2, col2, poz = map(int, f.readline().split())
            elicoptere.append((lin1, col1, lin2, col2, poz))
    return m, n, a, k, elicoptere

def triunghi_umbre(m, n, a, lin1, col1, lin2, col2, poz):
    umbite = 0
    total = 0
    if poz == 1:
        for i in range(lin1, lin2+1):
            for j in range(col1, col2+1):
                total += 1
                if a[i-1][j-1] == 0:
                    umbite += 1
    else:
        for i in range(lin2, lin1+1):
            for j in range(col1, col2+1):
                total += 1
                if a[i-1][j-1] == 0:
                    umbite += 1
    return umbite, total

def verifica_aterizari(m, n, a, k, elicoptere):
    n1 = 0
    elicoptere_gresite = []
    for idx, (lin1, col1, lin2, col2, poz) in enumerate(elicoptere, start=1):
        umbite, total = triunghi_umbre(m, n, a, lin1, col1, lin2, col2, poz)
        if umbite == 0:
            n1 += 1
        elif umbite > total / 2:
            elicoptere_gresite.append(idx)
    return n1, elicoptere_gresite

def scrie_rezultate(nume_fisier, n1, elicoptere_gresite):
    with open(nume_fisier, 'w') as f:
        f.write(f"{n1}\n")
        f.write(f"{len(elicoptere_gresite)} {' '.join(map(str, elicoptere_gresite))}\n")

# Main function
def main():
    m, n, a, k, elicoptere = citire_date('date.in')
    n1, elicoptere_gresite = verifica_aterizari(m, n, a, k, elicoptere)
    scrie_rezultate('date.out', n1, elicoptere_gresite)

if __name__ == '__main__':
    main()
</syntaxhighlight>