taxe

[•cr1st18]

am o intrebare la problema asta daca o stie carevea de la oji 2003 acea cu taxe...vroiam sa intreb.....pt rezolvare mi-ar trebui 2 matrici si fac in fel acesta? adica introduc prima poz in coada....apoi parcurg matricea si incep sa verific vecinii care ii bag in coada si il aleg pe acela care ia taxa mai mica...?:-/

[•miculprogramator]

Cred ca am gasit problema:

Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.
Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune nxn. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

Cerinţă
Ştiind că el are în buzunar S euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

Date de intrare
Fişierul de intrare taxe.in conţine pe prima linie cele două numere S şi n despărţite printr-un spaţiu, iar pe următoarele n linii câte n numere separate prin spaţii ce reprezintă taxele cerute de funcţionarii din fiecare birou.

Date de ieşire
Fişierul de ieşire taxe.out conţine o singură linie pe care se află numărul maxim de euro care îi rămân în buzunar sau valoarea –1 dacă investitorului nu-i ajung banii pentru a obţine aprobarea.

Restricţii
3<=N<=100
1<=S<=10000
Valorile reprezentând taxele cerute de funcţionarii din birouri sunt numere naturale, o taxă nedepăşind valoarea de 200 de euro.
La încheierea programului nu se va solicita apăsarea unei taste.

Asta e?

[•cr1st18]

da......

[•cr1st18]

am gasit si rezolvarea da ii in pascal si n-o inteleg in totalitate.....

[•toni2007]

Se face cu parcurgere in latime. Nu cred totusi ca are importanta in ce e codat ca sa il intelegi.

[•Mishu91]

Citeste despre algoritmul Belman-Ford. In cazul acesta este o adaptare a acestui algoritm la o matrice

[•cr1st18]

am o intrebare ii bine daca as face asa "bag primu element in coada....apoi parcurg matricea si scot primu element din coada....si ii verific vecinii pe care ii bag in coada(bineinteles directiile in care se poate merge)....si cand revin iarasi la pasu cu scoaterea unui elem din coada....il aleg pe cel care are o taxa mai mica s.a.m.d pana ajung la poz finala".

[•Mishu91]

Poate daca ai fi putin mai coerent si ai folosi propozitii lumea chiar ar intelege ce ai vrut sa zici si poate te-ar putea ajuta

[•cr1st18]

vreau sa spun ca fac pasii de la lee ..numai ca la pasul cand trebuie sa scot un element din coada....il scot pe cel cu taxa cea mai mica pana atunci ....nu pe ultimu-l explorat

[•alexandru92]

vreau sa spun ca fac pasii de la lee ..numai ca la pasul cand trebuie sa scot un element din coada....il scot pe cel cu taxa cea mai mica pana atunci ....nu pe ultimu-l explorat

Si de ce nu pui direct in coada  doar pe cel mai mic vecin al camerei x ?
Nu mi se pare o idee prea buna si ca drept dovada sa luam exemplul din enunt :
10 3
1 2 5
1 3 1
0 8 1
La tine ar fi 1->1->0->8->1,  corect fiind 1->1->3->1->1

[•Mishu91]

Din ce am inteles eu, vrea sa faca ceva gen Dijkstra, adica la fiecare pas aleg sa ma duc in nodul cu suma minima de pana atunci, pentru ca toate celelalte avand costul mai mare, nu il mai pot imbunatati pe cel ales.