Problema Avârcolaci – ONI 2014, Clasa a 11-a

Problema Avârcolaci – ONI 2014, Clasa a 11-a

Rezumat

Se dă un vector de lungime 2n2 \cdot n ce conține codurile unor vârcolaci. Dacă oricum am împărți vectorul în două grupe, fiecare de lungime nn un vârcolac codificat cu vv apare cel puțin câte o dată în fiecare grupă, atunci el este cu siguranță cel care bântuie satul. Pentru tt astfel de teste, trebuie să determinăm vârcolacul care bântuie fiecare sat. Dacă nu există un astfel de vârcolac, se afișează mesajul "Mozart".

Soluție

Enunțul e destul de ciudat, probabil pentru a ne îndepărta de la ideea că nu trebuie decât să aflăm elementul majoritar al fiecărui vector. Cuvântul Mozart ar trebui totuși să ne ajute; soluția problemei e la fel de clasică precum muzica lui Mozart :yey:

Folosim algoritmul optim pentru găsirea elementului majoritar, de complexitate O(n)O(n) pe care l-am prezentat și în articolul despre problema livada. Totuși, ceva nu e bine. Algoritmul presupune parcurgerea vectorului de două ori, iar pentru asta ar trebui să reținem cumva vectorul, deși n-avem destulă memorie. Șmecheria este să efectuăm prima parte a algoritmului, reținând doar candidatul corespunzător fiecărui test (într-un vector cand), iar apoi să redeschidem fișierul pentru a doua parcurgere a vectorilor, în care verificăm pentru fiecare dacă are într-adevăr un element majoritar, folosind valorile găsite mai înainte:

fin.close();
fin.open("NumeFisier");

Dar, chiar dacă era necesară ideea asta isteață, mi se pare o problemă prea simplă pentru o națională de clasele 11-12… Nici nu aveai nevoie de citire în C sau de parsare, pentru că cele șase secunde oferite sunt suficiente.

Sursă C++

Problema Avârcolaci
#include <fstream>
#define TMAX 20
std::ifstream fin("avarcolaci.in");
std::ofstream fout("avarcolaci.out");
int t, n;
int cand[TMAX];
int main() {
fin >> t;
for (int i = 0; i < t; i++) {
fin >> n;
int ap = 0;
cand[i] = -1;
for (int j = 0; j < 2 * n; j++) {
int x; fin >> x;
if (!ap) {
cand[i] = x;
ap = 1;
}
else if (x == cand[i])
ap++;
else
ap--;
}
}
fin.close();
fin.open("avarcolaci.in");
fin >> t;
for (int i = 0; i < t; i++) {
fin >> n;
ap = 0;
for (int j = 0; j < 2 * n; j++) {
fin >> x;
if (x == cand[i])
ap++;
}
if (ap > n)
fout << cand[i] << '\n';
else
fout << "Mozart\n";
}
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Avârcolaci, lasă un comentariu și te voi ajuta :smile:

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii