796 Kdrum

[•pauldb]

Aici puteti discuta despre problema Kdrum.

[•dornescuvlad]

Am o intrebare.Din K==1 pt 20% din teste rezulta ca trebuie sa fac un lee clasic pentru cele 20pct ?
Pentru ca am facut asta si vad ca primesc 0 pct.
Nu e bun rationamentul, sau gresesc la implementare? Multumesc.

[•danalex97]

Salut ! Am incercat sa fac un fel de Fill (bkt , cum vreti ... ideea e ca incerc toate posibilitatile) si mi se parea ca , complexitatea acestuia pe hartie nu pare atat de exagerata. Preprocesez Cmmdc-urile cu ajutorul a 2 matrice ( 2D & 3D ) si daca calea e mai mare decat Min atunci algoritmul se opreste automat. Pt. N si M mai mici mi se pare ca ar intra , insa nu am nici o idee pentru 100p intrucat nu sunt familiarizat cu grafurile. Cine ma poate ajuta va rog sa imi dati un pont. Multumesc anticipat. 

http://infoarena.ro/job_detail/749129?action=view-source

[•darkseeker]

Un nod in graful tau poate fi considerat un triplet ( linie,coloana,indice_divizor), unde indice_divizor reprezinta al cata-lea dintre divizorii lui k ordonati in ordine crescatoare este cmmdc( produsul de pe drumul de lungime minima de la x1,y1 la linie,coloana , k) . Parcurgi acest graf in latime incepand din nodul (x1,y1,Indice[cmmdc(A[x1][y1],k)] . Nodul in care trebui sa ajungi este (x2,y2,nrDivizori(K)). Sper sa te ajute explicatia .