Lista de probleme 745

A venit ora mesei pentru Por Costel (masa dintre prânz și cină). Scormonind printr-o grădină, el descoperă un număr de N coceni de porumb și M mere. Masa lui Por Costel va consta în exact un cocean și un măr. Însă, mai nou, fanii săi l-au atenționat că trebuie să aibă grijă ce mănâncă. Fiecare cocean și fiecare măr are o valoare nutritivă. Valoarea nutritivă a mesei va fi valoarea nutritivă a coceanului ales + valoarea nutritiva a mărului ales. Dându-se valorile nutritive ale cocenilor și ale merelor, Por Costel vă întreabă dacă există o masă pe care o poate lua cu valoare nutritivă X. Pentru că Por Costel vrea sa mănânce de mai multe ori între prânz și cină, el va vă pune T întrebări de forma aceasta.
(Întrebările sunt independente între ele, a nu se considera că după o întrebare se elimină perechea cocean-mar aleasă).

Se citește un număr N, un număr K și apoi un șir cu N numere naturale. Determinați câte secvențe de lungime exact K au elementele distincte. Prin secvență înțelegem un set de elemente aflate pe poziții consecutive.

Se dă un șir ordonat crescător a1, a2, …, an de numere întregi. Asupra șirului putem efectua trei tipuri de interogări:

• 1 x – Câte numere din șir sunt mai mici sau egale decât x?
• 2 x – Câte numere din șir sunt mai strict mai mari decât x?
• 3 x – De câte ori apare în șir valoarea x?

Să se răspundă la Q interogări.

Victor și tatăl său au mers la magazinul de bomboane pentru ca tatăl să își onoreze o mai veche promisiune. Magazinul are bomboanele aranjate pe un rând, în mai multe cutii așezate una lângă alta. Se cunoaște numărul de bomboane din fiecare cutie, în ordinea în care sunt așezate cutiile începând de la intrare.
Tatăl i-a fixat lui Victor următoarea regulă de colectare a bomboanelor:

• Parcurge cutiile începând de la intrare.
• Colectează toate bomboanele din prima cutie.
• Când ajunge la o cutie de pe rând, colectează toate bomboanele de acolo doar dacă numărul lor este strict mai mare decât numărul de bomboane din ultima cutie din care a colectat.

Determinați câte bomboane a colectat Victor.

Se dau numerele naturale n, k și șirul de numere naturale a1, a2, …, an. O secvență din șir este bună dacă are cel puțin k numere distincte. Să se determine câte secvențe din șir sunt bune.

Se dau două șiruri de numere întregi a = a[1], a[2], ..., a[n] și b = b[1], b[2], ..., b[m], unde m < n. Spunem că o secvență a[i..i+m-1] = a[i], a[i+1], ..., a[i+m-1] se potrivește cu b dacă b conține, într-o ordine oarecare, toate numerele din secvența a[i..i+m-1]. De exemplu, dacă a = 3,5,1,2,2,5,3,8,1,2,3,5,2,1,1 și b = 2,2,1,5,3, atunci secvențele 3,5,1,2,2, 1,2,2,5,3, 1,2,3,5,2 și 2,3,5,2,1 se potrivesc cu b, pe când secvența 3,5,2,1,1 nu se potrivește cu b. Să se determine câte secvențe din a de lungime m se potrivesc cu b.

Se dă un șir a1, a2, …, an de numere naturale nenule. Se dă de asemenea un număr natural K. Se calculează sumele tuturor secvențelor nevide din șir și se ordonează crescător. Să se determine a K-a sumă din șirul ordonat crescător.

Se dă un șir a1, a2, …, an de numere întregi. În acest șir, o secvență de cel puțin două elemente ai, ai+1, …, aj este SCCI (secvență cu capetele identice) dacă ai = aj. Să se determine câte secvențe SCCI sunt în șir.

Doru s-a mutat în New York și își caută o nouă locuință specială în perimetrul străzilor numerotate cu numerele distincte de la 1 la n. Fiind pasionat de matematică, el vrea să se mute pe strada în care cel mai mare divizor comun (cmmdc) al înălțimilor clădirilor este maxim. De asemenea, clădirea aleasă trebuie să aibă cea mai mare înălțime număr prim de pe strada pe care se află. Doru vă roagă pe voi să găsiți clădirea perfectă.