Lista de probleme 9

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.

Fie o matrice A de dimensiuni 2N x 2N date. Aceasta se construiește astfel:
Se pornește de la o matrice de dimensiune 2 x 2 având ca elemente litere mici ale alfabetului englez. Matricea B de dimensiune 2k x 2k se formează din patru submatrice de dimensiune 2k-1 x 2k-1 și se obține din matricea C de dimensiune 2k-1 x 2k-1. Se dau Q triplete (i, j, L), cu semnificația: pe poziția A[i][j] se află litera L. Care este numărul maxim de triplete care se pot selecta astfel încât toate să fie adevărate?

Se consideră un șir de N numere naturale. Numim rectangle-sequence orice secvență continuă din șir (formată din elemente situate pe poziții consecutive) care conține cel puțin două elemente. Fiecare rectangle-sequence este caracterizată de un dreptunghi cu lungimile laturilor egale cu cele mai mari două elemente din cadrul ei. Să se calculeze restul împărțirii sumei ariilor dreptunghiurilor ce caracterizează toate rectangle-sequences din șir la numărul 1.000.000.007.

Pe axa numerelor reale, considerăm o autostradă cu un număr nelimitat de benzi. În dreptul bornei corespunzătoare kilometrului 0 (originea axei numerelor reale) se află un radar. Acest radar depistează N mașini care circulă cu viteze constante. Pentru fiecare mașină i se cunosc ti, momentul de timp la care este detectată de radar, exprimat în ore, și vi, viteza acesteia, exprimată în km/h. Să se răspundă la Q interogări de forma: dându-se t, care este la momentul t cea mai apropiată mașină de radar dintre cele detectate până atunci (inclusiv cele detectate fix la momentul t)? Dacă există mai multe mașini dintre cele detectate până la momentul t pentru care distanța față de radar este minimă, puteți afișa oricare dintre ele.

Fie N și K două numere naturale. Toate punctele din plan de coordonate întregi (x,y) cu proprietatea 0 ≤ x ≤ N, 0 ≤ y ≤ N se unesc prin linii orizontale și verticale de lungime 1. Apoi K linii de lungime 1 dintre cele de mai sus se șterg. Definim o cale ca fiind o succesiune continuă de linii orizontale sau verticale de lungime 1, între originea sistemului de axe și punctul de coordonate (N, N), cu lungimea totală 2∙N. Să se determine numărul total de căi distincte.

În Hogwarts există o tablă de șah cu N linii și M coloane. Harry Potter a găsit plasate, de către Hagrid, T ture care apără fiecare linia și coloana pe care este așezată. El trebuie să plaseze în siguranță K pioni pe tablă, adică fără ca vreunul dintre ei să fie atacat de vreo tură. Tabla de șah din Hogwarts este specială deoarece în cadrul unei celule pot fi plasați chiar și mai mulți pioni simultan! Cunoscând toate aceste reguli, ajutați-l pe Harry Potter să determine în câte modalități poate plasa în siguranță toți cei K pioni pe tabla de șah.

Se dă un șir de n litere mici, în care litera a are asociată valoarea 1, litera b valoarea 2, …, litera z valoarea 26. Se pot efectua oricâte operații de genul: modifică o literă c1 în litera c2 cu un cost c1+c2. Să se determine costul total minim al unor operații astfel încât șirul să devină crescător.