Pracsiu Dan (dnprx) Se consideră un şir format din M x N termeni a căror valoare poate fi 0 sau 1, cele Q poziţii în care se găsesc termenii egali cu 1 fiind P1, P2, …, PQ. Termenii şirului sunt memorați într-o matrice inițială cu M linii și N coloane, astfel încât șirul se obține dacă se parcurge matricea linie cu linie, în ordine, de sus în jos, și fiecare linie de la stânga la dreapta. Pentru un număr K dat, se obține o matrice nouă, cu M • K linii și N coloane, prin scrierea matricei inițiale de K ori, de sus în jos, astfel încât fiecare copie este plasată sub cea de la pasul anterior.
Un grup-1 în matrice este format din una sau mai multe valori 1 și se consideră că două valori egale cu 1 fac parte din acelaşi grup-1 dacă se poate ajunge de la una la cealaltă parcurgând matricea pe un traseu format doar din elemente egale cu 1, astfel încât oricare două elemente parcurse consecutiv să fie pe aceeași linie și coloane vecine sau pe aceeași coloană și linii vecine. De exemplu, dacă M = 2, N = 4, Q = 4, P1 = 1, P2 = 3, P3 = 7, P4 = 8, şirul va avea 8 termeni, 1 0 1 0 0 0 1 1, iar pentru K având valorile 1, 2, respectiv 3, matricea formată va fi:
Cele trei matrice au 2, 3, respectiv 4 grupuri-1. Cele 3 grupuri-1 din a doua matrice sunt formate cu elementele: {(1,1), (3,1)}, respectiv {(1,3), (2,3), (2,4), (3,3), (4,3), (4,4)}, elementele din acelaşi grup-1 având aceeaşi culoare.
Cerința
Se cere numărul grupurilor-1 din matricea cu M •K linii şi N coloane formată.
Date de intrare
Fișierul de intrare unuzero.in conține, în această ordine, pe prima linie numerele M N K Q, iar pe a doua linie cele Q numere P1, P2, …, PQ, separate prin câte un spaţiu.
Date de ieșire
În fișierul de ieșire unuzero.out se afişează numărul grupurilor-1 cerut.
Restricții și precizări
1 ≤ M, N, K ≤ 1.000.000.0001 ≤ Q ≤ min(M • N, 100.000)1 ≤ P1,P2, …,PQ≤ M • N- Pentru 65 de puncte,
M = 1,1 ≤ N ≤ 100,K = 1,Q = 2 - Pentru 3 puncte,
M = 1,1 ≤ N ≤ 100,K = 1 - Pentru 2 puncte,
M = 1,1 ≤ N ≤ 100.000 - Pentru 7 puncte,
1 ≤ M, N ≤ 1.000,K = 1 - Pentru 2 puncte,
M = 1 - Pentru 4 puncte,
M = 1,1 ≤ M • K ≤ 1.000,1 ≤ N ≤ 1.000 - Pentru 5 puncte,
K = 1 - Pentru 6 puncte,
1 ≤ M, N ≤ 1.000 - Pentru 6 puncte, fără alte restricții
Exemplul 1:
unuzero.in
1 5 1 2 3 5
unuzero.out
2
Explicație
Pentru primul exemplu termenii egali cu 1 sunt pe poziţiile 3 şi 5, deci şirul este 0 0 1 0 1, iar matricea formată are o linie şi 5 coloane, conţine două grupuri-1 şi este:
Exemplul 2:
unuzero.in
3 4 1 5 2 5 7 8 11
unuzero.out
3
Explicație
Pentru al doilea exemplu termenii egali cu 1 sunt pe poziţiile 2, 5, 7, 8 şi 11, deci şirul este 0 1 0 0 1 0 1 1 0 0 1 0, iar matricea formată are 3 linii şi 4 coloane, conţine trei grupuri-1 şi este:
Exemplul 3:
unuzero.in
2 5 3 4 1 4 7 9
unuzero.out
7
Explicație
Pentru al treilea exemplu termenii egali cu 1 sunt pe poziţiile 1, 4, 7 şi 9, deci şirul este 1 0 0 1 0 0 1 0 1 0, iar matricea formată are 6 linii şi 4 coloane (cele 2 linii au fost multiplicate de 3 ori), conţine 7 grupuri-1 şi este:
