Lista de probleme 3

Avem un șir V format din n cifre nenule precum și două numere naturale L și K. Putem efectua următoarea operație: alegem L elemente aflate unul lângă altul în șir apoi selectăm K dintre ele pe care le eliminăm. Cele L - K cifre se așează una lângă alta formând un număr a cărui valoare ne interesează (cifrele nu își pot schimba ordinea relativă, adică se așează în ordinea crescătoare a indicilor lor în șirul inițial). Trebuie să determinăm valoarea cu număr maxim de apariții pe care o obținem cu acest procedeu. Dacă sunt mai multe valori care apar de număr maxim de ori o vom alege pe cea mai mică. Două posibilități se consideră distincte dacă diferă prin indicele în șirul dat inițial al cel puțin uneia dintre cifrele de același rang în numerele asociate.

Se citește un număr n și apoi n numere naturale. Numim secvență un grup de elemente aflate pe poziții consecutive în șirul citit. Numim tri-secvență o secvență care începe cu un element impar, se termină cu un element impar și care mai conține în interior exact un element impar. Astfel, fiecare tri-secvență include două secvențe maximale formate doar din elemente pare (eventual, fiecare dintre cele două poate fi vidă). Dezechilibrul unei tri-secvențe se calculează astfel: determinăm suma elementelor din secvența din stânga formată doar din elemente pare, suma elementelor din secvența din dreapta formată doar din elemente pare și apoi diferența în modul a celor două valori (adică scădem din cea mare pe cea mică). Dacă vreuna dintre cele două secvențe de elemente pare este vidă, aceasta se consideră de sumă 0. Această diferență reprezintă dezechilibrul tri-secvenței. Să se determine o tri-secvența de dezechilibru minim. Dacă sunt mai multe astfel de tri-secvențe, să se determine cea care începe la o poziție cât mai mare.

Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1). Se dă un șir cu n elemente numere naturale. Să se sorteze elementele din șir în ordine crescătoare a forței, iar acele elemente care au aceeași forță să apară în ordine inversă decât apăreau inițial în șir.