Lista de probleme 6

Pasionat de informatică și de puzzle-uri, Dorel a construit o matrice A de dimensiunea N × M lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea 1 × 1 și rețin o aceeași valoare. Matricea rezultată nu are spații libere, iar piesele din care este compusă nu se suprapun. Nu există două piese cu aceeași valoare.
Deși inițial părea că acest design este unul inedit, nu a durat mult până când Dorel s-a plictisit. Astfel, acum el dorește să “upgradeze” matricea construită. Dorel alege o submatrice delimitată de coordonatele (x1,y1) – colțul stânga-sus, (x2,y2) – colțul dreapta-jos (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M), unde crește toate valorile elementelor submatricei cu valoarea V.
Dorel efectuează în ordine Q operații de upgrade, operații numerotate de la 1 la Q. La finalizarea celor Q operații de upgrade, toate elementele din matrice au valoarea mai mare sau egală cu K. După o operație de upgrade, structura inițială a matricei se modifică.
Cum priceperea lui Dorel este proverbială, trebuie să îl ajutați în rezolvarea următoarelor cerințe:
1) determinarea coordonatelor piesei cu număr maxim de elemente înainte ca Dorel să efectueze operațiile de upgrade;
2) determinarea numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.

Ionel are de rezolvat o nouă problemă. El trebuie să construiască un șir de N numere naturale. Numerele din șir pot avea ca divizori primi doar numere prime de o cifră. După construirea șirului, Ionel a constatat că există subsecvențe în șir pentru care produsul elementelor este cubul unui număr natural. Ionel vrea să determine numărul subsecvențelor din șirul construit care au produsul elementelor o valoare ce este cubul unui număr natural.

Tocmai ai primit un șir v de K numere naturale nenule distincte. Plecând de la acest șir, te-ai gândit să construiești un șir w de N numere naturale distincte, astfel încât un număr x este în șirul w dacă și numai dacă exista inițial în șirul v sau se pot alege cel puțin două numere din șirul v astfel încât x este cel mai mare divizor comun al acelor numere. De exemplu, dacă v = {4, 6, 7} atunci w = {1, 2, 4, 6, 7}. Uimit de proprietățile matematice frumoase ale noului șir w, ai uitat din păcate șirul original v de la care ai pornit. Dându-se șirul w, să se găsească un șir posibil inițial v având un număr minim de elemente.

Se consideră 3 progresii aritmetice de numere naturale nenule. Notăm cu Pi, 1 ≤ i ≤ 3, mulțimile formate cu elementele progresiei i. Fie P = P1 \( \bigcup \) P2 \( \bigcup \) P3 reuniunea mulțimilor P1, P2, P3. Să se determine cardinalul mulțimii P.

• Inițial, copiii se așază pe axa Ox, copilul i la distanța Xi metri față de origine.
• Copilul cel mai aproape de origine alege un cuvânt secret și îl transmite celui din dreapta lui; cel din dreapta lui îl transmite următorului și așa mai departe până se ajunge la ultimul copil.

1. Care este durata minimă a jocului, dacă Dorel nu ia parte la joc?
2. Care este durata minimă a jocului, dacă Dorel ia parte la joc și se poziționează în mod optim pentru a minimiza durata jocului?

Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N. Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.