# PBinfo #3824 – Perechi6 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dau două șiruri de numere întregi, ordonate crescător. Șirul x[] contine n numere întregi ordonate crescător, șirul y[] conține m numere întregi ordonate crescător. Să se calculeze numărul de perechi de forma (x[i], y[j]) unde x[i] = y[j] și x[i] ∊ X, respectiv y[j] ∊ Y.

Date de intrare
Fișierul de intrare perechi6.in conține pe prima linie numărul natural n, urmat de cele n elemente ale șirului x[], separate prin câte un spațiu. Pe a două linie numărul natural m, urmat de cele m elemente ale șirului y[], separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire perechi6.out va conține pe prima linie numărul p, reprezentând numărul de perechi de elemente cerut.

Restricții și precizări

1 ≤ n, m ≤ 100.000
-1.000.000.000 ≤ x[i], y[j] ≤ 1.000.000.000

Exemplu:
perechi6.in


5 1 2 3 4 5
6 1 2 2 3 3 4
perechi6.out

6
Explicație
În fișierul de intrare sunt 6 perechi de numere care îndeplinesc condițiile din enunț: (1,1), (2,2), (2,2), (3,3), (3,3), (4,4).

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("perechi6.in");
ofstream g("perechi6.out");
int a[100001],b[100001];
long long aa[100001],bb[100001];
int main()
{
    int n,m,i,j,p=0,nr;
    long long perechi=0;
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    f>>m;
    for(i=1; i<=m; i++)
        f>>b[i];
    nr=1;
    j=1;
    for(i=2; i<=n; i++)
        if(a[i-1]==a[i])nr++;
        else
        {
            aa[j]=nr;
            nr=1;
            j=i;
        }
    aa[j]=nr;
    nr=1;
    j=1;
    for(i=2; i<=m; i++)
        if(b[i-1]==b[i])nr++;
        else
        {
            bb[j]=nr;
            nr=1;
            j=i;
        }
    bb[j]=nr;
    i=1;
    j=1;
    while(j<=m &&i<=n)
    {
        if(a[i]==b[j])
        {
            perechi=perechi+aa[i]*bb[j];
            i=i+aa[i];
            j=j+bb[j];
        }
        else if(a[i]<b[j])i=i+aa[i];
        else j=j+bb[j];
    }
    g<<perechi;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3824)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3824/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3824/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)