Imprimă pagina - 051 Rell's Report

infoarena - concursuri, probleme, evaluator, articole => Arhiva Infoarena Monthly => Subiect creat de: Teodor Plop din Ianuarie 16, 2014, 22:08:48

Titlul: 051 Rell's Report
Scris de: Teodor Plop din Ianuarie 16, 2014, 22:08:48

Aici puteţi discuta despre problema Rell's Report (http://infoarena.ro/problema/rell).

Titlul: Răspuns: 051 Rell's Report
Scris de: Cobuz Andrei din Ianuarie 20, 2014, 22:44:41

Aceasta este functia recurenta la care m-am gandit pentru a rezolva problema:

Cod:

void rec(int x,int k1,int k2,int k3,int ts){
    if(!x){
        int ax=k1*a1+k2*a2+k3*a3;
        if(mn==ts){
            qti=min(qti,ax);
        }else if(mn>ts){
            mn=ts;
            qti=ax;
        }
        return;
    }

    rec(max(0,x-a1),t1,max(k2-1,0),max(k3-1,0),ts+1+k1);
    rec(max(0,x-a2),max(k1-1,0),t2,max(k3-1,0),ts+1+k2);
    rec(max(0,x-a3),max(k1-1,0),max(k2-1,0),t3,ts+1+k3);
    return;
}

Iar acesta este apelul ei

Cod:

rec(x,0,0,0,0)

.
qti si mn sunt variabile globale care retin timpul minim si suma:a1*k1+a2*k2+a3*k3.

Stiu ca aceasta abordare nu se incadreaza in limitele de timp si nici nu urmaresc asta. Ma intereseaza sa aflu unde am gresit, la formula recurenta, de nu imi este acceptat pe testele pe care imi intra in limita timp.

Multumesc mult pentru ajutor, oricui se indura!

Titlul: Răspuns: 051 Rell's Report
Scris de: George Marcus din Ianuarie 21, 2014, 00:10:47

Nu ai voie sa folosesti decat atacurile pentru care k = 0.

Titlul: Răspuns: 051 Rell's Report
Scris de: Cobuz Andrei din Ianuarie 21, 2014, 16:45:38

Citat din mesajul lui: George Marcus din Ianuarie 21, 2014, 00:10:47

Nu ai voie sa folosesti decat atacurile pentru care k = 0.

Multe multumiri :ok: