# PBinfo #4375 – div11 – Rezolvare C++

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

## Enunț

Se consideră N numere naturale nenule a1, a2, …, aN.

Cerința
Să se determine numărul de perechi de indici (i,j), 1 ≤ i, j ≤ N, i ≠ j , cu proprietatea că, dacă am alipi numărul aj la finalul numărului ai, obținem un număr divizibil cu 11. Perechile (i,j) și (j,i) se consideră diferite.

Date de intrare
Fişierul de intrare  div11.in  conţine pe prima linie numărul natural  N. Pe următoarea linie se află cele N numere naturale nenule a1, a2, …, aN, separate prin câte un spaţiu.

Date de ieșire
Fișierul de ieșire div11.out va conţine o singură linie pe care va fi scris numărul de perechi cu proprietatea din enunţ.

Restricții și precizări

1 ≤ N ≤ 100.000
Numerele de pe a doua linie a fișierului de intrare sunt mai mici sau egale cu 1017. Vom nota numărul maxim de cifre pe care le poate avea un număr cu C.
Pentru 12 puncte, N ≤ 1000, C ≤ 3
Pentru 12 puncte, N ≤ 1000, C ≤ 8
Pentru 16 puncte, N ≤ 1000, C ≤ 17
Pentru 7 puncte, N ≤ 100.000, C = 1
Pentru 17 puncte, N ≤ 100.000, C ≤ 3
Pentru 36 puncte, N ≤ 100.000, C ≤ 17

Exemplul 1:
div11.in

7
1 2 1 3 3 1 2
div11.out

10
Explicație
Numerele divizibile cu 11 care se pot obține sunt: 11 (de 6 ori pentru perechile de indici (1,3), (1,6), (3,6), (3,1), (6,1) și (6,3)), 22 și 33.

Exemplul 2:
div11.in

5
14 120 32 8 3
div11.out

3
Explicație
Numerele divizibile cu 11 care se pot obține sunt: 143, 32120, 814.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("div11.in");
ofstream fout("div11.out");
typedef long long ll;
ll f[2][12];// 0 -> restul 1 la inmultire, 1 -> restul 10 la inmultire
ll v[100005],n;
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i];
        ll aux=v[i];
        ll nrcif=0;
        while(aux)
        {
            nrcif++;
            aux/=10;
        }
        f[nrcif%2][v[i]%11]++;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ll aux=v[i];
        ll nrcif=0;
        while(aux)
        {
            nrcif++;
            aux/=10;
        }
        f[nrcif%2][v[i]%11]--;
        ll rest=v[i]%11;
        ll need=(11-rest)%11;
        ans+=f[0][need];
        rest=((v[i]%11)*10LL)%11;
        need=(11-rest)%11;
        ans+=f[1][need];
        f[nrcif%2][v[i]%11]++;
    }
    fout<<ans;
    return 0;
}
```

## Resurse

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