Lista de probleme 888

Cătălin lucrează la o firmă de transport de marfă. El se ocupă de planificarea traseelor pe care circulă camioanele. Există N trasee pe care pot merge camioanele, pe fiecare traseu poate circula cel mult un camion, iar acest camion nu poate depăși o limită de greutate ai. Firma deţine M camioane, fiecare camion poate circula pe maxim un traseu şi are o greutate bi. Ajutați-l pe Cătălin să planifice camioanele pe trasee în așa fel încât să poată circula cât mai multe camioane. Determinați numărul maxim de camioane care pot circula în același timp pe trasee și afișați o modalitate de a distribui camioanele pe trasee pentru a obține acest maxim.

Primăria din Iași a hotărât să modernizeze șoselele din localitate. O șosea este o porțiune de drum care unește două intersecții. Firma constructoare a făcut un studiu pentru a determina costurile pentru fiecare șosea. Fondurile sunt limitate, astfel că în prima fază vor fi modernizate doar drumurile din apropierea Palas-ului, care se află la intersecția cu numărul 1. Mai precis: orice șosea modernizată trebuie sa fie cel puțin la fel de aproape de Palas ca orice șosea ce nu va fi modernizată.

Lungimea drumului dintre două intersecții a și b este numărul cel mai mic de intersecții ce trebuie parcurse pentru a ajunge de la a la b. Șoseaua (a, b) este mai aproape de Palas față de șoseaua (c, d) dacă lungimea drumului de la Palas până la cea mai apropiată intersecție dintre a și b este mai mică decât până la cea mai apropiată intersecție dintre c și d. Dacă lungimile drumurilor până la cele mai apropiate intersecții sunt egale, se compară lungimile drumurilor până la celelalte două intersecții. De exemplu dacă pentru șoselele (4, 7) și (3, 5) avem distanțele de la Palas până la intersecțiile: 3, 4, 5, 7 egale cu: 10, 10, 10, 11 în această ordine, atunci (3, 5) e mai aproape de Palas față de (4, 7) deoarece distanțele minime sunt ambele egale cu 10 dar distanța până la intersecția 3 este tot 10, mai mică față de distanța până la intersecția 7 care este 11. Dacă nu există cale de acces de la Palas la o intersecție a atunci șoselele legate de a nu vor fi modernizate.

Cunoscând: N – numărul de intersecții din oraș codificate prin numere naturale din mulțimea 1..N, M – numărul de șosele și șoselele împreună cu costul de modernizare, și F – fondurile de care dispune primăria, să se afle K – numărul maxim de șosele care pot fi modernizate.

Gioni este un elev foarte pasionat de informatică și îndrăgește în special problemele care se rezolvă cu tehnica programării dinamice. El are un număr natural n și vrea să știe pentru fiecare numar i de la 1 la n câte numere cu i cifre nu sunt palindromuri. Fiindcă acest număr poate să fie foarte mare, se cere afișarea lui modulo 666013.

Se consideră un graf neorientat conex cu n noduri și n muchii. Să se determine numărul arborilor parțiali ai grafului.

Într-un magazin intergalactic sunt n tipuri de obiecte, o infinitate din fiecare; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

Se dă un șir de n cifre. Șirul se împarte în secvențe disjuncte de cifre, fiecare secvență având lungimea cel mult 6. Cu fiecare secvență extrasă se formează numărul corespunzător și apoi se adună doar numerele prime obținute. De exemplu, dacă șirul de cifre este 37237, se pot extrage secvențele disjuncte 3, 72, 37, iar suma numerelor prime este 3 + 37 = 40. O altă modalitate este 3, 7237 care are suma 7240 (deoarece numărul 7237 este prim). Să se determine suma maximă care se poate obține împărțind șirul în secvențe disjuncte de lungimi cel mult 6 și adunând apoi numai numerele prime.

Spunem că un cuvânt este valid dacă el este format doar cu litere din mulțimea {a,b,c,d} și literele a și b nu sunt alăturate. De exemplu, cuvintele aaaa, acdca sunt valide, dar abbc și baabd nu sunt. Să se determine numărul cuvintelor valide de lungime n. Pentru că acest număr este foarte mare, se va afișa rezultatul modulo 777013.

Dorel tocmai a aflat despre existenţa şirului lui Fibonacci: F₀=0, F₁=1, F₂=1, F₃=2, F₄=3, F₅=5,… . Pentru numerele n, k şi p date, Dorel vă roagă să calculaţi suma F_p + F_k+p + F_2•k+p + … + F_n•k+p.