Problema C++ Mere De Pe Campion

[Kid Koder]

Am incercat astazi sa rezolv o problema de pe .campion.

Enuntul: Click

Solutia mea: Click

O idee a ce am facut eu acolo: Mai intai apelam functia Fall(1) (deoarece primul mar cade automat), iar apoi "simulam" caderea marului respectiv. Daca cumva pe drum lovea alt mar, apelam aceeasi functia, doar ca pentru marul care a fost atins. In Down retineam nivelul la care se afla ultimul mar (care l-am considerat ca fiind solul). In Fallen marcam cu 1 daca marul i a fost atins, respectiv 0 in caz contrar. Faza e ca solutia trebuie optimizata, astfel incat sa intre in 0.1 secunde Mentionez ca pe primul test gresit, rezultatul este corect (am verificat).

Primul test gresit: Click

Rezultatul corect (care imi da si mie) : 164

[Kid Koder]

Nu stiu de ce, dar nu pot da EDIT la primul post.

Am rezolvat: Click

Sursa: Click

 

Am modificat doar functia Fall() in felul urmator:

void Fall(int App_nr) {
    for(int i = 1; i <= N; ++i) {
        if(App_nr != i && Fallen[i] == 0 && Apple[App_nr].z >= Apple[i].z) {
            if(Distance(Apple[i], Apple[App_nr]) <= (Apple[App_nr].r + Apple[i].r) * (Apple[App_nr].r + Apple[i].r)) {
                Fallen[i] = 1;
                Fall(i);
            }
        }
    }
}

Am facut abstractie de "z". Pur si simplu am verificat daca se ating atunci cand marul App_nr va ajunge la i (daca este posibil).