Lista de probleme 888

Se consideră pe axa Ox din plan n puncte distincte reprezentând centrele a n cercuri numerotate cu numerele distincte de la 1 la n. Pentru fiecare cerc k se cunosc abscisa xk a centrului său şi raza sa rk.

Să se scrie un program care să determine numărul y maxim de cercuri exterioare două câte două dintre cele n.

Se citesc două numere naturale n și m. Afișați în ordine lexicografică toate cuvintele care sunt formate din n litere E și m litere M cu proprietatea că nu există mai mult de două litere M alăturate și nici mai mult de două litere E alăturate.

Se consideră un graf orientat cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de arce al unui drum elementar care uneşte x cu y.

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța minimă dintre x și y.

Dom’ Profesor Unu și Dom’ Profesor Doi au găsit o matrice cu n linii numerotate de la 1 la n și n coloane numerotate de la 1 la n și elemente numere naturale. Semnificativ marcați de algoritmul de determinare a celui mai lung subșir crescător, au inventat pe loc un joc:

• liniile cu indice impar aparțin lui Dom’ Profesor Unu, cele cu indice par aparțin lui Dom’ Profesor Doi;
• pentru fiecare linie a sa, Dom’ Profesor Unu determină lungimea maximă a unui subșir crescător;
• pentru fiecare linie a sa, Dom’ Profesor Doi determină lungimea maximă a unui subșir descrescător;
• scorul fiecărei linii este lungimea determinată;
• scorul total al fiecărui Dom’ Profesor este egal cu suma scorurilor liniilor corespunzătoare;
• jocul este câștigat de Dom’ Profesor cu scorul total mai mare.

Determinați scorului fiecărui Dom’ Profesor și stabiliți câștigătorul.

Se consideră un graf neorientat conex cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de muchii al unui lanţ elementar care uneşte x cu y.

Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța de la x la y.

Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.

Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la N. Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.

La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.

Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:

• La dreapta, ajungând în sectorul (i,j+1) .
• Pe diagonala la dreapta în sus, ajungând în sectorul (i-1,j+1).
• Pe diagonala la dreapta în jos, ajungând în sectorul (i+1,j+1).

Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.

Șcuțu, elev pe clasa a 10-a, s-a plictisit să lucreze probleme de clasa a 6-a. Mygo a văzut că Șcuțu a reușit să obțină 100p pe problema Munte de la OJI2014, însă nu cu o soluție prea inteligentă, așa că îi va pune o provocare. Se dă un vector A de N elemente indexat de la 1. Un vârf este un element A[i] cu proprietatea că A[i-1] < A[i] > A[i+1] (1 < i < N). Mygo îi oferă lui Șcuțu Q operații de tipul:

• 1 x y: “Elementul de pe poziția x ia valoarea y”.
• 2 x y: “Având o copie a vectorului A[x...y] (ceea ce urmează nu va afecta cu nimic vectorul A), se determină toate vârfurile iar acestea se elimină, procedeul acesta continuă până când nu vor mai exista vârfuri. Se cere să se afișeze câte vârfuri au existat de la început până la final”.

Se dau două numere naturale n și m. Determinati o modalitate alegere de m numere din mulțimea \({1,2,…,n}\) și de așezare a lor pe un cerc astfel încât suma a oricare două nume învecinate să fie pătrat perfect.

Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:

• 1 x – adaugă numărul x în A
• 2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare?

Să se răspundă la cele n întrebări.

Se dă un şir format din n numere naturale nenule. Aflaţi lungimea maximă a unui subşir al şirului dat, astfel încât oricare două elemente consecutive din subşir să nu fie prime între ele.