2564 - Macara

O macara industrială automatizată execută operații de mutare a unor containere aflate într-un depozit de materiale. Acest depozit poate fi reprezentat ca o matrice dreptunghiulară cu m linii şi n coloane, fiecare element al matricei reprezentând un container. Mai exact, elementul situat pe linia i(1 ≤ i ≤ m) şi coloana j (1 ≤ j ≤ n) din matrice reprezintă numărul de dale de granit aflate în containerul situat în depozit pe poziția corespunzătoare. Toate dalele aflate în acelaşi container au aceeaşi culoare. În containerele cu dale negre, numărul de dale conținute este prim, în timp ce în containerele cu dale albe, numărul de dale conținute nu este prim. Primul container cu dale negre situat pe fiecare linie a matricei (dacă un astfel de container există) are un senzor special. Dalele din containere trebuie să fie transportate de către macara spre un terminal. Macaraua poate executa cel mult K comenzi. La o comandă, macaraua va colecta toate dalele aflate în containerele situate într-o zonă dreptunghiulară din depozit. Mai exact, o comandă are forma i1 j1 i2 j2, unde (i1, j1) reprezintă coordonatele containerului aflat în colțul din stânga-sus (linia, respectiv coloana), iar (i2, j2) coordonatele containerului aflat în colțul din dreapta-jos ale zonei dreptunghiulare. Macaraua ar trebui să care la un terminal toate dalele conținute în containere situate în pozițiile (i, j) pentru care i1 ≤ i ≤ i2 şi j1 ≤ j ≤ j2. Însă, macaraua are un defect de funcționare. Pentru fiecare comandă, atunci când ajunge la un container cu dale negre, dacă acest container nu are senzor special nu va transporta la terminal dalele conținute de acesta. După executarea unei comenzi, un robot va umple din nou containerele golite cu acelaşi număr de dale pe care le avea inițial, aceste dale având exact aceeaşi culoare cu cea inițială.

Cerința

Calculați și afișați:

a) S – Suma dalelor negre din containerele cu senzor special de pe fiecare linie.

b) M – numărul maxim de dale pe care le poate transporta macaraua la terminal din cele k comenzi diferite.

c) Comanda optimă de forma: i1 j1 i2 j2 din cele k, pentru care macaraua transportă un număr maxim de dale M aduse la terminal. Dacă sunt mai multe comenzi optime afișați-le pe fiecare în ordinea apariției lor, urmate de numărul de ordine al comenzii din cele k comenzi date.

Date de intrare

Din fișierul de intrare macara.in se citesc pe prima linie m și n reprezentând dimensiunile matricei. Se citesc apoi elementele matricei ce reprezintă numărul de dale din fiecare container. Citim apoi pe o linie separată numărul k iar pe următoarele k linii câte o comandă cu cele patru poziții : i1 j1 i2 j2

Date de ieșire

a) Pe prima linie a fișierului macara.out se afișează numărul S conform cerinței a).

b) Pe a doua linie numărul M conform cerinței b).

c) Pe următoarea linie/linii, comanda/comenzile optime de forma: i1 j1 i2 j2 urmate de numărul de ordine conform cerinței c).

Restricții și precizări

• 1 ≤ i1 ≤ i2 ≤ m, 1 ≤ j1 ≤ j2 ≤ n, 1 ≤ m ≤ 1000, 1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000
• numărul de dale aflate într-un container ≤ 5000
• comenzile nu sunt unice, orice comandă se poate repeta
• se asigură 20% din punctaj pentru rezolvarea corectă a cerinței a)
• pentru 30% din teste 1 ≤ n ≤ 250, 1 ≤ m ≤ 250, 1 ≤ k ≤ 250

Exemplu:

macara.in

5 6
6 2 5 7 12 13
3 9 15 11 4 3
18 7 9 3 31 9
15 5 5 13 4 6
8 6 11 10 23 7
5
1 2 4 4
2 1 3 5
2 2 4 5
2 1 3 5 
1 3 5 5

macara.out

28
65
2 1 3 5 2
2 1 3 5 4
1 3 5 5 5

Explicație

a) Calculăm de pe fiecare linie suma dalelor din primul container cu dale negre astfel: 2+3+7+5+11=28

b) Maximul obținut din suma dalelor care ajung la terminal este 65

c) Acest maxim este obținut din trei comenzi : primele două sunt identice pe pozițiile 2 și 4:

2 1 3 5 2 și 2 1 3 5 4 cu suma 3 + 9 + 15 + 4 + 18 + 7 + 9 = 65

1 3 5 5 5 – cu suma 12 + 15 + 4 + 9 + 4 + 11 + 10 = 65 și este comanda de pe poziția 5 din k = 5 comenzi inițiale date.

Numerele subliniate reprezintă dale negre care aparțin containerelor care nu pot ajunge la terminal

Încărcare soluție

Lipește codul aici

import numpy as np

NMax = 5005
Nk = 1001
a = np.zeros((Nk, Nk))
ti1 = np.zeros(Nk)
ti2 = np.zeros(Nk)
tj1 = np.zeros(Nk)
tj2 = np.zeros(Nk)
Poz = np.zeros(Nk)
i1 = 0
i2 = 0
j1 = 0
j2 = 0
n = 0
t = 0
m = 0
k = 0
nr = 0
sp = 0
b = np.zeros((Nk, Nk))
w = np.zeros(NMax)
ok = False

def sieve_of_eratosthenes():
    for i in range(2, NMax):
        if w[i] == 0:
            for j in range(i*i, NMax, i):
                w[j] = 1
    w[1] = 1

def main():
    with open("macara.in", "r") as f, open("macara.out", "w") as g:
        m, n = map(int, f.readline().split())
        sieve_of_eratosthenes()
        
        for i in range(1, m+1):
            s = 0
            ok = True
            for j in range(1, n+1):
                a[i][j] = int(f.readline())
                if ok and w[a[i][j]] == 0:
                    ok = False
                    sp += a[i][j]
                    s += a[i][j]
                    b[i][j] = s
                if w[a[i][j]] == 1:
                    s += a[i][j]
                    b[i][j] = s
                else:
                    b[i][j] = s
        
        k = int(f.readline())
        
        maxx = 0
        for t in range(1, k+1):
            i1, j1, i2, j2 = map(int, f.readline().split())
            s = 0
            for i in range(i1, i2+1):
                s += b[i][j2] - b[i][j1-1]
            if s > maxx:
                maxx = s
                nr = 1
                ti1[nr] = i1
                tj1[nr] = j1
                ti2[nr] = i2
                tj2[nr] = j2
                Poz[nr] = t
            elif s == maxx:
                nr += 1
                ti1[nr] = i1
                tj1[nr] = j1
                ti2[nr] = i2
                tj2[nr] = j2
                Poz[nr] = t
        
        g.write(str(sp) + "\n")
        g.write(str(maxx) + "\n")
        for i in range(1, nr+1):
            g.write(f"{ti1[i]} {tj1[i]} {ti2[i]} {tj2[i]} {Poz[i]}\n")

if __name__ == "__main__":
    main()