#2970
Avem o matrice de dimensiuni N x M
, cu elemente 0
și 1
. Numim segment o secvență de cel puțin două valori 1
aflate una lângă alta, toate pe aceeași linie, sau toate pe aceeași coloană a matricei.
Cerința
Se cere determinarea numărului de perechi de segmente:
1. aflate pe linii distincte ale matricei;
2. aflate pe coloane distincte ale matricei;
Date de intrare
Fișierul paralele.in
conține pe prima linie, separate prin câte un spațiu trei valori naturale, în ordine: T
, N
și M
. Dacă T
este 1
se rezolvă doar cerința 1
, iar dacă T
este 2
se rezolvă doar cerința 2
. Începând cu linia a doua se află elementele matricei, o linie a matricei pe o linie a fișierului. Elementele de pe aceeași linie se separă prin câte un spațiu.
Date de ieșire
Fișierul paralele.out
conține pe prima linie un număr natural reprezentând valoarea cerută.
Restricții și precizări
1 <= T <= 2
- Pentru
30
de puncte se garantează căT = 1
,N = 2
,2 ≤ M ≤ 500
și toate elementele1
de pe oricare dintre linii, dacă există, formează o secvență compactă. - Pentru alte
30
de puncte se garantează căT = 2
,2 ≤ N ≤ 500
,2 ≤ M ≤ 500
și pe oricare coloană sunt maximum două valori de1
alăturate. - Pentru alte
9
puncte se garantează căT = 1
,2 ≤ N ≤ 500
,2 ≤ M ≤ 500
. - Pentru alte
9
puncte se garantează căT = 2
,2 ≤ N ≤ 500
,2 ≤ M ≤ 500
. - Pentru alte
12
puncte se garantează căT = 1
,35.000 ≤ N ≤ 40.000
și8 ≤ M ≤ 10
. - În concurs s-au acordat
10
puncte din oficiu. Aici se acordă pentru exemplul din enunț.
Exemplu
paralele.in
1 5 6 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0
paralele.out
11
Explicație
Prima valoare din fișierul de intrare fiind 1
, ne interesează segmente formate pe linii. Pe prima linie este o secvență de valori 1
formată din trei elemente. Ea produce trei segmente: cel cu primele două valori de 1
, cel cu ultimele două valori de 1
și cel cu toate cele trei valori de 1
. Pe linia a doua nu se găsește niciun segment, nefiind cel puțin două valori 1
alăturate. Pe linia a treia nu se găsește niciun segment, pe linia a patra sunt două segmente iar pe linia a cincea este un singur segment. Numărul cerut se obține astfel: fiecare dintre cele trei segmente de pe prima linie este paralel cu fiecare dintre segmentele de pe a patra și de pe a cincea linie iar segmentele de pe linia a patra sunt paralele cu segmentul de pe ultima linie. Pentru exemplul prezentat, dacă am fi avut T = 2
rezultatul calculat ar fi trebuit să fie 1
(segmentul de pe coloana a doua este paralel cu segmentul de pe coloana a patra).
#include <bits/stdc++.h> using namespace std; #define nMax 50010 #define mMax 1010 ifstream f("paralele.in"); ofstream g("paralele.out"); int n, m, t; long long lin[nMax], col[mMax], lgCol[nMax]; bool a[mMax]; long long peLinii() { int i, j, lg; long long total=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) f>>a[j]; lg=0; for(j=1;j<=m+1;j++) if(a[j]==1) lg++; else lin[i]+=1LL*lg*(lg-1)/2, lg=0; total+=lin[i]; } total=total*(total-1)/2; for(i=1;i<=n;i++) total-=1LL*lin[i]*(lin[i]-1)/2; return total; } long long peColoane() { long long total=0; int i, j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) f>>a[j]; for(j=1;j<=m+1;j++) if(a[j]==1) lgCol[j]++; else col[j]+=1LL*lgCol[j]*(lgCol[j]-1)/2, lgCol[j]=0; } for(j=1;j<=m;j++) { if(lgCol[j]) col[j]+=1LL*lgCol[j]*(lgCol[j]-1)/2; total+=col[j]; } total=total*(total-1)/2; for(j=1;j<=m;j++) total-=1LL*col[j]*(col[j]-1)/2; return total; } int main() { f>>t>>n>>m; if(t==1) g<<peLinii()<<'\n'; else g<<peColoane()<<'\n'; return 0; }