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++
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!