Fişierul intrare/ieşire:sarpe2.in, sarpe2.outSursăAlgoritmiada 2012, Runda 1
AutorCosmin GheorgheAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sarpe2

HM are o matrice de NxN elemente şi un vector de M elemente distincte. El doreşte să potrivească vectorul peste matrice ca şi cum acesta ar fi un şarpe: alege o pozitie (x, y) pentru începutul vectorului şi apoi potriveşte restul elementelor ducându-se în oricare dintre cele opt elemente adiacente ale poziţiei curente (bineînteles fără a ieşi din matrice).
HM ar dori să ştie în câte moduri poate potrivi vectorul peste matricea dată.

Date de intrare

Fişierul de intrare sarpe2.in se află doua numere N şi M reprezentând dimensunea matricei, respectiv dimensiunea vectorului de potrivit.
A doua linie din fişier conţine M elemente distincte reprezentând elementele vectorului de potrivit.
Următoarele N linii, cu N elemente fiecare, descriu matricea, elementul j de pe linia i reprezentând valoarea de pe linia i şi coloana j a matricei.

Date de ieşire

În fişierul de ieşire sarpe2.out trebuie afişat numarul de moduri în care vectorul se poate potrivi peste matrice modulo 666013.

Restricţii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ M ≤ 100.000
  • Vectorul si matricea conţin elemente în intervalul [0, 100.000]

Exemplu

sarpe2.insarpe2.out
4 3
1 5 4
0 1 5 4
1 5 4 3
4 7 8 2
0 5 4 1
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content