Fişierul intrare/ieşire:trotuar.in, trotuar.outSursăLot Bistrita 2009, Baraj 3
AutorZoltan SzaboAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test1.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trotuar

Un trotuar de lungime N şi lăţime L trebuie pavat cu dale. Dalele sunt de diferite tipuri, dar din fiecare tip avem o cantitate nelimitată. Lungimea dalelor în cazul fiecărui tip este aceeaşi L, iar lăţimea poate să fie o valoare dintre a1, a2, a3,... ak. Trotuarul are pe suprafaţa lui M zone ocupate, care nu vor fi pavate. Aceste zone au de fiecare dată o formă pătratică de latură 1 (reprezentând locul unor stâlpi, cutii poştale, canale, etc.). Se cunosc coordonatele acestor M puncte (x1,y1), (x2,y2),... (xm,ym). ( x reprezintă coloana, y reprezintă linia punctului).
În exemplele de mai jos vedem trei metode distincte de acoperire a unui trotuar de dimensiuni 6*3 folosind două tipuri de dale: 1*3, respectiv 2*3, având trei zone ocupate pe trotuar, şi anume: (6,2), (3,1), (6,3).

Cerinţă

Cunoscând dimensiunea trotuarului, tipurile de dale disponibile, şi coordonatele zonelor ocupate, să se determine numărul de pavări distincte posibile modulo 666013.

Date de intrare

Fişierul trotuar.in conţine pe prima linie 4 numere naturale N, L, K, şi M separate prin câte un spaţiu, reprezentând lungimea şi lăţimea trotuarului, respectiv numărul tipurilor de dale şi numărul zonelor ocupate. Pe linia următoare avem cele K lăţimi ale tipurilor de dale: a1, a2, a3,..., ak separate prin câte un spaţiu. Următoarele M linii conţin câte două numere naturale separate prin spaţiu, reprezentând câte o coordonată (xi,yi), pentru fiecare zona ocupata.

Date de ieşire

Fişierul trotuar.out va conţine o singură linie, numărul pavărilor distincte modulo 666013.

Restricţii

  • 1 ≤ N ≤ 100000
  • 1 ≤ K ≤ L ≤ 255
  • 1 ≤ a1, a2, a3,..., ak ≤ L sunt distincte două câte două
  • 0 ≤ M ≤ 450
  • Pentru 20% din teste M = 0
  • Se garantează existenţa a cel puţin unei soluţii
  • Se recomandă folosirea întregilor pe 64 de biţi pentru operaţia de înmultire.

Exemplu

trotuar.introtuar.out
6 3 2 3
2 1
6 2
3 1
6 3
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content