971 Drum3

[•pauldb]

Aici puteti discuta despre problema Drum3.

[•stocarul]

În soluția problemei s-a strecurat o mică greșeală.
Acolo apre că valorile No și Nv sunt calculate:

Cod:

No = K / 2
Nv = (K-1) / 2.

Eu cred că, corect este:

Cod:

No=(K/2)+1;
Nv=(K/2)+(K&1);

[•kyrk]

hmm..dc ? mie mi se pare corecta prima varianta

[•freak93]

E corect cum scrie in solutie, exact formula asta o am in rezolvarea mea.
Te-ai gandit ca unul din schimbari se va afla ori pe ultima coloana ori pe ultima linie?
Poate nu ai luat acest caz in vedere.

P.S: Pentru cazul 4 2 din exemplu formula ta da C(2,2)*C(2,2)*2=2 cand defapt ar trebui sa fie 4

[•stocarul]

P.S: Pentru cazul 4 2 din exemplu formula ta da C(2,2)*C(2,2)*2=2 cand defapt ar trebui sa fie 4

Conform formulei mele este:
No=[2/2]+1; //adiva 2
Nv=[2/2]+2&1; //adica 1 (2&1 e echivalent cu 2%2)
Deci ar fi C(2,1)*C(2,0)*2=4;

În soluția oficială se spune că:
No=numarul de segnemte orizontale
Nv=numarul de segmente verticale
Dacă vă uitați în "desenul" din enunțul problemei (pentru N=8 și K=5), se observă că sunt 3 segmente orizontale (pe liniile 1, 4 și 7 ) respectiv alte 3 segmente verticale (pe coloanele 3, 6 și 8 ).
Conform formulei mele, No=3 și Nv=3.
Conform formulei din soluție, No=2 și Nv=2.

Totuși, ambele soluții returnează același rezultat datorită proprietății combinărilor de a avea valori simetrice.

Eu am menționat că în soluție sunt greșite pentru că acolo se specifică că No și Nv sunt numărul de segmente orizontale respectiv verticale.

[•freak93]

In primul rand scuze ca am calculat gresit dupa formula ta.
In al doilea rand uite pusa in aplicare formula ta pentru n=k=5000
1-Solutia Oficiala->12882
2-Formula Ta->53

Cand s-au scris solutiile sunt sigur ca nu s-au tinut cont de schimbarile care aveau loc pe ultima/prima linie sau coloana. De aceea tie iti da cu 1 mai mult, insa trebuie sa te aprob, este o greseala de exprimare in solutia oficiala. Presupun ca o sa se modifice foarte curand.

[•stocarul]

Și cu formula mea tot 12882 îmi dă pt 5000 5000.

[•freak93]

Si presupun ca tu in rezolvare faci C[n-2][no-1]*C[n-2][nv-1]*2?
Asta tot la formula din solutia oficiala duce, chiar daca a ta e mai corect exprimata.

[•gcosmin]

Intr-adevar este o greseala in solutia oficiala. Am schimbat acum.
Scuze ca am vazut asa tarziu.