Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | nomem.in, nomem.out | Sursă | Lot Cluj 2009, Baraj 6 |
| Autor | Catalin-Stefan Tiseanu | Adăugată de |  Sima Cotizo •sima_cotizo |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 9216 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Nomem
În urma unei afaceri necurate cu mafiotul Ivan, Lunasorab a suferit un accident suspect de maşină. Din această cauză el se confruntă cu o pierdere temporară a memoriei. Acest lucru este foarte neplăcut, deoarece el trebuia să facă inventarul moşiilor sale de creştere a găinilor. Aceastea au forma unui triunghi isoscel dreptunghic, cu catetele paralele cu axele de coordonate. Mai exact, suprafaţa pe care se găsesc moşiile lui Lunasorab poate fi modelată ca o matrice pătratică de N linii şi N coloane (cu linii şi coloanele numerotate de la 1 la N) de numere naturale, reprezentând coeficientul de inteligenţă al unei găini. Un triunghi isoscel dreptunghic de catetă de lungime L cu originea pe linia x şi coloana y va conţine toate celulele din matrice de linie a şi coloană b cu a ≤ x şi b ≥ y şi cu |a – x| + |b - y| < L.
Pentru Lunasorab gradul de risc al unei moşii (reprezentată ca un triunghi isoscel dreptunghic definit ca mai sus) este dată de valoarea minimă a coeficientului de inteligenţă a unei găini de pe moşia respectivă.
Deoarece momentan Lunasorab nu stă prea bine cu memoria, el vă cere suma gradelor de risc ale tuturor moşiilor modulo 1 000 000 007.
Cerinţă
Ajutaţi-l pe Lunasorab să afle rapid suma tuturor gradelor de risc ale moşiilor sale.
Date de intrare
Pe prima linie a fişierului de intrare nomem.in se găsesc numerele N şi Q, separate prin câte un singur spaţiu, reprezentând dimensiunile matricii, respectiv numărul de moşii ale lui Lunasorab. Pe următoarele N linii, fiecare conţinând N elemente, urmează elementele matricii, separate prin câte un singur spaţiu. Următoarele Q linii conţin câte 3 numere L x y, separate prin câte un singur spaţiu reprezentând moşia cu originea în x y, de latură L.
Date de ieşire
În fişierul de ieşire nomem.out se va găsi un număr natural, reprezentând suma gradelor de risc ale tuturor moşiilor modulo 1 000 000 007.
Restricţii şi precizări
- ... ≤ ... ≤ ...
Exemplu
| nomem.in | nomem.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
