Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | marcel.in, marcel.out | Sursă | IIOT 2019-20 Runda 3 |
| Autor | Alexandru Petrescu, Andrei Constantinescu | Adăugată de |  Chichirim George •george_stelian |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Marcel
De cand a inceput sesiunea fiul lui Marcel o tine din petrecere in petrecere. De aceasta data el este pus in fata a N2 bauturi asezate sub forma unui tablou bidimensional cu N linii si N coloane. Se cunoaste continutul de alcool al bauturii de pe linia i, coloana j ca fiind alc[i][j] unitati. Intr-o tura protagonistul are de ales intre a efectua una din 4 actiuni:
- Bea toate bauturile de pe prima linie.
- Bea toate bauturile de pe prima coloana.
- Bea toate bauturile de pe ultima linie.
- Bea toate bauturile de pe ultima coloana.
De sigur, pentru a nu se face de ras, el nu poate efectua o actiune care rezulta in a bea mai putin de X unitati in acea tura. Dupa tura bauturile respective se elimina din matrice si petrecerea continua! In orice moment protagonistul poate alege sa se opreasca (lucru chiar obligatoriu in momentul in care se termina bauturile). A doua zi Marcel a aflat din surse sigure valorile lui N, X si alc si este interesat sa afle numarul de modalitati ANS in care ar fi putut decurge petrecerea, modulo 109 + 7. Doua modalitati sunt considerate diferite daca exista un moment la care fiul lui Marcel a ales sa efectueze actiuni diferite din cele 5 posibile (consuma prima/ultima linie/coloana, sau se opreste).
Date de intrare
Pe prima linie a fisierului de intrare marcel.in se afla N si X, separate prin spatiu. Urmeaza N linii a cate N numere intregi fiecare. Al j-ulea numar de pe linia i reprezinta valoarea lui alc[i][j].
Date de ieşire
Pe prima linie a fisierului de iesire marcel.out se va afla un singur numar ANS, reprezentand numarul de feluri in care poate decurge petrecerea, modulo 109 + 7.
Restricţii
- 1 ≤ N ≤ 120
- 1 ≤ X ≤ 109
- -106 ≤ alc[i][j] ≤ 106
Exemplu
| marcel.în | marcel.out |
|---|---|
| 1 10 23 | 5 |
| 1 23 10 | 1 |
| 2 10 23 23 23 23 | 53 |
| 3 4 1 4 2 3 9 -6 7 8 5 | 62 |
Explicaţie
In primul caz petrecerea va avea o singura runda, in care protagonistul are de ales intre a consuma 23 unitati (lucru posibil in 4 moduri distincte) sau a se opri.
In al doilea caz consumul a doar 10 unitati ar fi de ras, asa ca ramane doar varianta de a se opri.
