Lista de probleme 3

Se dă un șir A cu N elemente, numere naturale nenule, și un număr natural K. O subsecvență a șirului este un șir format din unul sau mai multe elemente aflate pe poziții consecutive în șirul inițial. Spunem că o valoare x se numește element majoritar al unei secvențe de lungime m, dacă ea apare în aceasta de cel puțin \( \left[ \frac{m}{2} \right] + 1\) ori. Să se afișeze valorile care sunt elemente majoritare pentru cel puțin o subsecvență de lungime mai mare sau egală cu K a șirului A.

Geologul George a descoperit recent în zona Iașiului o peșteră foarte frumoasă, ideală pentru studierea stalactitelor. În peșteră se află N stalactite, așezate în linie dreaptă. După săptămâni de muncă și analizare temeinică a peșterii, George a descoperit că fiecare stalactită este formată din straturi de depuneri cu diverse compoziții chimice. Astfel, dacă are o stalactită cu 4 straturi, cărora le-a asociat numerele prime 2, 11, 2, 3, atunci stalactita respectivă va avea valoarea 132 = 2 • 2 • 3 • 11. Aflați numărul maxim de stalactite care formează o subsecvență obținută prin curățare, care să fie pe gustul lui George.

Andra are un pachet cu n tipuri de buline de ciocolată, cu câte c[i] buline de fiecare tip i. Andra dorește să utilizeze toate bulinele pentru a construi piramide, fiecare fiind formată din unul sau mai multe rânduri, numerotate începând de la 1. Pentru fiecare piramidă în parte, pe rândul i, se află 2i-1 buline. Spre exemplu, pe rândul 8 al unei piramide, se află 27 = 128 de buline de ciocolată. Pe fiecare rând al unei piramide se află unul sau mai multe tipuri de buline, iar același tip de buline se poate folosi pe oricâte rânduri. Dintre piramidele care se pot forma, cele serioase conțin pe fiecare rând doar un tip de buline. Folosind toate bulinele, ajutați-o pe Andra să determine:

1) Numărul minim de piramide de ciocolată pe care le poate forma.
2) Numărul minim de piramide serioase de ciocolată pe care le poate forma, astfel încât toate cele obținute să fie de acest fel.