Lista de probleme 1991

Fie \( X = \overline{X_1 X_2 X_3…X_N} \) un număr natural din N cifre.

Definim secvență în numărul X orice număr format dintr-un grup de cifre situate pe poziții consecutive în X. De exemplu, pentru X=12543644 pot fi secvențe numerele: 5436, 12, 1, 364, 12543644, etc.

Definim secvență-maxim în șirul \(X\) o secvență \( \overline{X_K X_{K+1}…X_P…X_T} \) în care există o singură cifră \( X_P \) astfel încât \( X_K < X_{K+1} <…< X_P > X_{P+1} >…> X_T \) ( \(1≤K<P<T≤N\) și \(K,P,T\) sunt numere naturale). De exemplu, pentru X=12543644 secvențele-maxim sunt: 1254, 12543, 254, 2543, 364.

Scrieți un program care citește numărul N, cele N cifre ale numărului X și care determină numărul total de secvenţe-maxim din numărul X.

O persoana are de urcat n trepte. Aflaţi in câte moduri poate urca cele n trepte.

Dandu-se un sir, sa se afle cate din primele n numere sunt divizibile cu 3.

Să se scrie un program care pentru un şir cunoscut determină pentru câte subsecvenţe ale şirului suma elementelor care le alcătuiesc are un anumit rest dat la împărţirea cu 3.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

De Ziua Îndrăgostiţilor Vali a hotărât să organizeze o petrecere mare pe stadionul oraşului. La petrecere pot participa numai şi numai îndrăgostiţi care şi-au procurat biletele din timp. Biletele oricărui cuplu sunt aproape identice. Ele au proprietatea că numărul de serie are prima cifră 1 pentru băieţi şi *prima cifră 2 pentru fete, continuarea celor două numere este identică. De exemplu, dacă prietenul are biletul cu numărul 134, atunci prietena lui are biletul 234, iar dacă prietena are biletul 2234567890, atunci prietenul ei are biletul 1234567890.
Bineînțeles, că și Vali are bilet și speră să câștige un cadou. Biletul lui Vali are aceeași proprietate ca celelalte bilete, cu o singură excepție: Vali nu va participa cu pereche la acest eveniment.

Pe parcursul desfășurării petrecerii, biletele de intrare vor avea şi rolul de bilet de tombolă. Acestea vor fi introduse într-o urnă şi câteva dintre ele vor fi extrase, iar norocoşii proprietari ai biletelor vor primi cadouri valoroase. Se mai știe că există probabilitatea ca unii participanți să vină la petrecere cu bilete falsificate, având numere identice cu cele de pe un bilet original. Acest fapt se va depista cu ușurință în momentul extragerii.

Cunoscând numerele de serie ale tuturor biletelor de intrare la acest eveniment, aflaţi:
a) dacă pe Vali o cheamă Valentina sau îl cheamă Valentin;
b) numărul biletului lui Vali.

Fiind dat un şir de numere, denumim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem:

• platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;
• platourile 7 7 (cel care începe în poziţia a patra) şi 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
• platoul 3 care are lungimea 1.

În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziţii consecutive!

Se dă un şir de n numere. Fiecare dintre aceste numere aparţine intervalului [0,1000000]. Asupra acestui şir se pot efectua o singură dată următoarele două operaţiuni în această ordine:

1. se extrage un platou la alegere;
2. se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.

De exemplu, dacă avem următorul şir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În şirul rezultat inserăm platoul 2 2 (pe care l-am extras în pasul anterior) în poziţia a doua şi obţinem şirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

Să se scrie un program care pentru un şir dat determină:

1. Lungimea maximă a unui platou din şirul dat iniţial precum şi valoarea cea mai mare a elementelor care formează un platou de lungime maximă.
2. Lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni precum şi valoarea cea mai mare a elementelor care ar putea forma un astfel de platou.

După o amorţeală care durase mai bine de 3 luni, Mama Natură îşi dădu seama că primăvara stătea să vină şi florile cu care trebuia curând să umple câmpiile nu erau încă pregătite. Înainte de începerea iernii, a lucrat să combine nuanţe din care să creeze flori pline de culoare, iar acum are camera plină de discuri de diferite culori, care aşteaptă să fie asamblate în flori viu colorate, fie pe post de mijloc, fie ca şi petale.

Pentru a forma o floare, Mama Natură alege un mijloc de orice culoare şi cel puţin K petale. Totodată, ea nu îşi doreşte să strice ordinea firească a lucrurilor şi de aceea nu va folosi niciodată două culori diferite de petale pentru aceeaşi floare. Ea admite, în schimb, flori cu petalele și mijlocul de aceeași culoare.

Deoarece timpul e scurt şi Mama Natură are lucruri mai importante de făcut decât să stea să asambleze flori, ea îşi cheamă în ajutor toate prietenele şi doreşte să îi dea fiecăreia ceva de lucru. Pentru aceasta, ea are la dispoziţie un şir D de N numere, unde numărul de pe poziţia i din șir reprezintă câte discuri de culoarea i a pregătit. Apoi, Mama Natură îşi pune M întrebări de forma x y, prin care doreşte să afle care este numărul maxim de flori care se pot forma folosind doar discuri de culori din intervalul [x, y] din şirul D.

Se dă un șir P de lungime N cu elemente distincte din mulțimea {1,2..,N}. Pentru fiecare poziție i din șirul P se cere să aflați cea mai mică poziție j, astfel încât P[j] < P[i] și j < i. În caz că o astfel de poziție nu există se consideră -1 ca soluție.

Se dau două numere naturale w şi h reprezentând lungimile laturilor dreptunghiului ABCD, un număr natural n şi n numere naturale x1, x2,… xn cu propietatea din enunt. Punctul P se plasează, pe rând, în toate punctele interioare dreptunghiului ABCD care sunt colţuri ale unor pătrate de latură 1. Pentru fiecare valoare x[i] (1 ≤ i ≤ n), determinaţi numărul de segmente distincte care trec prin exact x[i] pătrate
2-intersectate.

Se citesc de la tastatură n numere naturale. Să se determine numarul de numere prime formate din ultimele 2 cifre ale fiecarui număr.