Enunț

Spunem că două matrice a și b sunt egale dacă au același număr de linii n și același număr de coloane m și pentru orice pereche de indici i, j (1 ≤ i ≤ n, 1 ≤ j ≤ m) a[i][j] = b[i][j].

Cerința

Se dau două seturi de N, respectiv Q matrice binare (cu valori 0 sau 1), pentru fiecare matrice fiind precizat numărul de linii respectiv de coloane. Să se afișeze numărul aparițiilor matricelor din al doilea set în primul.

Date de intrare

Fișierul de intrare qmat.in conține pe prima linie numărul N, urmat de N matrice, M1, M2, … Mn. Pentru fiecare matrice Mi este precizat, pe o linie, separate printr-un spațiu, numărul de linii li, respectiv de coloane ci, iar pe următoarele li linii câte ci cifre binare separate prin câte un spațiu. După cele N matrice se află și numărul Q urmat de asemenea de Q matrice descrise la fel ca și cele anterioare.

Date de ieșire

Fișierul de ieșire qmat.out va conține pe prima linie numărul sol, reprezentând numărul de matrice din al doilea set ce apar în primul.

Restricții și precizări

1 ≤ n,q ≤ 10000
pentru orice matrice dată 1 ≤ nr. de linii, nr. de coloane ≤ 10

Exemplu

qmat.in

5
2 6
0 0 0 1 1 1
1 0 1 1 0 0
7 4
0 0 0 1
0 0 0 0
0 1 1 0
0 1 1 0
1 1 1 1
0 1 0 0
0 1 0 1
5 1
0
0
1
0
1
3 5
0 1 1 1 1
1 1 1 0 0
0 0 1 1 0
9 2
0 1
1 1
1 1
1 0
1 1
0 1
0 1
0 0
1 1
3
3 5
0 1 1 1 1
1 1 1 0 0
0 0 1 1 0
9 2
0 1
1 1
1 1
1 0
1 1
0 1
0 1
0 0
1 1
2 3
1 1 1
1 1 1

qmat.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 qmat:

#include <iostream>
#include <fstream>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream fin("qmat.in");
ofstream fout("qmat.out");
bitset<11>ex[11];
bitset<11>b[11];
struct pm
{
    int s;
    short n,m;
    bitset<11>a[11];
};
pm mt[10001];
int g,p,i,j,q,n,m,s,sol;
short f;
int qx(pm a, pm b)
{
    return a.s<b.s;
}
int lwrbnd(int x)
{
    int s=1,d=g,m;
    while(s<=d)
    {
        m=(s+d)/2;
        if(x<=mt[m].s)
            d=m-1;
        else s=m+1;
    }
    return s;
}
int eg(int n,int m,int p)
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(b[i][j]!=mt[p].a[i][j])return 0;
    return 1;
}
int main()
{
    fin>>g;
    for(p=1;p<=g;p++)
    {
        fin>>mt[p].n>>mt[p].m;
        ex[mt[p].n][mt[p].m]=1;
        for(i=1;i<=mt[p].n;i++)
            for(j=1;j<=mt[p].m;j++)
            {
                fin>>f;
                if(f==1)mt[p].a[i][j]=1;
                else mt[p].a[i][j]=0;
                mt[p].s+=f;
            }
    }
    sort(mt+1,mt+g+1,qx);
    for(fin>>q;q;q--)
    {
        fin>>n>>m;
        s=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                fin>>f;
                if(f==1)b[i][j]=1;
                else b[i][j]=0;
                s+=f;
            }
        if(ex[n][m])
            for(p=lwrbnd(s);mt[p].s==s;p++)
                if(mt[p].n==n && mt[p].m==m)
                    sol+=eg(n,m,p);
    }
    fout<<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 #1629 qmat

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