Fişierul intrare/ieşire:engineer.in, engineer.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorPatrick SavaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test6 secLimită de memorie511384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Engineer

Intr-un univers plin de tractoare, este nevoie de un inginer (in engleza, "engineer") iscusit care se poate ocupa de intretinerea acestora. Fiecare tractor de pe lumea aceasta are nevoie de afectiune, la fel ca cel de mai jos.

Desigur, probabil ca va intrebati cum de omenirea a ajuns sa depinda atat de mult de existenta acestor masinarii care scot mult fum. Dupa implementarea cu succes a unui robot capabil sa rezolve orice problema de algoritmica (folosind machine learning), inclusiv cele NP-complete, majoritatea programatorilor au decis sa isi ocupe timpul liber facand agricultura. Astfel, lucrurile s-au schimbat radical: in loc sa iti doresti sa implementezi o problema cat mai rapid sau corect (precum se intampla la o competitie de ACM), acum castigatorul duelului este acela a carui plantatie este cea mai productiva.

Cum solutia perfecta niciodata nu exista, modul in care productivitatea plantatiei unui programator este evaluata, nu este cel mai corect si difera de la caz la caz. Fiecare programator detine o plantatie ce poate fi privita ca o submatrice a unei matrice de N x M, in care fiecare celula (i, j) cu 1iN si 1jM retine o valoare, reprezentand indicele de productivitate al acelei celule. In continuare, in stabilirea productivitatii medii a unui programator i, inginerul nostru va avea de calculat care este a Ki-a cea mai mica valoare dintre cele care se afla in plantatia acestuia. Inainte de a da startul acestei competitii nonconformiste intre programatori, trebuie sa ne asiguram ca al nostru inginer este suficient de brav incat poate calcula productivitatea fiecarui programator in parte.

Cerinta

Avand o matrice de N x M, se cere gasirea celei de a Ki-a (cu 1iQ) celei mai mici valori pentru Q submatrici date. O submatrice este caracterizata de (x1, y1, x2, y2), celulele (x1, y1) si (x2, y2) reprezentand coltul stanga-sus, respectiv coltul dreapta-jos. Orice submatrice poate fi privita ca un vector, deci a Ki-a valoare pentru o submatrice data este valoarea care s-ar afla pe pozitia Ki daca am sorta vectorul.

Date de intrare

Fişierul de intrare engineer.in va contine pe prima linie doua numere naturale N si M, reprezentand dimensiunile matricei. Urmatoarele N linii vor contine cate M numere naturale, reprezentand valorile indicilor de productivitate ale fiecarei celule in parte. Dupa acestea, va urma o linie pe care se va afla un numar Q, reprezentand numarul de programatori. Urmatoarele Q linii vor contine cate cinci numere naturale x1, y1, x2, y2, Ki, reprezentand coltul-stanga sus si coltul-dreapta jos al plantatiei alocate fiecaruia dintre cei Q programatori, cat si Ki, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire engineer.out vor fi Q linii, pe fiecare dintre acestea aflandu-se o valoare reprezentand productivitatea medie pentru fiecare programator in parte, pe cea de a i-a linie aflandu-se solutia pentru cel de al i-lea programator.

Restricţii

  • 1N1100
  • 1M1100
  • 1Q1000
  • 1x1x2N
  • 1y1y2M
  • 1Ki(x2 - x1 + 1) * (y2 - y1 + 1)
  • Valorile din matrice sunt numere naturale cuprinse intre 1 si 109
  • Programatorii pot avea aceleasi plantatii sau plantatiile lor se pot suprapune
  • In cazul in care doi programatori i si j detin exact aceeasi plantatie, nu este garantat ca Ki este egal cu Kj

Exemplu

engineer.inengineer.out
2 2
3 2
1 2
4
1 1 2 2 1
1 1 2 2 2
1 1 2 2 3
1 1 2 2 4
1
2
2
3

Explicaţie

Toti programatorii au exact aceeasi plantatie. Cea mai mica valoare din matrice este 1, a doua cea mai mica este 2, etc.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?