Lista de probleme 33

Se dă un arbore cu N noduri numerotate de la 1 la N cu rădăcina în nodul 1. Fiecare nod din arborele dat are o valoare întreagă atașată. Se dau M întrebări de forma (x, y), unde x este un strămoș al nodului y: dacă s-ar elimina toate nodurile de pe lanțul care unește x cu y (inclusiv nodurile x și y), care ar fi valoarea maximă din nodurile neeliminate?

Cunoscând numărul de noduri N, configurația arborelui, valorile atașate celor N noduri, și cele M întrebări, să se răspundă la fiecare întrebare dată.

Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.

Se dă planul unei rețele de metrou cu N stații și M tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i are asociat un profit p[i] dat.

Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.

Dându-se N, M, profiturile aduse de fiecare din cele N stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.

Un şir format din cifre trebuie să fie tastat în una sau mai multe sesiuni.

Există două tastaturi: tastatura A care conţine taste cu toate combinaţiile de exact două cifre: tasta 00, tasta 01, 02, …, 98, 99 și tastatura B care conţine taste cu toate combinaţiile de exact trei cifre: tasta 000, tasta 001, …, 998, 999. Cifrele se vor introduce în una sau mai multe sesiuni, pentru o sesiune putându-se folosi o singură tastatură. Datorită unei ordonanțe de urgență, dacă o combinație de taste a fost introdusă cu una din tastaturi în sesiunea curentă și, continuând sesiunea, această combinație poate fi introdusă din nou, este necesar să continuăm sesiunea cel puțin până când o vom introduce din nou. În cazul în care introducem până atunci și alte taste, trebuie să continuăm sesiunea până când vom introduce ultima apariție a lor.

Astfel, dacă şirul 255222255257 este început folosind tastatura A, se va scrie obligatoriu într‑o sesiune 25 52 22 25 52. Suntem obligați să tastăm până la ultima apariție a tastei 25 în sesiunea curentă, și când folosim tasta 52 suntem obligați să continuăm până la ultima apariție a acesteia. A se observa că cifrele de pe pozițiile subliniate sunt tot 2 și 5, însă nu formează o tastă care se poate apăsa în sesiunea curentă. Deoarece se dorește un număr cât mai mare de sesiuni, se va începe o nouă sesiune în care se va scrie doar 57.

Cunoscându-se numărul total de cifre și secvența de cifre ce formează şirul, să se determine o modalitate de a despărţi textul astfel încât el să poată fi scris într-un număr maxim de sesiuni.