Lista de probleme 888

Se dă un vector cu N elemente numere naturale numerotate de la 1 la N și M operații de forma:

• 1 x y, cu semnificația: elementul de poziția x ia valoarea valoarea y.
• 2 x y: se determină valoarea minimă a elementelor cu indici cuprinși între x și y.

Afișați rezultatele operațiilor de tipul 2.

Un program citeşte o valoare naturală nenulă impară pentru n şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n cifre care îndeplinesc următoarele proprietăţi:

- încep şi se termină cu 0;
- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.

Doi prieteni te provoacă la un joc. Cerința este simplă: trebuie doar să ghicești lungimea maximă a unui subșir crescător al șirului dat. Accepți provocarea?

Se citesc două numere naturale n și m. Afișați în ordine lexicografică toate cuvintele care sunt formate din
m litere folosind primele n litere mari din alfabet și care au literele ordonate alfabetic.

Atunci când nu se luptă cu Vilgax, Ben și Gwen se joacă pe calculator sau pe telefon. Unul dintre jocurile lor preferate se numește CTC și presupune numărararea vârfurilor din componentele tare conexe ale grafurilor orientate. Mai exact, Ben numără câte componente tare conexe au număr par de vărfuri, iar Gwen numără câte componente tare conexe au număr impar de vârfuri. Stabiliți care dintre cei doi veri câștigă jocul.

Într-un oraș sunt n case numerotate de la 1 la n. Între anumite case sunt străzi bidirecționale. În casa cu indicele g locuiește Ghiocel. El are k colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghicei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care Ghiocel are de parcurs un număr minim de străzi. Ajutați-l pe Ghiocel să determine numerele acestor case.

Se dă un digraf (graf orientat) cu n noduri numerotate de la 1 la n. Graful componentelor tare conexe se obține astfel: se construiesc componentele tare conexe, apoi fiecare astfel de componentă devine nod în noul graf. Apoi din lista inițială de arce se păstrează în noul graf numai arcele care au extremitățile în componente tare conexe diferite. Să se afișeze listele de adiacență asociate noului digraf.

Se dă un arbore cu n noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la Q întrebări de forma: dacă u şi v sunt două noduri din arbore, care este valoarea xor a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte u şi v?

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf q. Să se determine cel mai lung lanț elementar cu extremitatea finală în q.

Mario a primit de ziua lui un nou joc video, “ Up “. În acest joc are n baloane numerotate de la 1 la n. Fiecare balon i ( 1 ≤ i ≤ n ) se află la o distanță di de sol. La începutul jocului Mario poate alege oricare dintre cele n baloane pe care să se poziționeze. Aflându-se la un moment dat pe un balon cu numărul de ordine l, băiatul poare sări pe oricare alt balon cu indicele t doar daca l < t și dl < dt. Jocul continuă până când nu mai există baloane care să respecte condiția dată. Numărul de baloane pe care jucatorul sare este egal cu scorul obținut. Mario, curios din fire, vrea să afle care este scorul maxim pe care l-ar putea obține în joc.