122 Calatorie interplanetara

[•DraStiK]

Ma ajuta cineva si pe mine?

Am facut cu dinamica best[ i ][ j ] - costul minim de combustibil normal pentru a ajunge la planeta i cu exact j unitati de viteza luminii.

Am incercat toate testele de pe forum, si imi dau corect. Am tratat si cazul in care n=1. Any idea?

LE: Nevermind. Am pus un < in loc de <= 

[•APOCALYPTO]

Salut!
Trebuie numere mari la problema aceasta
?

[•wefgef]

Nu, intra pe long long.

[•APOCALYPTO]

Si mie imi ies toate testele( in afara de cel din evaluator), am pus si punct, si enter, daca n<=1 afisez 0 cu toate astea iau 0.
Mai exista ceva special ce trebuie stiut.
Eu am folosit o recurenta proprie care mai tarziu am observat ca este recomandata si in solutiile de la Happy coding.

[•spider853]

 

Puteti sami spuneti daca la mine e o gresala de afisare, sau raspunsul e gresit?... straniu ca nici primul test nu merge... 
toate testele pe care le-am incercat offline merg...
am facut si un generator de teste... tot merge...

[•SpiderMan]

Imi poti da afisarea ?

[•spider853]

iata mai bine sursa...

http://pastebin.com/sgufKUFE

P.S. nu stiu daca e permis sa postez cod pe acest forum... FAQ-ul nu exista.. (pagina inexistenta)

[•blasterz]

iata mai bine sursa...

http://pastebin.com/sgufKUFE

P.S. nu stiu daca e permis sa postez cod pe acest forum... FAQ-ul nu exista.. (pagina inexistenta)

Tu folosesti unsigned long in loc de long long.

long = int pe g++


Hmmm... tu nu rezolvi prin programare dinamica... nu stiu ce sa zic ... cred ca e gresita solutia ta

[•spider853]

iata mai bine sursa...

http://pastebin.com/sgufKUFE

P.S. nu stiu daca e permis sa postez cod pe acest forum... FAQ-ul nu exista.. (pagina inexistenta)

Tu folosesti unsigned long in loc de long long.

long = int pe g++


Hmmm... to nu rezolvi prin programare dinamica... nu stiu ce sa zic ... cred ca e gresita solutia ta

am incercat si cu long long... nimic..

incearca sa-i dai niste teste.. si sa controlez outputul cu alt algoritm... l-am comparat cu un brutforce... si dau aceleash rezultate

brutforce-ul aici nu-l primeste deoarece e TimeLimit..

[•blasterz]

Solutia ta e Greedy, nu? Ca am vazut ca iei niste optime locale pe acolo. Deci foarte probabil nu e corecta...

[•spider853]

Solutia ta e Greedy, nu? Ca am vazut ca iei niste optime locale pe acolo. Deci foarte probabil nu e corecta...

da e posibil sa primesc un exemplu de tip Test 1 diferit de el la care algoritmul meu ar genera raspuns gresit?

Eu sortez dupa raportu cel mai mare (N/K) si apoi apoi incerc sa substitui viteza cu superviteza pina raspunsul este mai mare decit ultimul raspuns..

[•ZALUPA]

Recursive brute-force cu memorizarea a primit TL

[•gabitzish1]

Citeste tot topicul si incearca altceva decat "recursive brute-force cu memorizare".

[•informatician28]

Am facut o dinamica la problema asta. Totul pare ca merge bine. Am dat teste, si cele de pe acest post si toate dau corect.
Totusi, sigur buseste undeva sursa mea. Daca ar vrea cineva sa ma ajute, i-as putea trimite sursa, as fi recunoscator.

Multumesc! 

[•informatician28]

Am rezolvat problema. Multumesc oricum!

***Pentru cei care au probleme in a obtine 100 p, va dau aici un test, mic, sa va verificati. Daca nici asa nu va dati seama unde gresiti, lasati-mi un mesaj ***

3
2
736 8
3
943 0
470 6
1

Raspuns:  Consumul minim = 736.
              Consumul minim = 470.
              Consumul minim = 0.

Aveti totodata grija si la afisare, trebuie sa fie long long. Puteti face ceva de genul : long long rezultat (long long ind) { ...return rezultat;}
Bafta!

[•Opportunity]

primesc corect pe toate testele din topic dar oricum iau 0pt

1
10
14322 1
544355 10
888 9
12311 9
6432533 2
4553 5
3421 1
1 10
999999 9

Consumul minim = 229977. ??

Need help.
http://infoarena.ro/job_detail/850806?action=view-source
daca poate cineva va rog sa va uitati la source

[•crisbodnar]

Mie imi mergea pe toate exemplele si luam 0 pct. Problema a fost ca nu am ales un numar bun pentru infinit-ul cu care initializam matricea. Am pus 625e10 si a functionat. Nu de alta da mi-a facut ceva nervi problema asta si poate mai ajuta pe cineva cu aceeasi problema.

[•dr_personality]

Vlad Negura: raspunsul la testul ala chiar e 229977, dar pentru n = 0, mi se pare ca nu-ti da consumul minim = 0., cat ar trebui. Poate gresesc,dar merita verificat.

[•gapdan]

Sa aveti grija sa puneti " . " dupa numar !!

[•Opportunity]

Ei bine m-am reintors la problema. Am rescriso de data asta in c++. am adaugat cazul cind n=0, si am initializat tablout cu 625e10 si tot nu merge. WTF
source: https://ideone.com/Wh3n0l
Unica problema care imi ia asa mult timp si efort.

Cine ma poate ajuta? Pun o bere.

[•krityx]

Si mie imi da corect pe toate testele din thread insa iau 0 pcte.
Am verificat afisarea, constanta de maxim si tot ce s-a mai zis pe aici.