Velika Matrica
vreme | memorija | ulaz | izlaz |
---|---|---|---|
2 s | 64 Mb | standardni izlaz | standardni ulaz |
Prošlo je vreme igre, uživanja i razonode. Prošlo je vreme malih matrica. Danas su računari neverovatno brzi i mogu izvršiti i do komandi u sekundi. Iz tog razloga komisija vam je spremila jednostavan zadatak sa jednom matricom i mnogo interesantnih upita.
U ovom zadatku vam je data matrica dimenzije - matrica ima tačno vrsta i tačno kolona. Za svako () i () vrednost na poziciji () u matrici je definisano na sledeći način :
= ( + ) mod
Operacija predstavlja ostatak koji daje broj pri deljenju sa .
Potrebno je odgovoriti na upita oblika : Naći sumu svih brojeva u podmatrici matrice A sa gornjim levim temenom () i donjim desnim temenom() po modulu . Podmatrica matrice A sa navedenim ograničenjima obuhvata sve elemente takve da važi , .
Opis ulaza
U prvoj liniji standardnog ulaza nalaze se brojevi , , -- broj vrsta matrice , broj kolona matrice i modul opisan u tekstu zadatka, redom. Druga linija standardnog ulaza sadrži broj , broj upita na koje je potrebno odgovoriti. Narednih linija sadrže po četiri broja, koji predstaljaju, redom, vrstu gornjeg levog temena podmatrice, kolonu gornjeg levog temena podmatrice, vrstu donjeg desnog temena podmatrice i kolonu donjeg desnog temena podmatrice.
Opis izlaza
Na standardnom izlazu u redova odgovoriti na upite opisane u tekstu zadatka, tačnije u -toj liniji standardnog izlaza ispisati sumu tražene podmatrice po modulu iz -tog upita.
Primer
Ulaz
5 4 3 3 1 2 4 3 2 3 4 4 3 3 3 3
Izlaz
7 6 0
Objašnjenje primera
Matrica je dimenzija , . Matrica izgleda:
2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0
U prvom upitu, gornje levo teme podmatrice ima koordinate (), dok donje desno teme ima koordinate (). Rešenje ovog upita je: = = .
U trećem upitu jedini broj se nalazi na polju () i on ima vrednost . Rešenje ovog upita je .
Ograničenja
Podzadaci
Test primeri su podeljeni u pet disjunktnih grupa:
- U primerima vrednim 10 poena važiće ograničenje
- U primerima vrednim 10 poena važiće ograničenje
- U primerima vrednim 10 poena važiće ograničenje
- U primerima vrednim 30 poena važiće ograničenje ,
- U primerima vrednim 40 poena nema dodatnih ograničenja.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.