OJI 2002, a IX-a, Solutii

[•truenight]

Salut, stie cineva unde as putea gasi solutiile oficiale pentru problemele de a IX-a de la OJI 2002? Am gasit pentru prima, poartas pe .campion, insa pentru a doua, mouse, nu am gasit nicaieri. Am cautat si pe olimpiada.info, dar acolo nu sunt decat subiectele si testele, iar testele pentru a doua problema mi se pare ca nu includ si ok-ul.

Daca, totusi, nu se gaseste nicaieri, se poate uita cineva peste sursa de mai jos si sa imi spuna daca ar intra in timpul de 1s? PDF cu problema aici. Multumesc anticipat!

Cod:

#include <stdio.h>

#define N 100 + 1
#define IN "mouse.in"
#define OUT "mouse.out"

int main(void) {

    int cutie[N][N], poz[N][N], m, n, i, j, k,
        hrana = 0, cam = 0, max, sus, jos, stanga, dreapta;

    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);

    scanf("%d %d", &m, &n);

    for(i = 1; i <= m; ++i)
        for(j = 1; j <= n; ++j)
            scanf("%d", &cutie[i][j]);

    i = 1;
    j = 1;
    k = 1;
    while(!(i == m && j == n)) {

        hrana += cutie[i][j];
        cutie[i][j] = 0;
        poz[i][j] = k++;

        sus = i > 1 ? cutie[i - 1][j] : 0;
        jos = i < m ? cutie[i + 1][j] : 0;
        stanga = j > 1 ? cutie[i][j - 1] : 0;
        dreapta = j < n ? cutie[i][j + 1] : 0;

        max = sus;
        if(jos > max)
            max = jos;
        if(stanga > max)
            max = stanga;
        if(dreapta > max)
            max = dreapta;

        if(max == sus)
            --i;
        else if(max == jos)
            ++i;
        else if(max == stanga)
            --j;
        else if(max == dreapta)
            ++j;

        ++cam;
    }
    hrana += cutie[i][j];
    cutie[i][j] = 0;
    poz[i][j] = k;
    ++cam;

    printf("%d %d\n", cam, hrana);

    for(i = 1; i <= cam; ++i)
        for(j = 1; j <= m; ++j)
            for(k = 1; k <= n; ++k)
                if(poz[j][k] == i)
                    printf("%d %d\n", j, k);

    return 0;
}

[•mrares]

Poti folosi codeblocks sa vezi in cat timp iti ruleaza si dai pe un test random ... fisierul .in continand doar n, m si o matrice n-ar fi mare chestie.

Mai erau o functie/ sau functii sa iti afiseze si timpul de executie, dar nu le-am folosit niciodata, doar le-am vazut prin alte surse ... poate aici gasesti http://www.cplusplus.com/forum/beginner/1769/

Iar codul sursa ... din ce m-am uitat pe el nu stiu daca da mereu solutia cea mai buna ... asta ai verificat ? Intra sigur in 1 s oricum ... din ce vad faci doar n*m maxim (acuma nush cat e n si m ... )

[•truenight]

Da, am folosit time pe Unix (Mac) si intra, dar ma gandeam la un test maxim, de 100x100 (in problema scrie ca cea mai mare valoare din fisier e 100), si parca n-as sta sa fac unul, desi ar fi o idee buna sa invat sa fac asa ceva. In plus, voiam sa si verific solutia. M-am gandit ca ar putea fi o varianta in care sa nu dea ca lumea, dar cand am incercat un contraexemplu nu m-am lamurit daca da gresit

[•mrares]

Faci un backtracking. pe 8 directii ( parca asa cere ), iti faci vectorii aia si te duci pe fiecare drum posibil si.. la sfarsit afisezi doar maximul ala sau cat iti cere si cam asa te verifici. ( reconstituirea drumului nu cred ca fi o problema ... daca a aflat bine maximul ... da-l incolo de drum )

iar pentru teste dai pur si simplu ... random. pui si tu valori mai mici in matrice intre 1 si 10 nah.. vezi tu ...

oricum backtrackingul asta merge repede implementat..

[•truenight]

Pai... stai ca ar fi mai multe probleme aici. In primul rand, backtracking la a IX-a? In al doilea rand, nu poate trece dintr-o camera intr-alta decat daca cele doua camere au un perete comun. Opt directii inseamna un colt comun. In al treilea rand, problema-ti cere sa scrii drumul dupa ce afisezi maximul. E ceva ce-mi scapa?

[•mrares]

of of ... faza cu backtrackingul era doar de verificare a rezultatului. din moment ce tu nu ai teste oficiale / sau nu e pe infoarena/campion cum vrei sa te verifici ?

4 directii... nu am citit problema in amanunte... e o problema clasica... in fine. Daca intrebi de backtracking la a IX-a ... banuiesc ca nu stii recursivitate deci vorbesc singur T_T

ideea era ... sa iti faci 2 vectori de deplasare, dx si dy cu valorile -1, 0, 1, 0 si 0, 1, 0, -1 si sa apelezi backtrackingul dupa pozitia i si j... in el faceai un for de la 0 la 4 pentru deplasare... si foloseai inca o matrice uz[j] = 1 daca a mai fost pe acolo sau nu... din ce-am citit parca iti cere din (1, 1) in (n, m) sa ajungi... si de fiecare data cand atingi n, m verifici daca e mai mare ca maximul curent...

nah si daca vrei si drumul... de fiecare data cand gasesti un maxim nou, faci reconstituirea recursiv... ai putea de fapt in loc sa folosesti uz[j] = 1 sau 0 sa pui chiar o valoare care tot creste pana ajunge in (n, m)... daca esti in i, j si te duci la dreapta, in uz[j+1] = uz[j] + 1; si pe baza asta faci recursiv... din (n, m) cauti cu unu mai mic... de acolo iar cu unu mai mic si tot asa


....

am uitat de italic .. ma rog cred ca se intelege

[•SpiderMan]

Poti sa-ti iei testele si sa te corectezi singur ( Sectiunea Downloads, Oji 2002 ) .