fbpx

Problema #2440 – puzzle – Rezolvari PBInfo

de Mihai-Alexandru

Mihai a primit de ziua lui un joc de puzzle. Jocul are N piese confecţionate prin lipirea unor bucăţi de dimensiune 1x1 (ilustrate în figurile de mai jos prin X); aceste bucăţi le vom numi în continuare, pe scurt, X-uri. Pentru confecţionarea unei piese se respectă următoarele reguli:

Exemplu

puzzle.in

5
222 432 234 123 111

puzzle.out

3

Explicație

Se pot îmbina 3 perechi de piese: piesa 1 cu piesa 5, piesa 2 cu piesa 3, piesa 2 cu piesa 4. Piesele 3 și 4 s-ar putea îmbina corect dacă una dintre ele ar fi răsturnată stânga-dreapta sau rotită, dar acest lucru nu e permis.

#include <bits/stdc++.h>
using namespace std;

ifstream fin("puzzle.in");
ofstream fout("puzzle.out");

long long int f[100001] , v[100001] , frecv[12];
long long int rez , n , k;

int fa(int numar)
{
    long long int t = 0, mi = 9;
    while (numar)
    {
        frecv[++t] = numar % 10;
        numar /= 10;
        if (frecv[t] < mi)
            mi = frecv[t];
    }
    long long int r = 0;
    for (int i = t ; i >= 1 ; i--)
        r = r * 10 + (frecv[i] - mi);
    return r;
}

int intoarce(int code, int k)
{
    long long int t = 0 , aux = code , ma = 0;
    for (int i = 1 ; i <= k ; i++)
    {
        frecv[++t] = aux%10;
        aux /= 10;
        ma = max(ma, frecv[t]);
    }
    long long int r = 0;
    for (int i = t; i >= 1; i--)
        r = r * 10 + (ma - frecv[i]);
    return r;
}

int lungime_nr(int n)
{
    long long int cnt = 0;
    while (n)
        cnt++ , n /= 10;
    return cnt;
}

int main ()
{
    fin >> n;
    for (int i = 1 ; i <= n ; i++)
    {
        fin >> v[i];
        if (i == 1)
            k = lungime_nr(v[i]);
        f[fa(v[i])]++;
    }
    rez = 0;
    for (int i = 1 ; i <= 100000 ; i++)
        rez += 1LL * f[i] * f[intoarce(i, k)];
    rez /= 2;
    rez += 1LL * f[0] * (f[0] - 1) / 2;
    fout << rez << endl;
    return 0;
}
Comentarii

S-ar putea sa iti placa