122 Calatorie interplanetara

[•bogdan2412]

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]

[•Coty]

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 ) si imi da gresit, intru in rhide si da bine... acum nu mai sunt probleme ( cred... )

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?

[•svalentin]

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..)

[•Coty]

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?

[•svalentin]

toate trebuie invatate candva, de undeva..

[•cos_min]

need help (de cateva zile incerc dinamica, da nu imi iese )    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 

[•Coty]

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?

[•cos_min]

nuh, o sa incerc sa o rezolv singur, daca nu o sa reusesc o sa mai intreb pe forum (10X)

[•Coty]

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

[•cos_min]

cat va da pe:

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

 

[•filipb]

Consumul minim = 17866.

[•cos_min]

noh    imi iese pe toate exemplele care le dau ... da iau WA 

[•Coty]

si mie la fel... de la ce sa fie???  

[•cos_min]

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 ? 

[•Coty]

Consumul minim = 6754.

Acum sa si verificam...

[•bogdan2412]

"Consumul minim = 6754." e bine

[•cos_min]

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

[•cos_min]

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??

[andreit1]

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.

[•Coty]

si daca-mi da bine, de la ce sa fie de iau mereu 0? 

[•cos_min]

dah ... deci am gresit uneva k imi da alt rezultat ... da habar nu am ce am gresit   

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

[•andrei-alpha]

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 ?  .

 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 . 

[•CezarMocan]

Si dupa cunostintele tale avansate de matematica 5 miliarde e mai mic decat 2 miliarde, ca sa intre in int? 

[•andrei-alpha]

a da ai dreptate  , aveam impresia ca intra in int pana la 9 miliarde 

[•mordred]

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