Lista de probleme 28

Un număr natural n se numește număr VIP dacă este format din cel puțin două cifre, conține cel puțin o cifră impară și cel puțin o cifră pară, iar toate cifrele impare sunt scrise înaintea tuturor celor pare. ( VIP = Valori Impare Pare). De exemplu, 352, 7546 sunt numere VIP, iar 35, 468, 5483, 387 nu sunt numere VIP. Se numește SECVENȚĂ VIP într-un șir de cifre, o succesiune de cifre (aflate pe poziții consecutive în șir) care formează, în ordine, un număr VIP.

Pentru un șir de cifre nenule, se cere să se determine:

1. Numărul de SECVENȚE VIP din șir.
2. Lungimea minimă a unui șir de cifre care conține același număr de SECVENȚE VIP ca șirul dat și are toate cifrele impare situate înaintea celor pare.
3. Suma tuturor numerelor ce se pot forma, astfel încât fiecare număr să conțină toate cifrele distincte ale celui mai mare număr VIP din șirul dat, fiecare cifră fiind folosită exact o dată, și nicio altă cifră diferită de acestea.

Se consideră următoarea structură de date. În vârful structurii se găsește fracția 1/1. Din fiecare vârf în care se găsește fracția p/q se formează alte două fracții trasând câte două segmente de dreaptă astfel: către stânga fracția p/(p+q) și către dreapta fracția (p+q)/q.
Cunoscând numărătorul, respectiv numitorul a două fracții ireductibile diferite din structură, determinați numărul minim de segmente de dreaptă cu care putem conecta în structura dată, cele două fracții.

În matematică factorialul unui număr natural nenul K este notat cu K! și este egal cu produsul numerelor naturale nenule mai mici sau egale cu K.
Orice număr natural N poate fi descompus cu ajutorul numerelor factoriale astfel:
N = 1! • f[1] + 2! • f[2] + 3! • f[3] + ... + m! • f[m]
unde coeficienții f[i], cu 1 ≤ i ≤ m sunt numere naturale și în plus f[m] ≠ 0.
Dintre toate aceste descompuneri posibile există o singură descompunere, numită descompunere în bază factorială care respectă suplimentar condițiile 0 ≤ f[i] ≤ i, cu 1 ≤ i < m și 0 < f[m] ≤ m.
1. Să se determine descompunerea în bază factorială a unui număr natural X dat.
2. Cunoscând o descompunere oarecare a unui număr natural Y să se determine descompunerea în bază factorială a acestuia.

Fie k, n și y trei numere naturale. Fie X un șir format din n numere naturale: \( x_1, x_2, x_3, …, x_n \). Fie P produsul numerelor \( y, x_1, x_2, x_3, …, x_n \), adică \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \). Numărul P este o “k-putere” dacă există un număr natural z astfel încât \( P=z^k \).

Scrieți un program care să citească numerele \( k, n, x_1, x_2, x_3, …, x_n \) și care să determine:

• 1. cel mai mic și cel mai mare număr din șirul X ce sunt formate doar din cifre identice;
• 2. descompunerea în factori primi a celui mai mic număr natural y (y ≥ 2) cu proprietatea că numărul \( P = y\times x_1\times x_2 \times x_3 \times … \times x_n \) este o “k-putere”.

Se consideră două șiruri D=(D1,D2,...,Dn) și E=(E1,E2,... ,En) ce reprezintă descompunerea în factori primi pentru un număr natural nenul X, după cum urmează: Di – factorul prim, Ei – puterea la care apare factorul prim Di în descompunerea numărului X (1≤i≤n), unde n reprezintă numărul factorilor primi.

Cerința

Să se determine:
1. numărul total de divizori naturali ai lui X
2. divizorii lui X care aparțin intervalului [A,B], unde A și B sunt două numere naturale date.

Primăria a montat, pe faleza din Mamaia, N proiectoare așezate liniar, pentru fiecare cunoscându-se zona de faleză pe care o luminează, sub forma unui interval [s, d], unde s și d (s < d) sunt numere naturale reprezentând distanțele față de punctul unde începe faleza. Pentru a verifica eficiența iluminării falezei, tehnicienii primăriei vor să determine intervalul de faleză de lungime maximă, iluminat de cel mult K proiectoare, conținut într-un interval [X, Y] precizat. Pentru a fi siguri de corectitudinea rezultatelor obținute, tehnicienii realizează Q astfel de verificări.
Dându-se Q intervale de forma [Xi, Yi] determinați, pentru fiecare dintre acestea, câte un interval de lungime maximă iluminat de cel mult K proiectoare. Dacă nici un proiector nu iluminează vreo porțiune din intervalul [Xi, Yi] se va afișa valoarea 0.

Determinaţi costul total minim al segmentelor care pot fi alese pentru a obtura orice fascicul de lumină care
ar pleca din origine către un punct cu ordonata pozitivă.

O mulțime cu elemente numere naturale poate fi scrisă într-o formă redusă dacă, ordonând crescător elementele ei, diferența dintre oricare două valori alăturate este aceeași. De exemplu, mulțimea D={11, 14, 17, 20, 23} poate fi scrisă sub forma D=11-23/3, precizând elementul minim, elementul maxim și diferența dintre elemente.
Date fiind N mulțimi scrise sub forma redusă, fiecare fiind notată cu o literă mare a alfabetului englez, se cere să se calculeze o expresie care poate conține:

• operația de reuniune, notată cu +;
• operația de intersecție, notată cu *;
• literele asociate mulțimilor;
• paranteze rotunde.

Considerăm că valoarea expresiei este mulțimea obținută după efectuarea operațiilor specifice mulțimilor considerând că operațiile de intersecție au prioritate mai mare decât cele de reuniune.
Cunoscând forma redusă a celor N mulțimi și o expresie, să se calculeze valoarea expresiei date.

Se dau două șiruri S1 si S2 formate doar cu litere mici. Numim subșir de lungime K al unui șir a un șir a' = ai1, ai2,…, aiK astfel încât să avem: i1 < i2 < ... < iK.
Să se determine lungimea maximă a unui subșir din S1, format prin concatenarea unor anagrame ale șirului S2. Dintre toate subșirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un șir de lungime na se consideră mai mic lexicografic decât un șir de lungime nb dacă există un indice i, astfel încât a1=b1, a2=b1, …, ai-1=bi-1 și ai<bi. Un șir a este anagrama unui șir b dacă sortându-le crescător pe fiecare se obțin două șiruri identice.

Prietenul nostru, Pit, se află în Grecia antică, în cea mai vestită piață publică. Considerăm că piața este un dreptunghi din plan, de dimensiuni X și Y. Dacă reprezentăm piața într-un reper cartezian xOy, aceasta are cele patru vârfuri în punctele de coordonate (0,0), (X,0), (X,Y) și (0,Y). În fiecare punct (a,b), cu a ∈ {1,...,X} și b ∈ {1,...,Y}, se află câte o tarabă care vinde echere. Prietenul nostru este afacerist și vrea să închirieze o parcelă de teren dreptunghiulară, având laturile paralele cu laturile pieței, iar cele patru vârfuri de coordonate numere naturale. Vârfurile parcelei se află în interiorul pieței sau pe laturile acesteia. În această parcelă, Pit vrea să cuprindă cât mai multe tarabe speciale, care au următoarele proprietăți:

• distanta de la origine la tarabă este număr natural;
• nu există nici o altă tarabă pe segmentul dintre origine și tarabă.

Cunoscându-se valorile X, Y și coordonatele (SXi, SYi) și (DXi, DYi) pentru Q parcele, unde 1 ≤ i ≤ Q, să se afle, pentru fiecare parcelă, care este numărul de tarabe speciale pe care le conține.