# PBinfo #3397 – gard2 – Rezolvare C++

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

## Enunț

Mihăiță s-a hotărât să își construiască un gard perfect cu ajutorul lui Dorel – un constructor renumit.
Un gard perfect trebuie  să respecte următoarele cerințe:
1. Gardul să fie format din N scânduri de înălțimi nu neapărat egale;
2. Scândurile pot fi așezate în orice ordine;
3. Există un număr egal de scânduri pentru fiecare înălțime;
Mihăiță acceptă un gard ca fiind perfect dacă respectă condițiile de mai sus înainte sau după eliminarea unei singure scânduri.

Cerința
Ajutați-l pe Mihăiță să verifice perfecțiunea celor T garduri propuse de Dorel.

Date de intrare
Pe prima linie  din fișierul gard.in se află un număr natural T, reprezentând numărul gardurilor propuse de Dorel. Pe următoarele T linii se află un număr natural N, urmat de N valori Hi separate printr-un singur spațiu, reprezentând înălțimile scândurilor gardului propus de Dorel. 

Date de ieșire
Fișierul de ieșire gard.out va conține T linii, pe fiecare linie fiind afișat 1 dacă gardul este perfect, 0 altfel.

Restricții și precizări

1 ≤ T ≤ 10
Primele teste, 1 ≤ N ≤ 1.000.000, 1 ≤ Hi ≤ 10.000
Următoarele teste, 1 ≤ N ≤ 100.000, 1 ≤ Hi ≤ 1.000.000.000
Datorită dimensiunii mari ale testelor, doar unele dintre ele au fost încărcate.

Exemplu:
gard.in

4
6 2 2 3 3 4 4
6 2 3 3 5 5 5
7 3 3 4 4 4 5 5
8 3 3 3 4 4 5 5 5
gard.out

1
0
1
0
Explicație
1: Există un număr egal de scânduri pentru fiecare înălțime
0: Gardul nu poate fi perfect nici înainte și nici după eliminarea oricărei scânduri
1: Gardul devine perfect după eliminarea unei scânduri de înălțime 4
0:  Gardul nu poate fi perfect nici înainte și nici după eliminarea oricărei scânduri

## Cod sursă C++

```cpp
// Sursa: Dragan Andrei-Gabriel
#include <bits/stdc++.h>
using namespace std;
int t, n, k, ans, frecv[10005], a, b, nrA, nrB, v[100005];
int main()
{
    freopen("gard.in", "r", stdin);
    freopen("gard.out", "w", stdout);
    scanf("%d", &t);
    while (t--)
    {
        a = b = -1;
        nrA = nrB = 0;
        ans = 1;
        scanf("%d", &n);
        if (n <= 100000)
        {
            for (int i = 1; i <= n; i++)
            {
                scanf("%d", &v[i]);
            }
            sort(v + 1, v + n + 1);
            int temp = 1;
            int index = 1;
            while (index <= n)
            {
                while (v[index] == v[index + 1] && index <= n)
                    temp++, index++;
                if (temp > 0)
                {
                    if (a == -1)
                        a = temp; else
                        if (a == temp)
                            nrA++; else
                        if (a != -1 && a != temp && b == -1)
                            b = temp; else
                                if (b == temp)
                                    nrB++; else
                            if (a != -1 && b != -1 && a != temp && b != temp)
                                {
                                    ans = -1;
                                    break;
                                }
                }
                index++;
                temp = 1;
            }
            if (b != -1 && ans != -1)
            {
                if (abs(a - b) > 1)
                    ans = 0;
                if (a < b && (nrA - nrB != 1) && (nrA - nrB != 0))
                    ans = 0;
                if (b < a && (nrB - nrA != 1) && (nrB - nrA != 0))
                    ans = 0;
            }
            if (b != -1 && ans != -1 && ((nrA == 0 && a == 1) || (b == 1 && nrB == 0)))
                ans = 1;
            if (b != -1 && ans != -1 && (nrB == 0 && ((b - a == 1) || (b - a == 0))))
                ans = 1;
            if (b != -1 && ans != -1 && (nrA == 0 && ((a - b == 1) || (a - b == 0))))
                ans = 1;
        } else
        {
            memset(frecv, 0, sizeof(frecv));
            for (int i = 1; i <= n; i++)
            {
                scanf("%d", &k);
                frecv[k]++;
            }
            for (int i = 1; i <= 10000; i++)
            if (frecv[i] > 0)
            {
                if (a == -1)
                    a = frecv[i]; else
                    if (a == frecv[i])
                        nrA++; else
                    if (a != -1 && a != frecv[i] && b == -1)
                        b = frecv[i]; else
                            if (b == frecv[i])
                                nrB++; else
                        if (a != -1 && b != -1 && a != frecv[i] && b != frecv[i])
                            {
                                ans = -1;
                                break;
                            }
            }
            if (b != -1 && ans != -1)
            {
                if (abs(a - b) > 1)
                    ans = 0;
                if (a < b && (nrA - nrB != 1) && (nrA - nrB != 0))
                    ans = 0;
                if (b < a && (nrB - nrA != 1) && (nrB - nrA != 0))
                    ans = 0;
            }
            if (b != -1 && ans != -1 && ((nrA == 0 && a == 1) || (b == 1 && nrB == 0)))
                ans = 1;
            if (b != -1 && ans != -1 && (nrB == 0 && ((b - a == 1) || (b - a == 0))))
                ans = 1;
            if (b != -1 && ans != -1 && (nrA == 0 && ((a - b == 1) || (a - b == 0))))
                ans = 1;
        }
        printf("%d\n", ans >= 1);
    }
    return 0;
}
```

## Resurse

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