infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Octombrie 23, 2005, 21:48:20


Titlul: 122 Calatorie interplanetara
Scris de: ditzone din Octombrie 23, 2005, 21:48:20
Aici puteţi discuta despre problema Calatorie interplanetara (http://infoarena.ro/problema/calatorie).

Titlul: 122 Calatorie interplanetara
Scris de: Sara Nicolae Bogdan din Octombrie 24, 2005, 14:05:25
Dati-mi va rog  un hint cum se facea dinamica la problema asta ca nu mi-a iesit nici cum.

Titlul: 122 Calatorie interplanetara
Scris de: Bogdan-Cristian Tataroiu din Octombrie 24, 2005, 14:43:39
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

Titlul: 122 Calatorie interplanetara
Scris de: darlene din Octombrie 24, 2005, 14:55:42
aha!!..deci pana l urma era programare dinamica.....mie dc nu mi-o fi iesit??... :annoyed:

Titlul: 122 Calatorie interplanetara
Scris de: Adriana Sperlea din Octombrie 26, 2005, 15:15:23
pentru ca nu ti-a venit ideea...
 :D

Titlul: 122 Calatorie interplanetara
Scris de: Iorgulescu Calin din Octombrie 29, 2005, 21:44:06
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....  ](*,)  ](*,)  ](*,)

Titlul: 122 Calatorie interplanetara
Scris de: Filip Cristian Buruiana din Octombrie 30, 2005, 18:38:13
Eu am avut probleme la afisare  :oops: pt k nu puneam punctul la sfarsitul fiecarei linii...  :dontgetit: 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  :wink: 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!

Titlul: 122 Calatorie interplanetara
Scris de: Marius Stroe din Ianuarie 18, 2006, 01:00:53
Si eu am incercat sa implementez, dar nu am reusit  :-s . Folosesc 64 de biti pentru numere si pun punctul la sfarsitul liniilor...  :thumbdown:  Ce sa fie ?

Titlul: 122 Calatorie interplanetara
Scris de: Adriana Sperlea din Ianuarie 18, 2006, 13:56:47
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....

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iunie 11, 2006, 18:38:02
Cat va da pe:

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

mie imi da 21549. ii bine?

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Andrei Grigorean din Iunie 11, 2006, 20:13:25
e bine  :)

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iunie 11, 2006, 20:30:18
in cazu asta habar n-am ce-am gresit....

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iunie 13, 2006, 17:08:35
mi-ati putea da macar un test (nu unul din cele oficiale) ca sa vad ce am gresit?

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: u-92 din Iunie 13, 2006, 20:29:12
lasa tu un test (mai maricel) si iti spun rezultatul corect

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iulie 06, 2006, 17:03:57
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.
?  :-s

Titlul: Re: 122 Calatorie interplanetara
Scris de: Bogdan-Cristian Tataroiu din Iulie 06, 2006, 17:14:33
da... e bine..

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iulie 06, 2006, 17:52:21
Ce naspa ca nu este decat un singur test  :sad: imi da bine pe toate testele facute de mana, dar totusi primesc WA...

Titlul: Re: 122 Calatorie interplanetara
Scris de: Bogdan-Cristian Tataroiu din Iulie 06, 2006, 17:59:32
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...

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iulie 06, 2006, 18:12:02
Pentru n = 1, trebuie afisat 0, nu?

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Filip Cristian Buruiana din Iulie 06, 2006, 21:00:58
DA

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 09, 2006, 15:45:05
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;

Citat din mesajul lui: bogdan2412
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 > ???

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Toma Radu din Iulie 19, 2006, 17:16:18
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

Titlul: Re: Raspuns: 122 Calatorie interplanetara
Scris de: Valentin Stanciu din Iulie 19, 2006, 22:30:26
Citat din mesajul lui: tm_radu din Iulie 19, 2006, 17:16:18
..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
Citat din mesajul lui: Coty din Iulie 09, 2006, 15:45:05
Cod:
(long long)(A[N][j]+j*j*j*j)

... cred ca face deja calculele in long long

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 20, 2006, 07:24:22
Citat din mesajul lui: tm_radu din Iulie 19, 2006, 17:16:18
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 ???

Titlul: Re: 122 Calatorie interplanetara
Scris de: Valentin Stanciu din Iulie 20, 2006, 09:13:09
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 :P (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

Titlul: Re: 122 Calatorie interplanetara
Scris de: Bogdan-Cristian Tataroiu din Iulie 20, 2006, 09:23:01
Nu tine cont de cate enteruri sunt la sfarsit... Sorry pt ce am zis mai sus....

Matricea A trebuie sa fie long long si rezultatul trebuie sa fie long long....Gandeste-te la limite... daca ai Nk = 10^8 (k=1,N) si N = 50... de exemplu A[n][0] (dupa relatia de recurenta care am dat-o eu mai sus) o sa fie 50 * 10 ^ 8 si depaseste long long...
Constanta MARE e prea mica... Incearca ceva de genu
Cod:
const long long MARE = 1LL << 60;

[Later edit: Nu vazusem ca a postat deja svalentin]

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 20, 2006, 09:41:36
Citat din mesajul lui: svalentin din Iulie 20, 2006, 09:13:09
ruleza-l si in Linux sa vezi daca ai probleme..
de la ONI incoace numai in Linux lucrez ca sa scap de problemele astea cu "incalecatul memoriei"... nu m-am exprimat bine mai sus: mai intai rulez executabilul (de linux :D ) si imi da gresit, intru in rhide si da bine... acum nu mai sunt probleme ( cred... )
Citat din mesajul lui: bogdan2412 din Iulie 20, 2006, 09:23:01
Matricea A trebuie sa fie long long si rezultatul trebuie sa fie long long....Gandeste-te la limite... daca ai Nk = 10^8 (k=1,N) si N = 50... de exemplu A[n][0] (dupa relatia de recurenta care am dat-o eu mai sus) o sa fie 50 * 10 ^ 8 si depaseste long long...
Constanta MARE e prea mica... Incearca ceva de genu
Cod:
const long long MARE = 1LL << 60;

well, am A matrice long long, am facut cum ai zis tu pe MARE ( apropo, 1LL in ce baza e, ce semnifica ??? ) tot WA primesc... cred ca e de la recurenta, oi fi implementat-o prost, dar nu gasesc unde... o postez?

Titlul: Re: 122 Calatorie interplanetara
Scris de: Valentin Stanciu din Iulie 20, 2006, 09:44:56
1LL este 1, doar ca ii spune ca este long long
x = 1000000000000000000 nu poti sa faci ca este > int.. trebuie sa ii pui LL la sfarsit ca sa inteleaga ca este o constanta long long

deci ce a scris bogdan 1 << 60, adica 2^60 (cred LL ala te incurca, dar intelegi de ce trebuie..)

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 20, 2006, 13:19:09
well, acu inteleg si de ce nu mergea sa pun 2^60 direct (incercasem asta... si nu voia) se vede ca nu stiu C cum trebuie  :? nu?

Titlul: Re: 122 Calatorie interplanetara
Scris de: Valentin Stanciu din Iulie 20, 2006, 13:20:13
toate trebuie invatate candva, de undeva..

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din Iulie 21, 2006, 15:24:51
need help (de cateva zile incerc dinamica, da nu imi iese )  :oops:  plz pune careva intreaga matricea b calculata  ( matricea care retine drum minim pan la planeta i cu j superviteza) pentru testu din problema (exemplu 2) 

noh ms...deci nu pune nime  :sad:

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 22, 2006, 07:31:38
Cod:
       0     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE 
   10000        0     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE 
   13547     3547    10000        0     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE 
   50329    40329    46782    36782     MARE     MARE     MARE    13547     3547    10000        0     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE 
   52507    42507    48960    38960    50329    40329    46782    15725     5725    12178     2178    13547     3547    10000        0     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE 
  119935   109935   116388   106388   117757   107757   114210    83153    73153    52507    42507    48960    38960    50329    40329    46782    15725     5725    12178     2178    13547     3547    10000        0     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE     MARE

unde MARE e infinit (2^60) ... se poate sa nu fie tocmai bine, atata timp cat iau 0, dar asa arata la mine... si am printat toata matricea, asa cum o calculez, de la i = 0..n, j=0..MAX (MAX=100 parca)

[later edit] btw, postez si recurenta, poate e undeva o buba?

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din Iulie 23, 2006, 20:56:44
nuh, o sa incerc sa o rezolv singur, daca nu o sa reusesc o sa mai intreb pe forum (10X)

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 24, 2006, 08:25:54
:D stai calm, intrebam de recurenta pentru ca nici mie nu imi da bine (nu iau 100) desi matricea aia poate fi bine atata timp cat da corect... si am mai si verificat-o

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din Iulie 25, 2006, 12:35:57
cat va da pe:

1
8
10001 7
2345 2
517 3
907 4
2314 1
32143 4
5666 3

 :-k

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Filip Cristian Buruiana din Iulie 25, 2006, 12:41:21
Consumul minim = 17866.

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din Iulie 25, 2006, 13:17:59
noh   :x imi iese pe toate exemplele care le dau ... da iau WA  :angry:

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 25, 2006, 13:29:10
si mie la fel... de la ce sa fie??? :(  :eyebrow:

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din Iulie 26, 2006, 12:32:30
mai pun un test (chiar nu imi dau seama ce gresesc ](*,)) cat va da pe :

1
6
20006 2
3334 3
2124 2
32349 1
4329 3

mie imi da : Consumul minim = 7430. ... voua ?  :-k

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din Iulie 26, 2006, 15:30:28
Consumul minim = 6754.

Acum sa si verificam...

Titlul: Re: 122 Calatorie interplanetara
Scris de: Bogdan-Cristian Tataroiu din Iulie 26, 2006, 18:55:39
"Consumul minim = 6754." e bine

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din Iulie 26, 2006, 19:13:39
ah da atat da ... uitasem sa initializez o chestie, k lasam mai multe ex de-o data sa mearga ... am corectat da tot 0 pcte

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din August 02, 2006, 17:56:32
un ultim test ... mai mare
Cod:
1
38
12543 7
2345 2
60 3
3467 5
7347 4 
57629 5
100 3
24560 9
3232 6
1231 10
45325 8
12543 7
2345 2
60 3
3467 5
7347 4 
57629 5
100 3
24560 9
3232 6
1231 10
45325 8
12543 7
2345 2
60 3
3467 5
7347 4 
57629 5
100 3
24560 9
3232 6
1231 10
45325 8
10000000 1
10000000 2
1000001 5
1000001 3
anybody??

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: andreit1 din August 02, 2006, 20:02:39
Consumul minim = 17866.
Consumul minim = 6754.
Consumul minim = 481424.
481424 e pentru ultimu test. Solutia mea are vreo 30 de linii in pascal. Probabil a ta cam la fel... deci uite-te mai atent peste cod( ca e foarte scurt) inainte sa bagi teste si sa faci debug.

Titlul: Re: 122 Calatorie interplanetara
Scris de: Sima Mihai Cotizo -vechi din August 02, 2006, 21:27:35
si daca-mi da bine, de la ce sa fie de iau mereu 0?  :-'

Titlul: Raspuns: 122 Calatorie interplanetara
Scris de: Bondane Cosmin din August 02, 2006, 22:21:42
dah ... deci am gresit uneva k imi da alt rezultat ... da habar nu am ce am gresit  #-o  :oops:

am reparat ... refacut dinamica imi iese bine da tot 0pcte ... ciudata problema

Titlul: De ce nu intra in int ?
Scris de: Andrei-Bogdan Antonescu din Iulie 22, 2008, 15:01:44
Matricea pentru dinamica
Cod:
(C[i][j] = cat timp a mers normal ca sa ajunga la planeta i cu j timp de super viteza )
ar trebui sa intre in int nu ?  :-k .

 Ca sunt maxim 50 de planete  *  1<<8 adica vreo 5 miliarde pe testul maxim.
 Eu am luat 0 daca am declarat matricea in int .  :?

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Cezar Mocan din Iulie 22, 2008, 15:15:26
Si dupa cunostintele tale avansate de matematica 5 miliarde e mai mic decat 2 miliarde, ca sa intre in int?  :)

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Andrei-Bogdan Antonescu din Iulie 22, 2008, 18:10:26
a da ai dreptate  :) , aveam impresia ca intra in int pana la 9 miliarde 

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Simionescu Andrei din August 19, 2008, 17:37:45
Cod:
        0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
     1000       BIG       BIG         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
     6000       BIG      1000      5000       BIG         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
    14000       BIG      9000     13000      6000      8000      1000      5000       BIG         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
Consumul minim = 2296.
        0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
    10000         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
    13547      3547     10000         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
    50329     40329     46782     36782       BIG       BIG       BIG     13547      3547     10000         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
    52507     42507     48960     38960     50329     40329     46782     15725      5725     12178      2178     13547      3547     10000         0       BIG       BIG       BIG       BIG       BIG       BIG       BIG 
   119935    109935    116388    106388    117757    107757    114210     83153     73153     52507     42507     48960     38960     50329     40329     46782     15725      5725     12178      2178     13547      3547 
Consumul minim = 52507.
si recurenta:
Cod:
    for(i=1;i<n;++i) a[i][0] += a[i-1][0] + nk[i];
    for(i=1;i<n;++i)
        for(j=0;j<501;++j)
            {
            aux = (a[i-1][j]==big)?big:(unsigned long long)(a[i-1][j] + nk[i]);
            if(j-hk[i] < 0)
                a[i][j] = aux;
            else
                aux2 = (a[i-1][j-hk[i]]==big)?big:a[i-1][j-hk[i]],
                a[i][j] = minim(aux,aux2);
            }
    for(i=0,min=big; i<501; ++i)
        {
        aux = (unsigned long long)(a[n-1][i] +  i*i*i*i);
        if(aux<min)
            min = aux;
        }
mi-au mers toate testele pe care le-am rulat, output-ul este corect dpdv sintactic
care sa fie problema?

ps:
Cod:
#define big 1LL<<60
typedef unsigned long long ull;
inline ull minim(ull x, ull y){if(x>y) return y;return x;}

int n,t,nk[64],hk[64];
unsigned long long a[51][501],min,aux,aux2;
int i,j;

pps: intreb pt ca e o problema care au avut-o mai multi, unii si recent, si au rezolvat-o cumva

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Dragos Oprica din Decembrie 18, 2009, 14:48:08
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 <=  ](*,)

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Dragos din Martie 01, 2010, 17:33:23
Salut!
Trebuie numere mari la problema aceasta
?
:(

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Andrei Grigorean din Martie 01, 2010, 17:47:12
Nu, intra pe long long.

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Dragos din Martie 02, 2010, 00:13:54
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.

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Adrian Ionescu din Mai 14, 2010, 17:01:19
 ](*,)

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

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Simoiu Robert din Mai 14, 2010, 17:24:25
Imi poti da afisarea ?

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Adrian Ionescu din Mai 14, 2010, 18:04:06
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)

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Mircea Dima din Mai 14, 2010, 18:08:35
Citat din mesajul lui: Adrian Ionescu din Mai 14, 2010, 18:04:06
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

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Adrian Ionescu din Mai 14, 2010, 18:10:19
Citat din mesajul lui: Mircea Dima din Mai 14, 2010, 18:08:35
Citat din mesajul lui: Adrian Ionescu din Mai 14, 2010, 18:04:06
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..

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Mircea Dima din Mai 14, 2010, 18:15:11
Solutia ta e Greedy, nu? Ca am vazut ca iei niste optime locale pe acolo. Deci foarte probabil nu e corecta...

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Adrian Ionescu din Mai 14, 2010, 18:22:47
Citat din mesajul lui: Mircea Dima din Mai 14, 2010, 18:15:11
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..

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Vasea Mordatii din Mai 19, 2010, 11:06:45
Recursive brute-force cu memorizarea a primit TL :-(

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Gabriel Bitis din Mai 19, 2010, 12:15:16
Citeste tot topicul si incearca altceva decat "recursive brute-force cu memorizare".

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Andrei Dinu din Iunie 28, 2012, 13:00:01
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!  :)

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Andrei Dinu din Iunie 28, 2012, 21:19:06
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! :)


Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Vlad Negura din Ianuarie 08, 2013, 23:16:30
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

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Cristian Bodnar din Ianuarie 05, 2014, 18:10:01
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.

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Eftime Andrei Horatiu din Februarie 21, 2014, 15:48:41
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.

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Popescu George din Februarie 25, 2015, 18:57:23
Sa aveti grija sa puneti " . " dupa numar !!

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Vlad Negura din August 17, 2015, 01:54:53
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.

Titlul: Răspuns: 122 Calatorie interplanetara
Scris de: Adrian Buzea din Februarie 20, 2016, 12:08:38
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.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines