Lista de probleme 1390

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].

Avem o suprafață dreptunghiulară pătratică de dimensiune n x n (n – impar). Colțul de dimensiune 1 x 1 din stânga-sus lipsește. Se dorește pavarea a cât mai mult din suprafața sa cu dale de dimensiune 1 x 2 (sau 2 x 1). Trebuie folosite cât mai multe dale și în plus, numărul de dale orizontale folosite trebuie să fie egal cu numărul de dale verticale folosite pentru pavare.

Crina și Rareș pornesc în călătoria imaginară spre Deva și pentru aceasta fiecare își construiește câte un autocar din piese de lego. Pentru a nu crea blocaje în trafic, intrarea autocarelor în oraș este gestionată de un semnal pe care este scris un număr natural S. Astfel, fiecare autocar ce ajunge în dreptul semnalului, trebuie să aștepte, un număr de minute egal cu valoarea absolută a diferenței dintre S și numărul de identificare al autocarului său.

1. Determinați numerele N1 și N2 astfel încât, autocarul fiecărui copil să aștepte cât mai puține minute la semnal.
2. Știind că autocarele celor doi copii au ajuns în același timp în fața semnalului, determinați numărul minim de minute de așteptare ale autocarului care va trece primul de semnal.

Cristi, deja familiarizat cu noțiunea de densitate de la orele de fizică, își propune să o studieze și din perspectiva informaticii. Astfel, el alege un șir de N numere naturale A[1], A[2], …, A[N] și își dorește să experimenteze. Să se calculeze, câte secvențe nevide, au proprietatea că raportul dintre numărul elementelor pare din cadrul secvenței și lungimea secvenței este exact D.

Se consideră un șir A format din N numere întregi, numerotate de la 1 la N. Numim secvență a șirului A orice succesiune de elemente consecutive din șir de forma A[i], A[i+1], …, A[j], cu 0 < i < j ≤ N. Fiind dat șirul A cu N numere întregi se cere să se răspundă la Q întrebări de forma: i j k (0 < i < j ≤ N). Pentru fiecare întrebare se cere să se determine câte numere din secvența A[i], …, A[j] au frecvența de apariții egală cu k.

Pe un cerc sunt așezate echidistant N puncte, etichetate în sensul acelor de ceas cu 1, 2, 3, …, N.
Se dau M intervale de forma [a, b] și T interogări de forma P Q.

Pentru fiecare interogare [P, Q] să se verifice dacă este adevărat sau fals că intersecția tuturor intervalelor care au puncte comune cu [P, Q] include intervalul [P, Q].

Scrieți un program care citește un număr natural n și care să calculeze suma S a tuturor numerelor obținute prin permutări circulare la dreapta ale cifrelor lui n cu o poziție.

Fie un zid perfect dreptunghiular de înaltime H și lățime W, format din cărămizi de înalțime 1 și lățime variabilă, lipite între ele.

Să se taie acest zid pe verticală astfel încât numărul de cărămizi ce trebuie tăiate să fie minim. În cazul în care există mai multe astfel de locuri unde poate fi tăiat zidul, se dorește ca diferența lățimilor celor două bucăți obținute să fie cât mai mică.

Pentru reprezentarea numerelor s-a decis să nu se mai folosească cifra C. Astfel din șirul numerelor naturale se vor elimina toate numerele care conțin cifra C. Notăm noul șir cu S.

1) Să se determine al N-lea număr din șirul S.
2) Se dau Y și Z, două numere naturale din șirul S. Să se determine numărul de numere naturale eliminate dintre Y și Z.

O permutare de ordin K este formată din toate numerele 1, 2, …, K nu neapărat în această ordine.
O secvență de lungime L este formată din L elemente ale șirului aflate pe poziții consecutive. Spunem că o secvență de lungime L este permutare de ordin L dacă ea conține toate numerele 1, 2, …, L, nu neapărat în această ordine.

Se dă un șir de N numere naturale nenule \( {a}_{1}, {a}_{2}, …,{a}_{N} \), ce reprezintă o permutare de ordin N. Să se calculeze numărul secvențelor din șirul a care au proprietatea că sunt permutări.