infoarena

Aici puteţi discuta despre problema Heroes of Might & Magic (http://infoarena.ro/problema/homm).

sigur e bun exemplul? mie imi da 104 (am verificat sursa de 10 de ori)

Sigur e bun. Nu am verificat cu back... dar trebuie sa fie bun.

Eu la problema am facut asa:
 H:array[1..20,0..101,0..101]of longint;

 H[p,i,j]:=H[p-1,i-1,j]+H[p-1,i+1,j]+H[p-1,i,j-1]+H[p-1,i,j+1];
 rez:=H[1,fi,fj] +H[2,fi,fj]+...H[k,fi,fj];
Si iau doar 30 de puncte :(
  Am incercat varianta din articol(probabil ca nu am inteles bine)
  H[p,i,j]:=H[p-1,i-1,j]+H[p-1,i+1,j]+H[p-1,i,j-1]+H[p-1,i,j+1]+H[p-1,i,j];
  rez:=H[p,fi,fj];
  Si da niste valori de te sperii....
  Ce am abordat gresit?

Prima abordare este corecta (am corectat si articolul) dar ai grija sa calculezi H[p,i,j] doar pentru pozitiile (i, j) pentru care este 0 in matrice.

Pai mai intai verific daca Map[i,j]=0 daca da insumez vecinii.
Nu conteaza daca un vecin are obstacol. Dar totusi 30 p :(

Am luat 90 p acum
am pus in loc de longint- int64...
TEST 7   ...[0.02s]...   Incorect sau fisier iesire lipsa
Totusi int64 cred ca ajunge  :shock: . Ce altceva poate fi?

Ciudat caci eu am luat 100p cu int (echivalent longint in pascal) , plus ca parca se garanta in enunt ca numarul nu depaseste 2.000.000.000.
Cred ca mai degraba eroare e de la matricea "map" care e declarata byte.. incearca cu longint.

Dobre vezi ca ai uitat un caz: atunci cand punctul initial este acelasi cu punctul final.

Mersi pt. obesrvatie, am facut asa dar se pare ca nu asta era problema, am facut map de tip longint si tot asa :( . Chiar ma calca pe nervi!!!  :x

Domino:  chiar daca se garanta, pana la raspunsul final mai sunt puncte in care sunt mult mai multe drumuri...

Lucreaza modulo 1000001 daca nu vrei sa ai probleme cu tipul de data folosit... astfel poti folosi linistit longint.

NU cred ca ii problema cu citirea. Doar mi-au mers 9 teste pe byte. NU cred ca ii testul 7 mai cu mot si depaseste longint!!!  :-s

La testul 7 punctul initial este acelasi cu punctul final( am trimis sursa in 2 variante diferite si mi-am dat seama)... deci adaoga 1 la rezultat in cazul asta. Alt motiv nu vad pentru care iei 9 teste din 10.

Esti tare ma, asta era problema ;) , mersi mult ,totusi de ce ii +1?

..pai e drum de lungime 0.
0 < K

:lol:  chiar asa este, nu m-am gandit la situatia asta, mersi pentru lamurire  :wink:

un link cu explicatiile oficiale mi-ar fii de mare ajutor....am luat cu back 20 si am in Ginfo solutia oficiala si am inteles insa:( ...dar zicea domino ca a schimbat ceva in articol si vreau sa vad solutia recorectata........si nu o gasesc pe www.ginfo.ro(ori sunt orb:(:(: ..ori sunt prea obosit sa o observ)...help pls F1!!

http://info.devnet.ro/articole.php?page=art&art=62

ciudat ... am facut un back in plan,bineinteles k nu ma gandesc la 100 de pcte cu asha ceva, dar nush din cele 6 in care imi intra in timp iau numa 3 ... help me cu ceva teste plz

Nu cred ca o sa iti dea nimeni teste ca sa vezi de ce nu iti merge backu. Mai bine fa solutia buna care are doar cateva zeci de linii si ata. Si dupa asta daca insisti sa inveti back in plan genereaza teste singur si verifica-le cu dinamica. Asa o sa inveti mai multe dupa parerea mea.

a mers pana la urma cu matricea tridimensionala de 100 \:D/

    Nustiu de ce pe exemplul din problema imi da 32.
 Fac cu 3 foruri . Initializez H[x,y,0] cu 1 , apoi intr-un for de la 0 la k parcurg toata matricea si daca m[i,j] este 0 , adun H[i,j,k1] la H[vecini,k1+1].(unde H[i,j,k1] reprezinta nr de moduri de a ajunge de pe m[x,y] pe m[i,j] in k1 pasi )
 E gresit ? Vad ca scoate timpul de 0,01 sec pt fiecare test
 

Last edit : Gata , s-a rezolvat .

Forul ala de k trebuie sa inceapa de la 1. ( cel putin eu asa am facut )

[Later Edit] A iesit ?

Pt
va da 2580? Ms anticipat

Mie imi da 276.

Of...si ai luat 100?...am facut sursa de 100 in sfarsit si mie imi da 1140

da 0....nu poti ajunge in celula (3,3)  - are valoarea 1, deci e inaccesibila

De ce da rezultat gresit (80 de puncte) daca intializez direct vecinii nodului de start (calculez direct h[1][vecin x][vecin y]), dar daca intializez h[0][xi][yi] merge perfect (chiar daca se fac EXACT ACEIASI pasi).

Imi poate recomanda cineva vri-un articol care m-ar ajuta sa rezolv problema data ?

numerele alea din matrice, cele diferite de zero, cat de mari/mici pot fi ("intregii" din cerinta inseamna ca sunt int-uri?). si inca o intrebare, conteaza la ceva ce valoare are o casuta, atata timp cat ea e diferita de 0? daca nu, de ce sa nu spunem pur si simplu ca e o matrice cu 0 si 1?

@ blue_phoenix :Numerele din matrice se incadreaza in limita int-ului.Si referitor la a doua intrebare nu conteaza deloc ce valoare e atat timp cat ea e diferita de 0.Enuntul este dat in asa fel incat se incearca,ca sa spun asa, "mascarea" dinamicii.

Imi poate spune si mie cineva ce initializari ar trebui facute la inceput ca nu ma prind.   ](*,)

Done.

Am luat pe problema 50 de puncte cu o memoizare...
Am WA si TLE ... testul 7 e corect(cel in care x1,y1 coincid cu x2, y2).

Am procedat astfel: Am apelat memo(x2,y2,k) si am mers recursiv in memo(xnou,ynou,k-1), pana dadeam de starea x1,y1,k=0.

xnou,ynou sunt toti vecinii si am verificat sa nu ies din matrice, iar vecinul respectiv sa fie 0. Nu inteleg de ce am WA...
TLE s-ar putea sa fie din cauza ca intru in ciclu infinit in unele cazuri, insa nu imi dau seama de ce. Am verificat mai multe cazuri.
Imi puteti spune ce cazuri scap?

Acolo unde verifici daca esti matrice, cred ca ai gresit ordinea lui x si y. x e linia si y e coloana.

Cand am citit, am citit N si M, N = nr linii, M = nr coloane, deci nu cred ca de acolo e problema.

EDIT: Am rezolvat-o... nu calculam cum trebuie toate starile, pentru ca apelam Memoizarea o singura data... :D

Si mie imi da 32 pe exemplul dat. De la ce ar putea fi?
http://infoarena.ro/job_detail/882662

In enunt zice sa calculezi in cate moduri poti ajunge in (x2, y2) cu cel mult K mutari, dar tu calculezi in cate moduri ajungi cu exact K mutari.

Asa e. Acum am rezolvat. Multumesc!

Unde se gaseste articolul cu explicatiile necesare?

http://www.infoarena.ro/agora-finala/solutii

btw, e super jmecher jocul :)
mersi! nu stiam de el

Cat va da pt testul :
5 5 10
0 0 0 0 0
0 2 0 3 0
0 0 1 0 0
0 2 0 0 0
0 0 0 0 0
5 5 5 5
 Ms anticipat !

mie imi da

Si mie tot 4505 imi da.

Nu poate cineva sa ma ajute?Fac rezolvarea exact ca pe articol, dar nu merge
Cod:
#include <fstream>
using namespace std;
ifstream f("homm.in");
ofstream g("homm.out");
long long H[30][100][100],i,j,N,M,K,stx,sty,fnx,fny,rez,Ma[100][100],p;
int main()
{
    f>>N>>M>>K;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            f>>Ma[j];
        }
    }
    f>>stx>>sty>>fnx>>fny;
    H[0][stx][sty]=1;
    for(p=1;p<=K;p++)
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                if(!Ma[j])
                    H[p][j]=H[p-1][i-1][j]+H[p-1][j+1]+H[p-1][i+1][j]+H[p-1][j-1];
    for(i=0;i<=K;i++)
        rez+=H[fnx][fny];
    g<<rez;
    return 0;
}
Multumesc anticipat!