Afişează mesaje
Pagini: [1]
1  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 042 Xor Max : Septembrie 16, 2008, 15:41:29
Tot incerc sa iau puncte la problema fara succes.. pana si brute force-ul ia WA asa ca poate am inteles gresit problema.
De exemplu pentru testul de mai jos am rulat brute-ul si o solutie de 100

11
21 98 77 35 90 11 51 3 58 54 74

BRUTE:
125 6 11

SOLUTIE 100 (submit #196825):
124 10 11

Atasez si brute-ul meu, poate ma lumineaza cineva.

Cod:
int N;
int A[maxn];

int main(void)
{
    int i, j;

#ifndef CACAMACA
    freopen ("xormax.in", "rt", stdin);
    freopen ("xormax.out", "wt", stdout);
#endif

    scanf ("%d", &N);

    for (i = 0; i < N; i++)
        scanf ("%d", A + i);

    int best_y = -1;
    int best_start = 0, best_end = -1;

    for (i = 0; i < N; i++) {
        int y = 0;
        for (j = i; j < N; j++) {
            y ^= A[j];

            if (y > best_y || (y == best_y && j < best_end) ||
                (y == best_y && j == best_end && i > best_start))
            {
                best_y = y;
                best_start = i;
                best_end = j;
            }

        }
    }

    printf ("%d %d %d\n", best_y, best_start + 1, best_end + 1);

    return 0;
}

editat de moderator: Foloseste tag-ul code pentru postat cod.
2  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 712 Albinuta : Septembrie 13, 2008, 17:58:53
Cred ca greseala e de la cum ai inteles articolul de pe wikipedia si nu de la cum consideri M(cmmmc sau produsul).
Dupa ce s-au intalnit cei doi pointeri ai gasit lungimea inceputului pana la ciclu + lungimea ciclului, resetezi contorul si trebuie sa-l mai parcurgi o data ca sa afli lungimea ciclului si apoi sa poti afla lungimea inceputului scazand din prima valoare.
Pagini: [1]
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines