Lista de probleme 2064

Á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 N, 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.

Se dă un număr n și apoi un șir cu n elemente, numere naturale nenule. Să se determine câte dintre numerele din șir sunt strict mai mari decât precedentele 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.

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 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.

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.

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.

Î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ă.

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 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.