Fişierul intrare/ieşire:matrice2.in, matrice2.outSursăONI 2009, clasele 11-12
AutorPaul-Dan BaltescuAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test1.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Matrice 2

Laura a primit de ziua ei o matrice pătratică de dimensiuni NxN de numere întregi. Neştiind ce să facă cu ea, a început să-şi pună diverse întrebări. Fata consideră că un drum de la (x1, y1) la (x2, y2) este o secvenţă de celule care începe în celula (x1, y1), se termină în (x2, y2) şi oricare două celule consecutive au o latură în comun (deplasarea se poate face spre nord, est, sud, vest). Laura a definit costul unui drum ca fiind valoarea minimă a unei celule de pe acel drum. Apoi ea a început să-şi pună Q întrebări de forma: Care este costul maxim pe care îl poate avea un drum de la (x1, y1) la (x2, y2)? Întrebările au început să i se pară dificile şi vă cere ajutorul.

Aflaţi răspunsul pentru fiecare dintre cele Q întrebări.

Date de intrare

Pe prima linie a fişierului de intrare matrice2.in se află 2 numere întregi N si Q cu semnificaţia din enunţ. Pe următoarele N linii se află câte N numere întregi reprezentând matricea primită de Laura. Fiecare dintre următoarele Q linii conţine câte patru numere întregi x1 y1 x2 y2 care descriu câte o întrebare.

Date de ieşire

În fişierul de ieşire matrice2.out se află răspunsul la cele Q întrebări, câte unul pe linie, în aceeaşi ordine în care au apărut în fişierul de intrare.

Restricţii

  • 1 ≤ N ≤ 300
  • 1 ≤ Q ≤ 20.000
  • Elementele matricei sunt numere întregi cuprinse între 1 şi 1.000.000.
  • Pentru 15% din teste N ≤ 50, Q ≤ 10 şi valorile matricei sunt cuprinse între 1 şi 250.
  • Pentru alte 20% din teste N ≤ 100, Q ≤ 100.
  • Nu există nicio întrebare pentru care perechea (x1, y1) să coincidă cu perechea (x2, y2).

Exemplu

matrice2.inmatrice2.out
5 3
9 5 9 8 7
2 1 1 3 8
1 3 9 4 6
4 1 8 6 7
2 4 5 5 6
1 1 3 3
5 5 1 5
2 2 4 3
5
6
1

Explicaţie

Pentru prima întrebare răspunsul este dat de următorul drum:
9 5 9 8 7
2 1 1 3 8
1 3 9 4 6
4 1 8 6 7
2 4 5 5 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content