Lista de probleme 18

Se consideră şirul crescător 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, ..., în care fiecare număr natural nenul i apare de 2i-1 ori. Elementele unei matrice A cu M linii şi N coloane au valori astfel încât, parcurgând matricea de sus în jos, pe linii, și de la stânga la dreapta pe fiecare linie, se obțin primii M x N termeni ai șirului precizat. O submatrice a lui A este definită de patru valori, l1, c1, l2, c2 şi este formată din elementele Ai,j cu proprietatea că l1 ≤ i ≤ l2 și c1 ≤ j ≤ c2. Determinaţi suma elementelor pentru fiecare dintre Q submatrice date ale lui A.

Lordul John a decis că a venit vremea să însămânțeze terenul său. Terenul a fost împărțit în parcele organizate în N linii, pe fiecare linie fiind câte N parcele pătrate, fiecare cu suprafața de un metru pătrat. Liniile au fost numerotate de sus în jos de la 1 la N, iar coloanele de la stânga la dreapta de la 1 la N. Fiind un aviator pasionat, a folosit avionul său pentru a survola terenul în vederea însămânțării. La final, după însămânțare, Lordul John dorește să împrejmuiască cu gard parcelele însămânțate, pentru a le separa de cele rămase neînsămânțate sau de marginea terenului.
1. Determinați numărul semințelor care sunt aruncate.
2. Determinați numărul de parcele care sunt însămânțate.
3. Determinați lungimea gardului care trebuie să separe suprafețele însămânțate de cele neînsămânțate sau de marginea terenului.

Elevii celor două clase de a șaptea din școală merg în excursie. În fiecare clasă sunt câte N elevi. Ovidiu și Mihnea, fiind liderii celor două clase din care fac parte, doresc să analizeze reușita excursiei, în funcție de gradul de compatibilitate dintre elevii participanți la excursie. Pentru a determina acest grad, fiecărui elev din cele două clase îi este atribuit un coeficient de amabilitate.
1. Determinați gradul de compatibilitate dintre cele două clase.
2. Determinați, pentru fiecare elev din clasa lui Ovidiu, numărul de elevi din clasa lui Mihnea cu care acesta poate lega o prietenie durabilă.

O operaţie de reducere aplicată asupra unui șir constă în selectarea unui număr prim p şi a unor elemente din șirul dat care sunt divizibile cu p şi împărţirea acestora la p. Asupra unui șir format din n numere naturale nenule se aplică o succesiune de operaţii de reducere, până când toate elementele șirului devin egale. Valoarea finală a elementelor șirului este denumită valoare de egalitate. Valoarea de reducere a unui șir este cea mai mare dintre valorile de egalitate care se pot obţine în urma aplicării unor operaţii de reducere asupra acestui șir.
1) Determinați valoarea de reducere pentru un șir dat.
2) Determinați numărul minim de operaţii de reducere care trebuie să fie aplicate șirului dat pentru a obţine valoarea de reducere.

Se dă un număr natural N și apoi N numere naturale, toate având același număr de cifre.
1) Determinați câte dintre cele N numere sunt palindrom.
2) Determinați câte dintre cele N numere pot deveni palindrom prin inserarea în acestea a câte unei cifre.
3) Determinați câte dintre cele N numere pot deveni palindrom prin inserarea în acestea a câte două cifre.

Un dispozitiv de tip semafor are trei culori, roșu, galben și verde, și funcționează ciclic, astfel încât, în fiecare moment, să fie aprinsă o singură culoare. Într-o serie, culorile se succed întotdeauna în ordinea următoare: roșu, galben, verde, galben. Astfel, la pornire se aprinde roșu, iar după ce se stinge această culoare se aprinde galben, apoi verde și apoi, din nou, galben, apoi seria culorilor se reia ciclic, în succesiunea precizată.
1) Știind că în acest moment la niciunul dintre semafoare nu este aprins verde, determinați numărul minim de secunde care trebuie să treacă, din acest moment, până când se aprinde verde la cel puțin unul dintre ele.
2) Determinați numărul minim de secunde care trebuie să treacă, din acest moment, până când ambele semafoare au aprinsă aceeași culoare.

Áles se află într-un castel, reprezentat printr-o matrice A cu N linii și N coloane, fiecare element corespunzând unei camere. Fiecare cameră are asociat câte un număr natural de la 1 la K, care este memorat în elementul corespunzător din matrice. Oricare două camere cu același număr asociat sunt conectate printr-un tunel. De asemenea, fiecare cameră este conectată printr-o ușă cu o cameră vecină, elementele corespunzătoare acestora fiind în matrice pe acceași linie și pe coloane alăturate sau pe aceeași coloană și pe linii alăturate. Scopul lui Áles este să viziteze toate camerele, fiecare cel puțin o dată, astfel încât numerele asociate lor, în ordinea vizitării acestora, să formeze un şir crescător, începând de la 1.

Áles alege la început o cameră care are asociat numărul 1. Din fiecare cameră ce corespunde unui element \(A_{i,j}\) el poate vizita:

• folosind un tunel, orice cameră ce corespunde unui element \(i’,j’\) astfel încât \(A_{i’,j’} = A_{i,j}\).
• folosind o uşă, orice camera vecină cu un număr asociat consecutiv, deci care corespunde unui element \(i’,j’\) astfel încât \( |i’-i|+|j’-j|=1 \) și \(A_{i’,j’}=A_{i,j}+1\).
• folosind un teleportor, în orice cameră cu numărul asociat \(A_{i,j}+1\), la această metodă de deplasare putând să recurgă numai dacă nu poate ajunge la o astfel de cameră utilizând un tunel sau o uşă.

Ați înțeles, Áles doreşte să folosească teleportorul de cât mai puţine ori! El calculează mai întâi numărul minim necesar de teleportări pentru configurația inițială a camerelor, apoi face, pe rând, Q transformări succesive ale configurației, prin schimbarea numărului asociat pentru câte o cameră; după fiecare astfel de transformare, calculează din nou numărul minim necesar de teleportări pentru configurația respectivă.

Pentru configurația inițială, precum și după fiecare dintre cele Q transformări ale acesteia, în ordinea în care sunt realizate, determinați numărul minim de teleportări necesare pentru ca Áles să își îndeplinească scopul.

Avionul cu care am zburat ultima dată are o organizare foarte simplă. Pe fiecare rând sunt 6 scaune, câte 3 pe fiecare parte, având la mijloc culoarul pe care intră și ies pasagerii. Rândurile de scaune pentru pasageri sunt numerotate de la 1 la NR, începând dinspre cabina piloților avionului. Pe fiecare rând, scaunele sunt numerotate cu cifre de la 1 la 6. Urcarea în avion se face pe una dintre cele două scări: scara 1, situată în partea din față a avionului, și scara 2, situată în partea din spate a acestuia.
1) Determinați pentru fiecare dintre cei n pasageri, scara pe care trebuie să urce în avion, astfel încât distanța parcursă de el până la locul său să fie minimă.
2) Determinați distanța totală minimă parcursă de pasageri în avion. Distanța totală parcursă este egală cu suma distanțelor minime parcurse de cei n pasageri până la locuurile lor.

Prințul Mugurel trebuie să organizeze un nou spectacol pentru locuitorii din Imperiul Rațelor de Cauciuc. De data aceasta s-a gândit la ceva inedit: o cursă de natație pe Râul Macilor. Mugurel a adunat cele mai bune N raţe din imperiu, numerotate de la 1 la N, fiecare rață fiind caracterizată prin viteză şi nivel de rezistenţă. Pe Râul Macilor s-au amenajat M culoare de înot, numerotate de la 1 la M; pe fiecare culoar este câte o baliză, situată la o anumită distanță (în metri) față de linia de start, iar această distanță este strict mai mare decât distanța balizei de pe culoarul anterior. Mugurel alege M rațe dintre cele N, care sunt așezate adecvat la linia de start, fiecare pe câte un culoar de înot. Apoi, toate aceste rațe alese pornesc simultan, fiecare rață înoată pe culoarul ei, până la baliza corespunzătoare, și se întoarce înapoi la linia de start, pe același culoar. Durata cursei se măsoară de la pornirea simultană a rațelor, până la momentul când toate rațele ajung înapoi la linia de start. Determinați durata minimă pe care o poate avea cursa.

Se dă un șir a1, a2, …, an de numere naturale. Trebuie să răspundeți la două cerințe:
1) Să se verifice dacă șirul este ordonat crescător sau nu.
2) Să se verifice dacă prin eliminarea unui singur element, șirul rămas este ordonat crescător sau nu.