[C++]Problem

[TraficantX]

Un automobilist porneste dintr-un oras A si trebuie sa ajunga in orasul B , rezervorul daca este plin , ii permite sa pargurga n kilometri . Pe harta sunt trecute m statii de alimentare si distantele dintre ele . Automobilistul doreste sa opreasca la cat mai putine statii . Scrieti un program care determina statiile de alimentare la care trebuie sa opreasca pentru alimentare.

Indicatii:

1)Soferul nu trebuie sa opreasca neaparat cand are rezervorul gol.

2)Datele se citesc dintr-un fisier text.

3)Va recomand sa folositi metoda Greedy.

Solvers :

-

-

-

-

-

[shop_toolz]

O singura observatie am. Din memoriile mele Greedy pe care o recomanzi are un mic clitch. Construirea pas cu pas a solutiei se cam bate cap in cap cu conditia ta ca nu trebuie sa aiba rezervorul gol. Practic, trebuie verificat la care din urmatoarele statii va avea cat mai putina benzina in rezervor, asta la fiecare trecere prin while-ul de la greedy(daca imi aduc aminte cu while era). Dar pot exista solutii in care este optim sa nu opreasca atunci cand are neaparat mai putina benzina in rezervor. In fine, e un pic mind twisting, o sa incerc sa vin cu o rezolvare greedy si un contraexemplu pentru care metoda greseste.

[dancezar]

O singura observatie am. Din memoriile mele Greedy pe care o recomanzi are un mic clitch. Construirea pas cu pas a solutiei se cam bate cap in cap cu conditia ta ca nu trebuie sa aiba rezervorul gol. Practic, trebuie verificat la care din urmatoarele statii va avea cat mai putina benzina in rezervor, asta la fiecare trecere prin while-ul de la greedy(daca imi aduc aminte cu while era). Dar pot exista solutii in care este optim sa nu opreasca atunci cand are neaparat mai putina benzina in rezervor. In fine, e un pic mind twisting, o sa incerc sa vin cu o rezolvare greedy si un contraexemplu pentru care metoda greseste.

nu neaparat in while merge si in for ,incerc si eu acuma

// o singura nelamurire deci rezervoru ii permite sa merga n kilometri ,trebuie sa citesc si distanta in km de la A la B

[TraficantX]

Da , din fisier se citesc , distanta de la A la B(adica n) si distantele dintre statii.

Si da , greedy merge facut cu for nu doar cu while

[TraficantX]

Nimeni ma!? Asa de grea e?

[qwerty12]

Arata-ne dovada ca ai facut-o tu ... Probabil e tema pentru scoala

[sevenziparchive]

Nu m-am obosit sa invat greedy, cea mai simpla metoda pare sa fie de genul:

cat timp n-ai ajuns la n (sau mai ai de citit statii din fisier)

citeste km statiei

daca poti junge, scazi din rezervor

daca nu poti ajunge, afiseaza oprirea la statia 'contor statie' (sau incrementezi contorul nr opriri) si incarca rezervor

incrementeaza contor statie

sf cat timp

nu am mentionat implementarea variabilelor.

te descurci cu transcrierea in cod, sper...

bafta!

[dancezar]

am facut problema trimitemi pm cu rezolvarea ta si apoi am sa ti-o trimit pe a mea