Lista de probleme 160

Supărat că fata de care-i plăcea l-a respins, Bogdan și-a făcut bagajele și a pornit într-o excursie de-a lungul întregii lumi. Acesta a vizitat mai toate continentele, însă acum este blocat în Africa din cauza faptului că Bogdan, băiat mai neastâmpărat din fire, s-a apucat să se bată cu țânțarii Mosquito.Bineînțeles că a fost înțepat și că acum trebuie să caute antidot pentru venin, altfel Bogdan se va transforma și el în Mosquito. Acesta s-a dus să-i ceară ajutorul lui Aashiq, care îi spune următoarele: “Te voi vindeca de înțepături dacă reușești să duci la bun sfârșit sarcina pe care ți-o dau.”, însă Bogdan nu prea se pricepe la sarcini complicate, așa că vă roagă să rezolvați voi cerința în locul lui.

Dându-se trei numere naturale, a, n, k, trebuie să aflați valoarea următoarei expresii: ak•ak+2k•...•ak+2k+...+nk. Antidotul pentru înțepăturile de Mosquito necesită foarte multă muncă, motiv pentru care vor trebui îndeplinite t teste.

Cunoscând prietenul preferat și hobby-ul fiecărui copil, scrieți un program care determină numărul grupurilor care se vor forma și numărul grupurilor formate din copii care au hobby-uri identice; doi copii vor face parte din același grup, dacă cel puțin unul din cei doi l-a numit pe celălalt ca prieten.

Într-o cutie sunt n bomboane.
Dacă se împart cele n bomboane în mod egal la un grup de p copii, rămân p-1 bomboane.
Dacă se împart cele n bomboane în mod egal la un grup de q copii, rămân q-1 bomboane.
Se dau p și q, numere naturale. Aflați cel mai mic n, număr natural care satisface condițiile de mai sus.

Se dă șirul lui Fibonacci: \({f}_{1}=1\), \({f}_{2}=1\), \({f}_{3}=2\), \({f}_{4}=3\), \({f}_{5}=5\), …, definit astfel \({f}_{k+2}\) = \({f}_{k+1}\) + \({f}_{k}\), \(k>2\).

Se dau \(Q\) query-uri de forma \(a b\). Se cere să se afișeze pentru fiecare query \({f}_{a}\), \({f}_{b}\) și suma elementelor \({f}_{k}\) din șirul lui Fibonacci cu \(a≤k≤b\).

Dat fiind o matrice de dimensiunea n*m, să se găsească punctul unde trebuie începută vaccinarea pentru a maximiza suma vârstelor celor vaccinați.

Se dă un număr natural n. Se construiește o matrice pătratică de dimensiune 2n-1, după următoarele reguli:

• elementul din mijlocul matricii este egal cu n
• elementele de pe linia mediană și cele de pe coloana mediană (exceptând elementul din mijlocul matricii) sunt nule
• folosind linia mediană și coloana mediană, se împarte matricea în alte 4 matrici care se generează similar, dar au dimensiunea 2n-1-1.
  Calculați și afișați suma elementelor din matricea construită conform regulilor de mai sus.

Se dă un număr natural n. Să se afișeze DA dacă numărul este prim altfel se afișează NU.

1. Dimensiunea suprafeţei (în hectare) pe care ar ocupa-o după t ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
2. Timpul scurs până când toate cele N oraşe şi-au încetat extinderea, începută din cartierele iniţiale ale căror coordonate se citesc din fişier, şi aria suprafeţei din hartă rămasă neocupată, exprimată în hectare.

Fie un șir de numere naturale nenule a[1], a[2], …, a[n] și un număr natural k. Să se determine un grup de k numere din șir care au proprietatea că cel mai mare divizor comun al lor este maxim. Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă.

Sandu a studiat la ora de informatică mai multe aplicații cu vectori de numere naturale, iar acum are de rezolvat o problemă interesantă. Se dă un șir X=(X[1],X[2],…,X[n]) de numere naturale nenule și două numere naturale p1 și p2, unde p1<p2. Sandu trebuie să construiască un nou șir Y=(Y[1],Y[2],…,Y[n*n]) cu n*n elemente obținute din toate produsele de câte două elemente din șirul X (fiecare element din șirul Y este de forma X[i]*X[j], 1<=i, j<=n). Sandu are de calculat două valori naturale d1 și d2 obținute din șirul Y. Valoarea d1 este egală cu diferența maximă posibilă dintre două valori ale șirului Y. Pentru a obține valoarea d2, Sandu trebuie să considere că șirul Y are elementele ordonate descrescător iar d2 va fi diferența dintre valorile aflate pe pozițiile p1 și p2 în șirul ordonat descrescător. Sandu a găsit rapid valorile d1 și d2 și, pentru a le verifica, vă roagă să le determinați și voi.

Dându-se șirul X cu n elemente și valorile p1 și p2, determinați valorile d1 și d2.