3370 - Amedie

Enunț

Pentru o matrice A cu n linii şi m coloane, ce conţine numere naturale, se defineşte amedia matricei A ca fiind valoarea situată la mijlocul şirului ordonat crescător format din toate elementele matricei A, dacă numărul de elemente din acest şir este impar, respectiv cea mai mică valoare dintre cele două valori situate la mijloc, dacă numărul de elemente din acest şir este par. Se definesc trei tipuri de operaţii ce pot fi aplicate matricei A:

• operaţia de tip 1, notată cu L x, ce constă în eliminarea liniei cu indicele x din matrice;
  
• operaţia de tip 2, notată cu C y, ce constă în eliminarea coloanei cu indicele y din matrice;
  
• operaţia de tip 3, notată cu Q, ce are ca rezultat determinarea valorii amediei matricei.
  

Ami este pasionată de matematică şi trebuie să rezolve următoarea problemă: pentru o matrice A asupra căreia se aplică un şir de astfel de operaţii, să se stabilească răspunsurile la toate operaţiile de tip 3.

Cerința

Scrieţi un program care determină valorile obţinute în urma efectuării operaţiilor de tip 3 din şirul de operaţii aplicate matricei A.

Date de intrare

Fișierul de intrare amediein.txt conţine pe prima linie trei numere naturale n, m şi q despărţite prin câte un spaţiu, ce reprezintă, în ordine, numărul de linii din matricea A, numărul de coloane din matricea A şi numărul de operaţii ce se aplică matricei A. Pe fiecare dintre următoarele n linii din fişier se află câte m numere naturale, separate prin câte un spaţiu, ce reprezintă, în ordine, elementele aflate pe liniile matricei A. Fiecare dintre următoarele q linii din fişier conţine un şir de caractere ce reprezintă o operaţie ce se va aplica matricei A.

Date de ieșire

Fișierul de ieșire amedieout.txt va conţine valorile obţinute, în ordine, la toate operaţiile Q din şirul de operaţii aplicate matricei A. Fiecare dintre valorile obţinute se va afişa pe câte o linie din fişier, în ordinea stabilită în şirul de operaţii.

Restricții și precizări

• 2 ⩽ n, m ⩽ 800
• 1 ⩽ q ⩽ 2.000
• elementele matricei A sunt numere naturale nenule, strict mai mici decât 100.001
• indicii de linie şi coloană din matrice sunt notaţi începând cu 1
• operaţiile de tipul 1 şi 2 se aplică utilizând indicii liniilor şi coloanelor din matricea A iniţială;
• se garantează că orice operaţie din fişierul de intrare poate fi efectuată.

Exemplul 1

Intrare

amediein.txt

4 4 4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

L 2

Q

C 1

Q

Ieșire

Datele de intrare corespund restricțiilor impuse

amedieout.txt

10

11

Explicație

L 2

!!

Prin aplicarea operaţiei de tip 3 obţinem valoarea 10.

C 1

!!

Prin aplicarea operaţiei de tip 3 obţinem valoarea 11.

Exemplul 2

Intrare

amediein.txt

1 801 0

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

L 2

Q

C 1

Q

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#3370 - Amedie

def valideaza_input(n, m, q, matrice, operatii):
    if not (2 <= n <= 800) or not (2 <= m <= 800) or not (0 < q <= 2000):
        return False

    for rand in matrice:
        if len(rand) != m or any(not(0 < int(elem) < 100001) for elem in rand):
            return False

    for op in operatii:
        if op[0] == 'L':
            if not (1 <= int(op[1]) <= n):
                return False
        elif op[0] == 'C':
            if not (1 <= int(op[1]) <= m):
                return False

    return True


def calculeaza_mediana(matrice):
    amedie = sorted([elem for rand in matrice for elem in rand])
    mijloc = len(amedie) // 2

    if len(amedie) % 2 == 1:
        return amedie[mijloc]
    else:
        return min(amedie[mijloc - 1], amedie[mijloc])


def aplica_operatii(matrice, operatii):
    rezultate = []

    for op in operatii:
        if op[0] == 'L':
            del matrice[int(op[1]) - 1]
        elif op[0] == 'C':
            for rand in matrice:
                del rand[int(op[1]) - 1]

        elif op[0] == 'Q':
            rezultate.append(calculeaza_mediana(matrice))

    return rezultate


def main():
    with open('amediein.txt', 'r') as infile:
        n, m, q = map(int, infile.readline().split())
        matrice = [list(map(int, infile.readline().split())) for _ in range(n)]
        operatii = [linie.strip().split() for linie in infile]

    if valideaza_input(n, m, q, matrice, operatii):
        print("Datele de intrare corespund restricțiilor impuse")
        rezultate = aplica_operatii(matrice, operatii)

        with open('amedieout.txt', 'w') as outfile:
            for rezultat in rezultate:
                outfile.write(str(rezultat) + '\n')
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")


if __name__ == "__main__":
    main()