122 Calatorie interplanetara

[ditzone]

Aici puteţi discuta despre problema Calatorie interplanetara.

[•sarabogdan]

Dati-mi va rog  un hint cum se facea dinamica la problema asta ca nu mi-a iesit nici cum.

[•bogdan2412]

b[i ][j] = valoarea minima de combustibil consumat in viteza normala pana la planeta i mergand exact j unitati de timp cu superviteza.
Solutie = minim ( b[n][j] + j ^ 4 ), j = 1, MAXH

[•dausyana]

aha!!..deci pana l urma era programare dinamica.....mie dc nu mi-o fi iesit??...

[•Adriana_S]

pentru ca nu ti-a venit ideea...
 

[•calinux]

Eu am incercat sa implementez... si n-am reusit. Am tratat si cazul cand n=1. Probabil imi scapa ceva mic... Nu stiu... Daca a mai avut cineva vreo problema similara si ma poate ajuta as fi recunoscator....      

[•filipb]

Eu am avut probleme la afisare   pt k nu puneam punctul la sfarsitul fiecarei linii...   In rest, dinamica e f usor de facut si nu apar cazuri speciale in sursa. Incearca si cu teste mici in care sa iti aleaga de fiecare data viteza normala, sau cu unele in care sa se aleaga mereu numai superviteza. Desi nu ar trebui sa ai probleme   Ce ar mai putea sa apara: consumul minim de combustibil s-ar putea sa nu se incadreze pe 32 de biti... Cam asta ar fi tot!

[•Marius]

Si eu am incercat sa implementez, dar nu am reusit   . Folosesc 64 de biti pentru numere si pun punctul la sfarsitul liniilor...    Ce sa fie ?

[•Adriana_S]

pai daca nu e de la afisare inseamna ca e de la dinamica. Poate ai busit implementarea, sau e chiar de la idee pe care ori ai inteles-o prost din postul lui bogdan ori ai gandit-o prost. E putin cam greu sa-si dea cineva seama ce ai gresit tu numai din ce ai zis....

[•tm_radu]

Cat va da pe:

Cod:

1
6
12543 7
2345 2
7347 4 
57629 5
100 3

mie imi da 21549. ii bine?

[•wefgef]

e bine 

[•tm_radu]

in cazu asta habar n-am ce-am gresit....

[•tm_radu]

mi-ati putea da macar un test (nu unul din cele oficiale) ca sa vad ce am gresit?

[u-92]

lasa tu un test (mai maricel) si iti spun rezultatul corect

[•tm_radu]

Pentru:

Cod:

3
12
12543 7
2345 2
60 3
3467 5
7347 4 
57629 5
100 3
24560 9
3232 6
1231 10
45325 8
4
100 2
101 4
102 6
5
10000 1
10000 2
10001 5
10001 3

va da:

Cod:

Consumul minim = 83446.
Consumul minim = 219.
Consumul minim = 11297.

? 

[•bogdan2412]

da... e bine..

[•tm_radu]

Ce naspa ca nu este decat un singur test  imi da bine pe toate testele facute de mana, dar totusi primesc WA...

[•bogdan2412]

Vezi daca programul tau nu crapa pentru N <= 1, daca folosesti int64 / long long peste tot pe unde trebuie, daca ai "." la sfarsitul fiecarui rand sau daca nu pui un enter in plus la sfarsitul fisierului...

[•tm_radu]

Pentru n = 1, trebuie afisat 0, nu?

[•filipb]

DA

[•Coty]

Cod:

    scanf("%ld", &T);
    while ( T-- )
    {
//      ................
        printf("Consumul minim = %lld.", solve());
        if ( T ) printf("\n");
    }

e cu punct la sfarsit, e long long, nu are un enter in plus... si imi dau toate destele facute de mana... ce are? 

[Later edit]
nu am zis, dar am facut cum a zis Bogdan, cu o matrice in care A[ i ][ j ] inseamna cat a mers cu viteza normala pana in bucata de drum i ( inclusiv ) atata timp cat a consumat j unitati de superviteza... si matricea e de 600 x 600 ... long long in matrice, long long rezultatul... cand fac minimul verifica pana la j 10 (care la a patra intra in long):

Cod:

    long long rez=MARE;
    for (j=0; j<10; ++j)
        if ( rez>(long long)(A[N][j]+j*j*j*j) ) rez=(long long)(A[N][j]+j*j*j*j);
    return rez;

sau daca nu pui un enter in plus la sfarsitul fisierului...

fisierul trebuie sa aiba un enter dupa ultimul punct? sau nu? adica te referi la < punct enter enter > sau la < punct enter >

[•tm_radu]

Probabil nu e de la afisare...verifica daca MARE este o constanta destul de mare, si daca initializezi cum trebuie matricea dupa fiecare test din fisierul de intrare. inca ceva....declara o constanta long long int sau chiar double in care tii rezultatul lui j^4...pentur ca s-ar putea sa devina destul de amre la un moment dat

[•svalentin]

..declara o constanta long long int sau chiar double in care tii rezultatul lui j^4...pentur ca s-ar putea sa devina destul de amre la un moment dat

Cod:

(long long)(A[N][j]+j*j*j*j)

... cred ca face deja calculele in long long

[•Coty]

Probabil nu e de la afisare...verifica daca MARE este o constanta destul de mare, si daca initializezi cum trebuie matricea dupa fiecare test din fisierul de intrare. inca ceva....declara o constanta long long int sau chiar double in care tii rezultatul lui j^4...pentur ca s-ar putea sa devina destul de amre la un moment dat

Cod:

 #define MARE 1073741824

mi se pare ca ala e 2^20, oricum, daca e mai mare parca face urat... da, calculez matricea A si rezultatul in long long. acum am modificat sursa un pic si functia solve() nu returneaza decat pozitia, valoarea o calculez inainte de afisare... nu ca ar fi o mare imbunatatire,,, intrebarea mare ar fi: evaluatorul tine cont de cate enteruri sunt la sfarsitul fisierului de iesire? ca daca nu, e de la valorile gresite pe care le returneaza programul...

si inca ceva: vi s-a intamplat sa rulati executabilul dupa compilare, sa primiti un raspuns aproximativ gresit ( pt 1 test nu era corect ) si sa dati run din rhide pe urma si sa va dea corect? si eventual stiti de la ce ar putea fi

[•svalentin]

ar putea fi de la faptul ca iti iese din memori pe undeva; cand rulezi din Rhide, Rhide mai tine niste chestii in memorie si tu cand iesi, poti sa iesi peste memoria lui Rhide; pe cand daca rulezi direct .exe, cand iesi din memorie poti intri peste altceva...
ruleza-l si in Linux sa vezi daca ai probleme..

si de ce ai long long rez daca il initializezi cu MARE care e doar 2^20? rez poate sa fie in cazul asta int.. sau fa MARE mai mare (ex 2^60)..
ex #define MARE 1e18 (asta e 10^18.. se aproprie de maximul long long..); dar vezi ca e double, insa il transforma bine in long long