Enunțul problemei avarcolaci, de clasa a 11-a, dată în 2014 la ONI, se găsește pe InfoArena și PbInfo.
Rezumat
Se dă un vector de lungime $2 \cdot n$, ce conține codurile unor vârcolaci. Dacă oricum am împărți vectorul în două grupe, fiecare de lungime $n$, un vârcolac codificat cu $v$ apare cel puțin câte o dată în fiecare grupă, atunci el este cu siguranță cel care bântuie satul. Pentru $t$ 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 (care știu că e scris greșit) ar trebui totuși să ne ajute; soluția problemei e la fel de clasică precum muzica lui Mozzart 😀
Folosim algoritmul optim pentru găsirea elementului majoritar, de complexitate $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:
|
1 2 |
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <fstream> #define TMAX 20 std::ifstream fin("avarcolaci.in"); std::ofstream fout("avarcolaci.out"); int t, n; int cand[TMAX]; int main() { int x; int ap; fin >> t; for (int i = 0; i < t; i++) { fin >> n; ap = 0; cand[i] = -1; for (int j = 0; j < 2 * n; j++) { 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"; } fout.close(); return 0; } |
Dacă ai vreo nedumerire cu privire la problema avarcolaci, lasă un comentariu și te voi ajuta 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!