Lista de probleme 7

Se dau N numere naturale s[1], s[2], …, s[N] și Q interogări de forma a b. Să se determine pentru fiecare interogare [a;b] numărul de subșiruri formate din elemente distincte ale secvenței s[a], s[a+1], s[a+2], …, s[b].

Definim mulțimea punctelor laticiale ca fiind mulțimea perechilor de puncte din plan (x,y) cu proprietatea că x și y sunt numere întregi. Fie R un număr natural pozitiv și C(O, R) cercul cu centrul în originea sistemului de axe, de rază R. Notăm cu P1, P2, P3, …, Pk punctele laticiale care se găsesc pe cercul C(O,R), în ordine inversă a acelor de ceasornic, începând cu punctul de coordonate (R,0). Să se scrie un program care determină numărul punctelor laticiale N cu proprietățile:

• se găsesc în interiorul sau pe cercul C(O, R);
• nu se găsesc în interiorul sau pe laturile poligonului P1 P2 P3… Pk.

Proprietatea trebuie împărțită fraților în mod egal. Zona are forma unui poligon convex cu vârfurile numerotate începând cu 1. Hotarul trebuie să fie un segment care are unul dintre capete în vârful 1 al poligonului. Trebuie să determinați celălalt capăt al segmentului care stabilește hotarul, așa încât ariile celor două suprafețe formate să fie egale. Punctul determinat trebuie să se afle pe poligon.

În Săptămâna Altfel – Să știi mai multe, să fi mai bun, elevii A și B se joacă un joc altfel, joc numit margi. Cei doi au la dispoziție o matrice pătratică binară de dimensiune 2n.
Scopul jocului este obținerea sumei maxim posibile prin adunarea punctajelor celor doi jucători. Dacă există mai multe posibilități de obținere a acestei sume, fiecare jucător va alege matricele cu număr de ordine mai mic.
Pentru un n număr natural dat și o matrice binară de dimensiunea 2n, se cere să se determine punctajul maxim obținut de cei doi jucători. Se cere și determinarea unei strategii de alegere a matricelor la fiecare pas care să ducă la obținerea punctajului maxim.

La grupa de excelență la care profesorul Genius predă sunt înscriși N elevi (reprezentați prin numere distincte de la 1 la N) care sunt sau nu prieteni. Pentru a face rezolvatul de probleme mai interesant, profesorul a inventat un joc: acesta alege elevul cu indicele K și îi spune enunțul unei probleme la care să se gândească și pe care să o spună mai departe tuturor prietenilor săi. Fiecare elev care află problema o va transmite în ziua următoare prietenilor săi care nu au aflat-o încă și tot așa, până când problema nu mai poate fi transmisă mai departe. Jocul e însă mai complex de atât: în ziua în care un elev află problema nivelul său de aprofundare a problemei este 0, în următoare zi nivelul de aprofundare este 1 și așa mai departe. În ziua X după aflarea problemei, un elev va ajunge la gradul X de aprofundare al acesteia. Profesorul Genius i-a anunțat pe elevi că aceștia se vor întâlni pentru a rezolva problema doar după ce toată lumea a aflat problema și toți elevii au ajuns la un nivel de aprofundare al problemei cel puțin P.
Știind modul în care funcționează jocul, profesorul Genius vrea să calculeze după câte zile de la lansarea problemei se va întâlni cu elevii săi pentru a o rezolva.

Cel mai lung tunel al autostrăzii Moldovei (?!) are lungimea L (exprimată în metri) și are un singur sens de deplasare. Autovehiculele care tranzitează tunelul se deplasează cu viteză constantă. Tunelul este monitorizat video permanent. Dacă sunt sesizate incidente, atunci conform protocolului situațiilor de urgență, se produc următoarele evenimente:

• este oprită intrarea în tunel;
• autovehiculele aflate în tunel sunt localizate prin detectarea poziției x față de intrarea în tunel precum și a vitezei de deplasare v;
• se interzice depășirea unui alt autovehicul.

Din păcate, pe perioada protocolului, în tunel se formează grupuri (stauband) de autovehicule, viteza de deplasare a grupului de mașini fiind adaptată la viteza primei mașini din grup, locația de referință (poziția) autovehiculului care se adaugă unui stauband va deveni locația primului autovehicul din stauband. Se presupune că atât autovehiculele cât și staubandurile formate au reprezentări punctiforme.
1) numărul de staubanduri formate până la părăsirea tunelului de către toate autovehiculele în cazul activării protocolului;
2) numărul maxim de autovehicule aflate într-un grup (stauband).

Se dau N bețe de bambus având lungimile L[1], L[2], …, L[N]. Conform unei tradiții străvechi, două bețe sunt în armonie dacă au aceeași lungime. Întrucât cele N lungimi pot diferi, nu este evident cum se pot face perechi de bețe armonioase. Astfel, se pot alege două bețe și în cazul în care unul dintre ele este mai lung, acesta va fi tăiat la o lungime corespunzătoare cu a celuilalt, pentru a armoniza cu perechea sa. Surplusul este adăugat la grupul de bețe deja existente, iar perechea este lăsată separat, să armonizeze îndelung pentru a aduce noroc și prosperitate. Procedeul de mai sus este repetat succesiv până când, fie toate bețele sunt epuizate, fie se va obține un singur băț. Dându-se Q seturi de bețe, să se determine pentru fiecare set, care este cea mai mică lungime posibilă a bățului final, nearmonizat.