infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Serban Andrei Stan din Martie 16, 2012, 23:21:30

Titlul: 1250 Markon
Scris de: Serban Andrei Stan din Martie 16, 2012, 23:21:30

Aici puteti discuta despre problema Markon (http://infoarena.ro/problema/markon).

Titlul: Răspuns: 1250 Markon
Scris de: Geman Dorin Andrei din Aprilie 22, 2016, 22:32:54

Ma puteti ajuta cu un hint, va rog? Nu pot sa-mi dau seama de ce nu trec de 20p.. ](*,)
Merci anticipat! :ok:
http://www.infoarena.ro/job_detail/1693388?action=view-source

Titlul: Răspuns: 1250 Markon
Scris de: George Marcus din Aprilie 23, 2016, 09:54:00

Ce imi sare imediat in ochi e ca apelezi decreaseDegree de 2 ori pentru nodul initial. Apoi, cand ajungi la un nod, chiar daca nu indeplineste proprietatea 2, s-ar putea ca dupa ce treci de el sa o indeplineasca.

Titlul: Răspuns: 1250 Markon
Scris de: Geman Dorin Andrei din Aprilie 23, 2016, 13:13:42

Am inteles, merci mult! :D

Titlul: Răspuns: 1250 Markon
Scris de: Roman Tudor din Septembrie 26, 2016, 11:46:06

Cum pot scăpa de TLE?

Cod:

    NR = 1;
    sol[NR] = X;
    seen[X] = 1;
    for (w=1; w<=N*N*N*N; w++)
        for (i=1; i<=N; i++)
            if (!seen[i])
            {
                cnt1 = 0;
                AA = i;
                for (j=1; j<=A[AA][0]; j++)
                {
                    BB = A[AA][j];
                    if (seen[BB] == 1)
                    {
                        if (code[BB] == 0)
                            cnt1 = 1;
                        else
                        {
                            cnt2 = 0;
                            for (k=1; k<=A[AA][0]; k++)
                                if (seen[A[AA][k]] == 0)
                                    cnt2++;
                            if (code[BB] > cnt2)
                                cnt1 = 1;
                        }
                    }
                }
                if (cnt1 == 1)
                {
                    NR++;
                    sol[NR] = AA;
                    seen[AA] = 1;
                }
            }

Titlul: Răspuns: 1250 Markon
Scris de: George Marcus din Octombrie 02, 2016, 12:52:23

Nu e buna complexitatea. Verifica solutia oficiala.