Lista de probleme 17

Filtrare

#2239 pow2

Se consideră un șir a[1], a[2],…, a[n] de numere naturale nenule. Să se determine câte perechi de indici (i, j), 1 ≤ i < j ≤ n, există cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Se dă un șir a1, a2, …, an de numere întregi și un număr întreg S. Să se determine numărul secvențelor nevide care au suma egală cu S.

#2048 mixperm

Se consideră două șiruri de numere naturale, ambele de lungime n, a=(a[1],a[2],...,a[n]) și b=(b[1],b[2],...,b[n]). Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea {1,2,…,n}. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici i și j, cu 1≤i≤j≤n, apoi prin interschimbarea secvențelor a[i],a[i+1],...,a[j] cu b[i],b[i+1],...,b[j] se obțin șirurile:

  • a[1], a[2], ...,a[i-1], b[i],b[i+1],…, b[j], a[j+1],a[j+2], …, a[n] și
  • b[1], b[2], ...,b[i-1], a[i], a[i+1],…, a[j], b[j+1],b[j+2], …, b[n].

Dacă măcar unul din șirurile obținute este permutare a mulțimii {1,2,…,n}, atunci spunem că s-a obținut un mixperm.

Să se determine în câte moduri se poate obține un mixperm.

#2974 Zzid

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

#3397 gard2

Mihăiță s-a hotărât să își construiască un gard perfect cu ajutorul lui Dorel – un constructor renumit.
Un gard perfect trebuie să respecte următoarele cerințe:
1. Gardul să fie format din N scânduri de înălțimi nu neapărat egale;
2. Scândurile pot fi așezate în orice ordine;
3. Există un număr egal de scânduri pentru fiecare înălțime;
Mihăiță acceptă un gard ca fiind perfect dacă respectă condițiile de mai sus înainte sau după eliminarea unei singure scânduri. Ajutați-l pe Mihăiță să verifice perfecțiunea celor T garduri propuse de Dorel.

#3941 CountSumS C++

Scrieți funcția care are antetul:

long long CountSumS(vector<int> &a, int s)

Funcția va returna numărul de perechi (a[i], a[j]) cu i < j și a[i] + a[j] = s.

Folclorul informatic

#4205 SecvSumS C++

Scrieți funcția care are antetul:

int SecvSumS(vector<int> &a, int s)

Funcția va returna lungimea minimă a unei secvențe nevide din a care are suma egală cu s. Dacă nu există nicio secvență de sumă s funcția va returna valoarea -1.

#4246 banana

Se consideră o pădure tropicală, reprezentată sub forma unui caroiaj dreptunghiular. Celula din colţul stânga sus al caroiajului are coordonatele (1, 1), iar coordonatele celorlalte celule sunt determinate de linia şi coloana pe care se află. În anumite celule ale caroiajului sunt plasaţi bananieri; o celulă conţine cel mult un bananier. Mai mulţi bananieri care se învecinează pe orizontală sau verticală formează o zonă de bananieri. Într-o astfel de zonă, CEKILI se deplasează uşor, cu agilitatea-i cunoscută, de la un bananier la altul. Determinaţi numărul maxim de bananieri care se poate obţine prin conectarea a exact K zone.

#3776 sp

Se dă un șir S format din litere mici ale alfabetului englez. O secvență din şir este palindromică dacă prin parcurgerea sa de la dreapta la stânga se obține același cuvânt precum la parcurgerea de la stânga la dreapta. Se formulează m întrebări de forma i, j, k cu semnificația: pornind de la secvența formată din caracterele dintre indicii i și j inclusiv și având posibilitatea să o extindem în total cu maximum k caractere în S (imediat în stânga poziției i și/sau imediat în dreapta poziției j), putem să obținem o secvență palindromică?

Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i. Să se determine numărul perechilor de puncte simetrice.