Lista de probleme 3

Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există N planete diferite și M canale bidirecţionale de transport de tipul (x, y, t) care îţi permit să te deplasezi de pe planeta x pe planeta y (sau invers) în t secunde.

Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă x pe orice altă planetă y în P secunde cu condiţia că ai putea ajunge pornind de pe planeta x pe planeta y folosind maxim L canale de transport.

Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de K ori. Marian se află pe planeta 1 și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta N.

Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

O partiție a unui număr natural n se definește ca o mulțime ordonată de numere naturale nenule (p1 , p2, … , pk) ce conține cel puțin două elemente, îndeplinind condiția: p1 +p2 +...+pk=n.

Să considerăm pentru un număr natural n toate partițiile luate în ordine lexicografică.

Cunoscând valoarea numărului natural n:

1. pentru un număr k dat, să se tipărească partiția de pe poziția k din tabelul lexicografic.
2. pentru o partiție dată, să se calculeze numărul de ordine a ei din tabelul lexicografic

Se dă un șir de N numere întregi notat cu A. O subsecvență a șirului A este un șir Ai Ai+1 Ai+2 ... Aj cu 1 ≤ i ≤ j ≤ N, iar lungimea acestei subsecvențe este egală cu j – i + 1. O operație constă în alegerea unei subsecvențe din șir și ștergerea acesteia. În cadrul unei operații, lungimea subsecvenței alese trebuie să fie o putere de 2. În cadrul tuturor operațiilor efectuate pe șir, lungimile subsecvențelor șterse trebuie să fie distincte.

Pentru fiecare subsecvență din șir considerăm suma elementelor ei. Definim costul unui șir ca fiind maximul acestor sume, în cazul în care șirul conține cel puțin un număr pozitiv, altfel costul șirului este egal cu 0.

Putem aplica o succesiune de operații (eventual niciuna) pe șirul A. În urma acestor operații se vor șterge
anumite elemente din șir, obținându-se astfel o mulțime de șiruri M={A, A’1 , A’2, A’3 , ...}.

Să se determine costul maxim posibil ce se poate obține dintr-un șir al mulțimii M.