Lista de probleme 4

În Piatra Neamț sunt N+2 locații numerotate de la 0 la N+1, de la stânga la dreapta. Distanța dintre două locații i si j este egală cu |i – j|. La început, în locațiile 0 și N+1, sunt construite benzinării, și în celelalte locații sunt case. Compania BuildNT a decis sa construiască N benzinării, una în fața fiecărei case.

Înainte să construiască o benzinărie, constructorii calculează valoarea S egală cu suma distanțelor de la fiecare casă la cea mai apropiată benzinărie, si adaugă această sumă la suma totală T. După, ei aleg o casă, la cea mai mare distanță de orice benzinărie, în fața căreia construiesc o nouă benzinărie. Casele sunt alese în așa fel încât, după construirea benzinăriilor, valoarea S recalculată sa fie minimă. Dacă sunt mai multe case ce respectă această regulă, se alege prima din stânga.
Desigur, după ce toate benzinăriile au fost construite, suma S va deveni 0 și suma totală T nu se va mai schimba.

Calculați T pentru o valoare dată N.

Compania lui Jimmy are n plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin n - 1 drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația x la plantația y , pentru fiecare 1 ≤ x, y ≤ n. De asemenea, știm și distanța în km pentru fiecare dintre cele n - 1 drumuri. Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem a tone de flori şi vrem să le trimitem pe o distanță de b kilometri, costul transportului este a * b. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.

Un KST este un arbore de căutare care are K valori în fiecare nod și fiecare nod are K+1 fii. De exemplu, pentru k=1, un KST devine un arbore de căutare binar. Valorile din fiecare nod sunt în ordine crescătoare. Notăm cu v[i], a i-a valoare dintr-un nod. Arborele are următoarea proprietate: pentru fiecare nod, primul său fiu va avea valori mai mici decât v[1], al doilea va avea valori aparținând intervalului (v[1], v[2]), al treilea va avea valori din intervalul (v[2], v[3]), …, penultimul fiu din intervalul (v[k-1], v[k]), ultimul va avea valori mai mari decât v[k]. Un nod nu poate avea fii dacă nu conține K valori. Frunzele pot avea și mai puțin de K valori. Se dă N – numărul de elemente și K, trebuie să se afle câți arbori care respectă cerința există.

Michael își petrece vacanța de vară la bunici, în Delta Dunării. În prima zi, se duce la pescuit cu tatăl său în locul în care acesta se ducea în copilărie. Michael își dă seama că traseul ales nu este singura opțiune de a parcurge distanța de la casa bunicilor până la locul unde pescuiesc, așa că, odată ce vizitează întreaga regiune împreună cu bunicul său, se întreabă în câte moduri distincte poate parcurge distanța de la casa bunicilor la locul unde pescuiesc. Regiunea pe care Michael o cunoaște are formă dreptunghiulară, cu rânduri numerotate de la 1 la L și coloane numerotate de la 1 la C. Valorile de 1 reprezintă zone de uscat și valorile de 0 reprezintă zone acoperite de apă. Michael poate merge doar pe uscat, cu următoarea restricție: din zona de coordonate (i, j) se poate duce doar în una din zonele (i – 1, j + 1), (i, j + 1), (i + 1, j + 1) – bineînțeles, doar dacă acestea reprezintă zone de uscat și Michael nu părăsește regiunea. Fiind un băiat inteligent, când Michael vizitează împrejurimile cu bunicul său, își dă seama de următorul lucru: coloanele din matricea care codifică regiunea se repetă identic din K în K. Coloanele 2, K + 2, 2 * K + 2, … sunt identice, coloanele K – 1, K + (K - 1), 2 * K + (K - 1), … sunt identice. Două coloane c1 și c2 sunt identice dacă elementul de pe poziția (i, c1) este egal cu elementul de pe poziția (i, c2), oricare ar fi i de la 1 la L. Știind coordonatele locului unde se află casa bunicilor și coordonatele locului de pescuit pe care tatăl lui Michael i l-a arătat acestuia, să se determine numărul de moduri de a parcurge distanța dintre ele. Două drumuri sunt considerate distincte dacă, scriind secvența rândurilor vizitate (în ordine crescătoare a coloanelor), ele diferă prin cel puțin o poziție.