Lista de probleme 237

Filtrare

#4557 Lee3

Se dă o matrice binara cu N linii și M coloane. Celulele cu numarul 0 sunt libere si se pot traversa. Celulele cu numarul 1 sunt ocupate si nu se pot traversa. Pentru K poziții date, se cere să se determine drumul de lungime minimă care pleacă de la poziția (i1, j1) și trece prin toate cele K poziții intermediare (nu contează în ce ordine), ajungând în final în poziția (i2, j2).

#4568 Sandale

Între timp, într-un univers paralel…

Ștefan Ghe este creatorul site-ului renumit de probleme de algoritmică InfoZona. Din păcate, verișorul său diabolic, Feștan Ț, punându-și în practică skill-urile de hacker nebunatic, a spart site-ul InfoZona și îl va da înapoi domnului Ștefan doar dacă reușeste să rezolve următoarea problemă:

Se dă un șir A, indexat de la 1, de N numere naturale nenule, reprezentând un raft de sandale. Vom defini funcția \( F(l,r) = ( \sum_{i=l}^{r} A[i] )^3 \) ca fiind costul pentru a cumpara sandalele din secvența [l, r] laolaltă, toate în același coș de cumpărături. Feștan Ț are K coșuri de cumpărături la dispoziție și dorește să afle care este prețul minim pe care poate cumpăra toate cele N sandale, folosind coșurile de cumpărături de care dispune.

Ajutați-l pe domnul Ștefan Ghe să-și recupereze site-ul rezolvând această problemă și vă va face cinste cu o bere și cinci cămile!

Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:

  • termenul i al sumei se află pe linia i din triunghi
  • pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mare sumă care se poate obține în acest mod.

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1). Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n,m).

Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

Se consideră un triunghi de numere naturale format din n linii.Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, astfel:

  • termenul i al sumei se află pe linia i din triunghi
  • pentru un anumit termen al sumei, termenul următor se află pe linia următoare și pe aceeași coloană, sau pe coloana imediat următoare spre dreapta.

Să se determine cea mai mică sumă care se poate obține în acest mod și numerele care o alcătuiesc.

Harta jocului PacmMan este sub forma unui dreptunghi împărțit în camere organizate pe linii și coloane. Din fiecare cameră se poate merge în camera situate pe coloana următoare și pe aceeași linie, sau in camera de pe coloana următoare și linia următoare, dar fără a ieși din hartă. Astfel din camera (i,j) se poate merge în camerele (i,j+1) și (i+1,j+1). PacMan se află în camera situată pe prima linie și pe prima coloana (1,1) și trebuie să ajungă în camera de pe ultima linie și ultima coloană (n,m). Calculați și afișați numărul de trasee pe care poate PacMan să parcurgă harta.

Se consideră un triunghi de numere întregi format din n linii. Prima linie conține un număr, a doua linie conține 2 numere, etc. ultima linie n, conține n numere. În acest triunghi se pot calcula diverse sume cu n elemente, în funcție de modul de parcurgere a numerelor din triunghi. Unul dintre aceste moduri este următorul:
  • se pleacă din ultimul element al ultimei linii
  • se merge întotdeauna spre stânga pe aceeași linie sau pe linia de deasupra, adică de pe linia i și coloana j se merge pe linia i și coloana j-1 sau pe linia i-1 și coloana j-1.
  • parcurgerile se termină pe prima coloană.

Să se determine cea mai mare sumă care se poate obține în acest mod.

Alice s-a pierdut din nou în labirint. Labirintul este de forma unui triunghi dreptunghic împărțit în camere organizate pe linii și coloane. Pe prima linie este o singură cameră, pe a doua sunt două camere, etc. Pe ultima linie sunt n camere. Din fiecare cameră se poate merge în camerele situate pe linia următoare și pe aceeași coloană, sau pe coloane cu 1 mai mari sau mai mici decât coloana curentă, dar fără să se părăsească labirintul. Astfel din camera (i,j) se poate merge în camerele (i+1,j-1), (i+1,j) și (i+1,j+1), dacă acestea există. Alice se află în camera de pe prima linia și de pe prima coloana (1,1).

Ca să iasă din labirint, Alice trebuie să ajungă într-o cameră de pe ultima linie. Calculați și afișați numărul de trasee pe care poate Alice să iasă din labirint.

Fermierul Gigel are o livadă cu peri de forma unui triunghi dreptunghic cu laturile de câte n peri fiecare și având perii organizați pe linii și coloane. Pe prima linie este un singur păr, pe a doua doi peri, etc. Pe ultima linie sunt n peri. Pentru fiecare păr se cunoaște numărul de pere din el. Hoțul Dorel intră în livada lui Gigel prin colțul stânga jos, adică prin primul element al ultimei linii. El se poate deplasa paralel cu rândurile de peri, adică cu liniile, respectiv cu coloanele livezii. Astfel, dintr-o poziție aflată pe linia i și coloana j, Dorel poate merge pe linia i-1 și coloana j sau pe linia i și coloana j+1. Ca să nu îl prindă Gigel, hoțul Dorel trebuie ia toate perele din perii de pe traseul pe care merge, să iasă pe la sfârșitul unei linii de peri și să fure un număr minim de pere (deoarece nu e lacom sau nu le poate duce și îl prinde Gigel).

#4576 BilboB

Bilbo Baggins a reușit să intre în Muntele Singuratic. În Muntele Singuratic este o rețea de n galerii numerotate de la 1 la n, fiecare galerie fiind împărțită în m camere numerotate de la 1 la m. Bilbo găsește o hartă a acestor galerii și vede că în fiecare din cele n*m camere se află o cantitate de aur. Bilbo a intrat prin prima cameră a primei galerii și conform hărții poate iesi doar prin ultima cameră a primei galerii.

Dintr-o cameră numerotatată (i,j) Bilbo se poate strecura fără a fi detectat de către Smaug doar în camerele numerotate cu (i-1,j+1), (i,j+1) și (i+1,j+1) fără a putea părăsi rețeaua de galerii decât prin camera (1,m).

Să se determine cantitatea maximă de aur pe care o poate colecta Bilbo din Muntele Singuratic.