Rezolvare completă PbInfo #2194 identice3

Mihai a construit o matrice pătratică A de dimensiune N cu valori în mulțimea {0,1}. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea A, numărul K de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea A într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul D, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea D din matricea precedentă în care schimbă toate elementele 0 în 1 și invers. El vrea să aplice operația ZET inițial pentru matricea A, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat R, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, R va avea valoarea -1.

Cerința

Mihai vă roagă să calculați valorile K și R. Pentru a preciza tipul cerinței, Mihai folosește un cod T care dacă are valoarea 1, atunci solicită calcularea valorii K, iar dacă T are valoarea 2, atunci solicită calcularea valorii R.

Date de intrare

Fișierul de intrare identice3.in se vor afla numerele naturale T, N și D, cu semnificația de mai sus, separate prin câte un spațiu. Pe următoarele N linii se vor afla câte N valori de 0 și 1, elementele liniilor matricei A, fără spații între ele.

Date de ieșire

Fișierul de ieșire identice3.out se va afla un număr natural, respectiv valoarea K pentru T = 1 sau valoarea R pentru T = 2.

Restricții și precizări

  • 1 < D < N ≤ 1000
  • Pentru calcularea valorii K, submatricele pot fi pătratice sau dreptunghiulare, cu diferite dimensiuni (inclusiv 1), cu elementele identice.

Exemplul 1:

identice3.in

1 4 2
0011
0011
1100
1100

identice3.out

36

Explicație

T = 1, deci se calculează K = 36. Sunt 18 submatrice cu toate elementele 0 și 18 cu toate elementele 1.

Exemplul 2:

identice3.in

2 4 2
0011
0011
1100
1100

identice3.out

2

Explicație

T = 2, deci se calculează R = 2, deoarece sunt necesare 2 aplicări ale operației ZET.

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 identice3:

#include<bits/stdc++.h>
using namespace std;
ifstream in("identice3.in");
ofstream out("identice3.out");
#define Nmax 1005

char a[Nmax][Nmax],a1[Nmax][Nmax];
char opus[]="10";
int t0[Nmax][Nmax],st0[Nmax],val0[Nmax],vf0,n,d;
int t1[Nmax][Nmax],st1[Nmax],val1[Nmax],vf1;
long long sum0,sum1;

int sol0,p0[Nmax],M0[Nmax][Nmax];
int sol1,p1[Nmax],M1[Nmax][Nmax];
int test;
void read()
{
    in>>test>>n>>d; in.get();
    for(int i=1;i<=n;++i)
    {
        in.getline(a[i]+1,n+2);
        for(int j=1;j<=n;++j) a1[i][j]=opus[a[i][j]-'0'];
    }
    in.close();
}

void suma0()
{
    for(int i=1;i<vf0;i++)
         sum0+=val0[i]*st0[i];
}
void suma1()
{
    for(int i=1;i<vf1;i++)
         sum1+=val1[i]*st1[i];
}

void solve0()
{
    int m;
    for(int j=1;j<=n;j++)
    {
        vf0=0;
        for(int i=1;i<=n;i++)
            {
                if(a[i][j]=='0')
                    t0[i][j+1]=1+t0[i][j];
                m=1;
                while(vf0>0&&st0[vf0]>=t0[i][j+1]) {m+=val0[vf0]; vf0--;}
                vf0++; st0[vf0]=t0[i][j+1]; val0[vf0]=m; sum0+=val0[vf0]*st0[vf0];
                suma0();
            }
    }
    //out<<sum0;
}
void solve1()
{
    int m;
    for(int j=1;j<=n;j++)
    {
        vf1=0;
        for(int i=1;i<=n;i++)
            {
                if(a[i][j]=='1')
                    t1[i][j+1]=1+t1[i][j];
                m=1;
                while(vf1>0&&st1[vf1]>=t1[i][j+1]) {m+=val1[vf1]; vf1--;}
                vf1++; st1[vf1]=t1[i][j+1]; val1[vf1]=m; sum1+=val1[vf1]*st1[vf1];
                suma1();
            }
    }
    //out<<sum1;
}

void R0()
{
    int ok=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            M0[i][j]+=M0[i-1][j];
            p0[j]=p0[j-1]+M0[i][j];
            int t=(p0[j]&1);
            if(i>n-d+1||j>n-d+1)
            {
                if(t!=(a[i][j]-'0')) ok=0;
            }
            else if(t!=(a[i][j]-'0'))
            {
                ++sol0;
                M0[i][j]++;
                M0[i+d][j]--;
                M0[i][j+d]--;
                M0[i+d][j+d]++;
                ++p0[j];
            }
        }
    if(!ok) sol0=-1;
}
void R1()
{
    int ok=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            M1[i][j]+=M1[i-1][j];
            p1[j]=p1[j-1]+M1[i][j];
            int t=(p1[j]&1);
            if(i>n-d+1||j>n-d+1)
            {
                if(t!=(a1[i][j]-'0')) ok=0;
            }
            else if(t!=(a1[i][j]-'0'))
            {
                ++sol1;
                M1[i][j]++;
                M1[i+d][j]--;
                M1[i][j+d]--;
                M1[i+d][j+d]++;
                ++p1[j];
            }
        }
    if(!ok) sol1=-1;
}
int main()
{
    read();
    if(test==1)
    {
        solve0();solve1();out<<sum0+sum1<<'\n';
    }
    else
        {
         R0();R1();
         int rx=min(sol0,sol1),ry=max(sol0,sol1); if(rx==-1) rx=ry;
         out<<rx<<'\n';
        }
    out.close();
    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 #2194 identice3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2194 identice3 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!