Lista de probleme 2077

Se consideră șirul A=(A[1], A[2],..., A[n]) cu n numere naturale nenule. Pe baza șirului A se construiește șirul B, unde fiecare element B[i] este cel mai mic număr natural care are aceiași factori primi cu A[i], cu 1 ≤ i ≤ n. O secvență de cel puțin două numere aflate pe poziții consecutive în șirul B este mandatorie dacă există un număr x (2 ≤ x ≤ 9) în această secvență care divide fiecare dintre elementele secvenței. Numim acest număr x - mandatar al secvenței. Lungimea secvenței este egală cu numărul de elemente ale acesteia.
1) Determinați cel mai mare număr prim din șirul A.
2) Determinați cel mai mare număr al șirului B ce are un număr maxim de factori primi.
3) Determinați lungimea maximă a unei secvențe mandatorii din șirul B.

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.

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.

Á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^{\prime },j^{\prime }$ astfel încât $A_{i^{\prime },j^{\prime }}=A_{i,j}$.
• folosind o uşă, orice camera vecină cu un număr asociat consecutiv, deci care corespunde unui element $i^{\prime },j^{\prime }$ astfel încât $|i^{\prime }-i|+|j^{\prime }-j|=1$ și $A_{i^{\prime },j^{\prime }}=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.

În regatul „Iluminia” există un laborator care conține o rețea de N camere, fiecare cameră are lungimea P și este reprezentată de o secvență de comutatoare, fiecare comutator având starea 0 (stins) sau 1 (aprins).

Regele dorește să construiască o cameră supremă pentru un experiment de mare anvergură. Această cameră supremă se obține prin aplicarea operației XOR (^) asupra tuturor secvențelor de comutatoare. Regele vrea ca această cameră rezultată să fie „supremă”, adică să conțină doar comutatoare în starea 1.

Deoarece acest lucru nu este garantat, regele are la dispoziție M operații de flip. Fiecare flip inversează starea anumitor comutatoare dintr-o subsecență de lungime cel mult L (0 devine 1, iar 1 devine 0). Comutatoarele care vor fi inversate sunt la discreția regelui.

Acest lucru înseamnă că regele are posibilitatea de a alege, dintr-o subsecență dată de comutatoare, care dintre acestea să fie inversate. El nu este obligat să inverseze toate comutatoarele din subsecența aleasă, ci poate alege doar anumite comutatoare, în funcție de cum consideră că este cel mai eficient pentru găsirea camerei supreme.

Sarcina ta este să găsești cea mai mică valoare L pentru care există o succesiune de cel mult M flip-uri (fiecare aplicată pe o subsecență de lungime cel mult L) care să construiască camera supremă.

Aflat pe plaja urbană din cartierul Cricozescu al orașului Jluc, Andrei participă la un concurs de construcții de castele de nisip. Fiecare concurent a construit deja un anumit număr de castele n, însă organizatorii concursului au schimbat regulile în ultimul moment, astfel că, pentru a fi eligibili în etapa de jurizare, toate castelele concurenților trebuie să aibă exact aceeași înălțime. Andrei ne cere să îl ajutăm să determine numărul minim de operații pe care el trebuie să le facă asupra castelelor sale astfel încât toate să aibă, în final, aceeași înălțime.

Fermierul Ion, cândva cunoscut pentru porumbul său de înaltă calitate, a intrat în faliment. Acum, el se mulțumește să crească roșii pe un câmp pătratic împărțit în N × N parcele. La început, câmpul era gol, dar de-a lungul timpului, Ion a efectuat mai multe plantări respectând o regulă specială, numită formula roșiilor gustoase:

• se alege un număr v;
• se alege o porțiune a câmpului definită de colțul stânga-sus (a, b) și colțul dreapta-jos (c, d. Cu alte cuvinte, pentru orice 1 ≤ i, j ≤ N, porțiunea câmpului conține parcela de pe linia i și coloana j dacă a ≤ i ≤ c și b ≤ j ≤ d.
• în fiecare parcelă din porțiune se plantează un număr de roșii egal cu suma modulo 1789 a numerelor mai mici decât v care sunt coprime cu v.

Se consideră șirul de N cifre nenule a = (a[1], a[2], ..., a[N]). Prin frecvență de apariție a unei cifre în șir înțelegem numărul de apariții ale cifrei în acest șir. Pentru o secvență a[i], a[i+1], ..., a[j] din acest șir (1 ≤ i < j ≤ N) calculăm frecvența fiecărei cifre distincte prezente în secvență și definim *diff*-ul secvenței ca fiind diferența dintre cea mai mare frecvență și cea mai mică frecvență dintre cele calculate.

1) Determinați frecvența maximă de apariție a unei cifre din șirul a.
2) Determinați diff-ul maxim posibil al unei secvențe care începe de la prima poziție din șirul a.
3) Determinați diff-ul maxim al unei secvențe din șirul a.

Pentru un număr natural N considerăm șirul: 0, 1, 2, …, N.
1) Se dau Q perechi de numere naturale de forma (a,b). Pentru fiecare pereche se cere să se determine numărul de numere prime care află în secvența de numere consecutive: a, a+1, a+2, ..., b.
2) Se dau Q numere naturale p1, p2, …, pQ. Pentru fiecare număr pi se cere să se determine numărul secvențelor a, a+1, a+2, ..., b din șirul 0, 1, ..., N care conțin câte pi numere prime (1 ≤ i ≤ Q).

Mihai și Ioana au creat o reprezentare a matricii A cu N linii (numerotate de la 0 la N-1) şi M coloane (numerotate de la 0 la M-1) în care fiecare element A[i][j] este determinat pe baza următoarei formule: A[i][j] = (15 * i + 4 * j + 2025) % K, unde i și j sunt indicii liniei și coloanei, iar K este un număr natural nenul, ales de ei.
1) Determinați numărul de numere speciale care există în matricea A.
2) Determinați numărul elementelor din matricea A care sunt numere aproape speciale, la care Mihai și Ioana ajung în același timp.