Lista de probleme 928

Se dă un arbore cu \(N\) noduri înrădăcinat în nodul \(1\), unde fiecare nod are un pondere asociat întreg \(V_i\). Să se proceseze \(Q\) evenimente de următoarele \(3\) tipuri:

• \(1 \ k \ v\) – ponderele nodului \(k\) devine egal cu \(v\)
• \(2 \ a \ b\) – să se afișeze ponderele minim al unui nod de pe drumul simplu de la nodul \(a\) la nodul \(b\).
• \(3 \ k\) – să se afișeze ponderele minim al unui nod din subarborele înrădăcinat în nodul \(k\).

Pentru avea succes la Olimpiada de Jocuri pe Internet (OJI), Vasilică a cumpărat de la Baba Yaga un talisman norocos. Talismanul norocos este un șir care îndeplineşte următoarele două condiţii:

• toate elementele șirului sunt cifre mai mici sau egale cu magicul 7;
• oricare două elemente aflate pe poziții consecutive în șir au cel puţin un divizor comun strict mai mare decât 1.

1. determinaţi numărul minim de cifre care trebuie să fie eliminate din șirul V, astfel încât acesta să devină talisman norocos;
2. determinaţi talismanul norocos minim lexicografic, care se obţine eliminând din șirul V un număr minim de cifre.

Se consideră un număr natural nenul N și o matrice cu N linii și coloane, numerotate de la 1 la N. Determinați numărul de modalități în care se poate ajunge de la elementul de coordonate (1,1) la cel de coordonate (N,N), cu condiția că, din elementul (i,j) se poate trece în ordice element (iv, jv), pentru care iv ≥ i, jv ≥ j.

Gușteru’ a descoperit într-un dulap un vechi joc de aventură, numit Ijnamuj. Jocul inițial pornește de la nivelul 1, iar scopul este completarea a cât mai multor nivele. Fiecare nivel i are asociată o listă L(i) care conține alte nivele din joc. Pentru a completa nivelul i, Gușteru’ va trebui mai întâi să completeze toate nivelele din lista L(i), în orice ordine dorește el. După completarea oricărui nivel, el poate să completeze orice alt nivel a cărui listă conține numai nivele completate. Pentru că jocul începe de la nivelul 1, lista L(1) va fi mereu vidă, adică completarea lui nu este restricționată de niciun alt nivel. Care este numărul maxim de nivele pe care le poate completa Gușteru’?

Dexter și-a deschis un laborator nou în care vrea să efectueze o serie de experimente pe șoareci pentru a descoperi leacul pentru cancer. În laborator există N șoareci, care se află așezați într-un cerc și sunt numerotați în ordine de la 0 la N-1. Dexter efectuează, pe rând, M experimente. Pentru fiecare experiment șoarecii care participă la al i-lea experiment formează întotdeauna un interval continuu, exprimat sub forma unei perechi de numere (S[i], F[i]), având semnificația:

• dacă S[i] ≤ F[i], atunci șoarecii S[i], S[i]+1, ..., F[i] participă la experimentul i;
• dacă S[i] > F[i], atunci șoarecii S[i], S[i]+1, ..., N-2, N-1, 0, ..., F[i] participă la experimentul i.

La fiecare pas, Dexter vrea să știe câți din cei N șoareci au participat la toate experimentele efectuate până atunci. Altfel spus, după fiecare al i-lea experiment efectuat, să se determine numărul de șoareci care au participat la toate experimentele 1, 2, ..., i.

Andrei se află într-un labirint format dintr-o matrice de camere, fiecare având unul dintre următoarele tipuri: 0: cameră cu bec stins, 1: cameră cu bec aprins, 2: cameră fără bec (inaccesibilă), 3: cameră cu întrerupător.

Camerele de tip 3 pot aprinde/stinge becurile altor camere. Andrei poate alege să apese sau nu întrerupătoarele întâlnite. El pornește dintr-o cameră dată și trebuie să ajungă într-o cameră destinație, deplasându-se doar prin camere aprinse.

Se cere determinarea distanței minime pentru a ajunge la destinație.

Să considerăm n zaruri, numerotate de la 1 la n. La aruncarea celor n zaruri obţinem o succesiune de n numere naturale cuprinse între 1 și 6. Suma unei aruncări va fi egală cu suma numerelor obţinute. Câte aruncări de n zaruri au suma cuprinsă între st și dr? Scrieți un program ce calculează răspunsul pentru mai multe întrebări de forma celei de mai sus. Pentru că numărul de aruncări poate fi destul de mare, calculați răspunsul modulo 1.000.003.

De câte ori trebuie să transmită un mesaj URGENT!!! directorul şcolii noastre are o mare problemă. Indiferent de canalul de comunicare pe care îl foloseşte (e-mail, what’s app, site-ul şcolii etc.), întotdeauna vor exista elevi la care mesajul nu ajunge sau nu ajunge în timp util. După multe încercări, a decis să numeroteze cei n elevi din şcoală cu numere distincte de la 1 la n şi să studieze relaţiile de comunicare dintre elevi. Apoi, bazându-se pe aceste relaţii de comunicare, să aleagă un număr minim de elevi-răspândaci cărora să le transmită mesajul direct, urmând ca aceasta să fie transmis la absolut toţi elevii, prin relaţiile de comunicare dintre aceştia. Să se scrie un program care, cunoscând relaţiile de comunicare dintre elevi, determină numărul minim de răspândaci necesari pentru ca mesajul directorului să ajungă în timp util la toţi elevii din şcoală.

Se dă un graf neorientat, nu neapărat conex. În unele componente conexe este posibil să fie un nod special. Acest lucru înseamnă că nu există lanț între două noduri speciale. Să se adauge un număr maxim de muchii astfel încât în continuare, orice două noduri speciale am alege, nu există lanț între ele.

Se dă un arbore cu \(N\) noduri și \(N-1\) muchii etichetate cu o literă fiecare. Vom defini un drum \((x, y)\) ca fiind secvența de muchii care duc de la nodul \(x\) la nodul \(y\). De asemenea, vom considera drumurile \((x, y)\) si \((y, x)\) ca fiind același drum. Un drum poate fi palindromic dacă există o cale de a permuta toate literele parcurse in drumul respectiv în așa fel încât să formăm un drum palindromic.

Să se afle câte drumuri pot fi palindromice.