Lista de probleme 9

Pe o masă, sunt așezate unul lângă altul, N cuburi numerotate în ordine cu valori de la 1 la N, care au dimensiunea laturii exprimată în centimetri, printr-un număr natural nenul. Un robot inteligent este programat să construiască turnuri prin aşezarea cuburilor unul peste altul. Ştiind că un turn poate fi format din cel puţin un cub, scrieţi un program care să determine:
1. cel mai mare număr de cuburi alăturate care au laturile exprimate printr-un număr par de centimetri;
2. înălţimea (exprimată în centimetri) celui mai înalt turn construit de robot.

În orașul Piticot locuiesc N pitici, fiecare într-o casă pe o stradă cu sens unic. Casele sunt așezate de-a lungul străzii, în sensul în care se circulă începând cu casa numerotată cu 1 până la casa numerotată cu N. În orașul Piticot piticii nu au un nume obișnuit! Ei poartă ca nume numărul casei în care stau. Neobișnuite sunt și casele lor! Dacă suni la soneria oricărei case depui atâta efort încât slăbești pe loc un număr de pitic-kilograme.
Pentru că au constatat că în timpul pandemiei s-au îngrășat, fiecare și-a propus să slăbească un număr de pitic-kilograme, într-o singură zi. Scrieți un program care determină care este numărul maxim de pitici care au sunat la o casă și la câte case s-a sunat de acest număr maxim de ori.

Se consideră un tablou cu N linii și N coloane ce conține numerele naturale de la 1 la N2 așezate consecutiv, întâi pe linii și apoi pe coloane, începând cu 1 în colțul din stânga sus. Să se scrie un program care citește:

• un numărul natural N, ce reprezintă numărul de linii și de coloane al unui tablou ce conține numerele naturale
  de la 1 la N2;
• două numere naturale X și Y, ce reprezintă coordonatele colțului de unde se face derularea:
  {(1,1) – stânga sus; (1,N) – dreapta sus; (N,N) – dreapta jos; (N,1) – stânga jos; }
• un caracter D (ma
  jusculă), ce reprezintă direcția pe care se face tragerea (O – orizontală și V – verticală).

și afișează șirul de numere ce rezultă din desfășurarea tabloului, începând cu colțul de unde se face tragerea și pe
direcția de tragere.

Profesorul începe ora scriind pe tablă următorul şir de numere: 1 1 1 2 1 1 2 3 1 3 1 2 3 4 1 3 1 2 3 4 5 1 3 5 1 2 3 4 5 6 1 3 5 … Copiii îl întrerup şi anunţă că au găsit regula după care sunt construiţi succesiv termenii şirului, şi anume: se scrie 1 urmat de 1, apoi 1 2 urmate tot de 1, apoi 1 2 3 urmate de 1 şi 3, apoi 1 2 3 4 urmate tot de 1 şi 3 … tot aşa, la un moment dat după secvenţa 1, 2, …, k se scriu numerele impare de la 1 la k. Evident că acesta este un şir infinit. Dându-se o poziţie din şir se cere determinarea valorii care se află pe acea poziţie. Dându-se o valoare, să se determine cea mai mică poziţie din şir pe care aceasta se află.

Se dau n și t două numere naturale nenule și S un șir binar de n elemente indexate de la 1. O interschimbare în acest șir constă în alegerea a doi indici i, j (1 ≤ i, j ≤ n) și schimbarea între ele a valorilor S[i] și S[j]. O subsecvență de lungime t a șirului S reprezintă t elemente aflate pe poziții consecutive în șirul S. Să se determine numărul minim de interschimbări ce trebuie realizate în șirul S pentru a obține două subsecvențe disjuncte de lungime t formate doar din elemente egale cu 1.

Ioana și Maria tocmai au învățat la matematică despre multiplii unui număr natural. Pentru a exersa lucrul cu noua noțiune, își propun să joace următorul joc: fiecare își alege câte un număr natural nenul și pentru câte un interval închis dat (la intervalele închise capetele fac parte din interval), calculează câți multipli are numărul ales în acel interval. Câștigă cea care a ales numărul care are mai mulți multipli în intervalul primit, sau este egalitate în cazul în care numărul multiplilor este acelaşi. Cunoscând numerele alese de cele două fete precum și numerele care determină intervalele date, să se determine cine câștigă jocul și care este numărul care conduce la câștigarea jocului.

Fie N un număr natural. Se consideră toate tripletele de forma (a, b, c), cu 1 ≤ a, b, c ≤ N, a≠b≠c≠a, cu proprietatea că c este cel mai mare divizor comun al numerelor a și b (c = cmmdc(a, b)). Dându-se N, determinați valoarea expresiei: a1•b1•c1 + a2•b2•c2 + ... + ak•bk•ck
unde (a1,b1,c1), (a2,b2,c2), …, (ak,bk,ck) sunt toate tripletele care îndeplinesc condițiile de mai sus. Întrucât rezultatul poate fi foarte mare, afișați resul împărțirii valorii expresiei la numărul 1.000.000.007.

Se dă un șir V de N numere naturale distincte. O secvență [X, Y] este formată din toate pozițiile consecutive dintre X și Y din șir. Se definește costul unei poziții P ca fiind valoarea din șir de pe poziția P înmulțită cu lungimea maximă a unei secvențe care conține poziția P și a cărei valoare maximă se află tot pe poziția P. Se dau M întrebări de forma: X Y – să se calculeze suma tuturor costurilor pozițiilor din secvența [X, Y].

Se dă un șir de numere hexazecimale, adică numere în care cele 16 cifre sunt din mulțimea {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. Spunem că două numere se potrivesc dacă nu au cifre hexazecimale comune și împreună conțin toate cifrele în baza 16, cel puțin o dată. Să se determine numărul perechilor de numere hexazecimale care se potrivesc.