Se consideră o matrice cu L linii și C coloane care memorează doar valori din mulțimea {0,1,2}. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 și egal cu numărul valorilor de 2. De exemplu, în matricea

0 1 2 0
1 2 0 1

sunt șase submatrice omogene, acestea fiind:

0 1 2
1 2 0

1 2 0
2 0 1

0 1 2

1 2 0

1 2 0

2 0 1

Submatricele a treia și a patra sunt formate din prima linie a matricei inițială, iar submatricele a cincea și a șasea sunt formate din a doua linie.

Cerința

Să se determine câte submatrice nevide omogene există.

Date de intrare

Fișierul de intrare omogene.in conține pe prima linie numerele naturale L și C. Pe următoarele L linii se află câte C numere naturale separate prin spații reprezentând câte o linie din matrice.

Date de ieșire

Fișierul de ieșire omogene.out va conține pe prima linie un singur număr natural reprezentând numărul submatricelor nevide omogene.

Restricții și precizări

2 <= L <= C <= 5000
4 <= L * C <= 65536
Atenție, o submatrice este formată dintr-o secvență continuă de linii și coloane, deci, de exemplu, dacă se aleg dintr-o matrice liniile 1, 2 și 5, atunci acestea nu formează o submatrice.
Numărul submatricelor omogene va fi mai mic decât 2*10⁹
Întreaga matrice poate fi submatrice omogenă

Exemplul 1

omogene.in

2 4
0 1 2 0
1 2 0 1

omogene.out

Explicație

Cele șase submatrice au fost menționate în enunț.

Exemplul 2

omogene.in

omogene.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Omogene:

#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("omogene.in");
ofstream g("omogene.out");
struct nod
    {
        int d01,d12,d20;
    };
inline bool test(const nod &t1,const nod &t2){

return t1.d01<t2.d01 || (t1.d01==t2.d01 &&
                         t1.d12<t2.d12) ||
                         (t1.d01==t2.d01 &&
                         t1.d12==t2.d12  && t1.d20<t2.d20);
}

nod v[10001];
int a[318][10001];
int z[318][10001],u[318][10001];
int t0,t1,t2,st0,st1,st2;
long long sol;
int n,m;
void citire()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            f>>a[i][j];
    f.close();
}
void prelucrare()
{
    for(int i=1;i<=n;++i)
       for(int j=1;j<=m;++j)
        {
            z[i][j]=z[i-1][j]+(a[i][j]==0);
            u[i][j]=u[i-1][j]+(a[i][j]==1);
        }
    for(int k=1;k<=n;++k)
       for(int p=k;p<=n;++p)
       {
           int d=p-k+1;
           st0=st1=st2=0;
           v[0].d01=v[0].d12=v[0].d20=0;
           for(int j=1;j<=m;++j)
           {
               t0=z[p][j]-z[k-1][j];st0+=t0;
               t1=u[p][j]-u[k-1][j];st1+=t1;
               t2=d-t0-t1;st2+=t2;
               v[j].d01=st0-st1;
               v[j].d12=st1-st2;
               v[j].d20=st2-st0;
           }
           sort(v,v+m+1,test);
           int x=1;
           for(int i=1;i<=m;++i)
            if(v[i-1].d01==v[i].d01 && v[i-1].d12==v[i].d12 &&
               v[i-1].d20==v[i].d20) x++;
            else
            {
                sol=sol+1ll*x*(x-1)/2;
                x=1;
            }
            sol=sol+1ll*x*(x-1)/2;
       }
}
int main()
{
    citire();
    prelucrare();
    g<<sol<<'\n';
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1687 Omogene

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1687 Omogene de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1687 Omogene