gard2 pbinfo #3397
Indicatii:
Problema gard2 – descrierea soluției
Rezolvarea problemei pornește prin calcularea frecvențelor înălțimilor scândurilor.
Având în vedere restricțiile problemei:
1. pentru 50% din teste putem folosi un vector de frecvență (înălțimile scândurilor și restricțiile de memorie ne permit alocarea unui vector de frecvență cu 10.000 de elemente); Complexitate: timp O(N), spațiu O(Hmax).
2. pentru restul de 50% dintre teste unde înălțimile scândurilor pot fi numere de până la 1.000.000.000, calcularea frecvențelor se face prin sortarea vectorului de înălțimi sau prin folosirea unei tabele hash, dar nu este cazul la clasele 7-8 :). Complexitate: timp O(N log N), spațiu O(N).
Având calculate frecvențele înălțimilor putem acum spune dacă un gard este sau nu perfect.
Pentru 50% din totalul testelor, trebuie să verificăm dacă gardul poate deveni perfect prin eliminarea unei singure scânduri.
Pentru aceasta calculăm numărul de frecvențe diferite și verificăm următoarele condiții:
1. Dacă avem mai mult de două frecvențe diferite => imperfect
2. Dacă cel puțin una dintre cele două frecvențe diferite rămase are valoarea 1 și apare o singură dată => perfect
3. Dacă una dintre frecvențe apare o singură dată, iar valoarea ei este egală cu cealaltă frecventă + 1 => perfect
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
Răspunsuri la întrebare
Răspuns:
#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;
}
Explicație: