049 Barbar

[•ciprianf]

Daca avem

Cod:

5 5
I....
*....
D....
.....
...0.

at distanta minima este 2? Sau zidul "blocheaza" dragonul?

[•jupanubv92]

Distanta minima nu este 2 deoarece dragonu nu poate arunca flacari prin zid ( zidu "blocheaza" dragonu ) deci in cazul asta distanta minima este 3 .

[•ciprianf]

Deci dragonul nu poate da cu flacari decat in S,N,E,V ,corect?. deci daca am avea

Cod:

5 5
0....
..I..
...D.
.....
.....

atunci distanta ar fi infinit.... pt ca paftenie nu interactioneaza cu dragonul...nu?, in cazul acesta ce afisez?

[•jupanubv92]

"minima din distantele pana la cel mai apropiat dragon din fiecare din celulele traseului sau sa fie maxim)." deci tu trebuie sa iti alegi un traseu a. i . distanta pana la cel mai apropiat dragon sa fie maximia , in cazul asta tu trebuie sa afisezi 3 pentru ca traseul tau este  (2,2)-(2,1)-(1,1) iar distanta pana la (2,2) este 3 obtinandu-se astfel : (3,3)-(3,2)-(2,2)

[•ciprianf]

deci pt exemplul de la problema as obtine ceva de genu

Cod:

5 4 3 4 3 2 1 2 3 4 
4 3 2 3 2 1 0 1 2 3 
3 2 1 2 3 2 1 2 3 4 
2 1 0 1 2 1 0 1 2 3 
1 -1 1 2 2 2 1 2 3 4 
0 -1 2 2 1 2 2 3 4 5 
-1 3 2 1 0 1 2 3 4 5 
5 4 -1 -1 -1 -1 3 4 5 6 
6 5 6 7 6 5 4 5 6 7 
7 6 7 8 7 6 5 6 7 8 

unde a(i,j) = dist minima pana la cel mai apropiat dragon. iar a(i)(j)=-1 unde avem zid
e corect?

[•jupanubv92]

da e corect practic tu trebuie sa faci un BFS iar in coada bagi pozitiile dragonilor apoi sa alegi un traseu care sa contina elemente cat mai mari

[•ciprianf]

asa am si facut...dar iau 80 de pcte....am incercat toate testele de pe forum si tot nu gasesc buba....imi puteti da cateva teste dificile?
LE: am scos 90
Am si eu probleme cu testul 7...

[•toni2007]

@ciprian
incearca sa maresti coada (sau mai bine implementeaz-o circular)

[•savim]

Sincer si eu am avut probleme cu testul 7.

Incearca testele de pe forum (primul test de pe prima pagina are raspunsul 3), s-ar putea sa analizezi gresit cazul cand flacara dragonului loveste punctul "I" in cazul de drum minim. 

Daca ai formatia

Cod:

...
.*.
.D.

Dragonul poate arunca foc(F) si in urmatorul fel:

Cod:

...
F*F
FDF

Nu e foarte clar exprimat in enunt, dar cam asta e. Focul poate s-o ia si "pe langa" zid.

[•ciprianf]

pf, ms savime, eu incercasem testul dar credeam ca raspunsul e 4, adica ma gandeam ca trebuie sa gasesc acel drum , dar fara pozitia de plecare..

[•jupanubv92]

Eu iau pe ultimul test "wrong answer" , ma poate ajuta cineva ? Presupun ca imi intra in memorie din moment ce iau  "wrong answer". Am incercat toate testele de pe formun si imi merg.


LE: Am luat 100 era cazul cand nu aveam solutie si trebuia sa afisez -1 .

[•PavelRazvan]

Pentru exemplul

Cod:

6 6
...O..
......
...I..
......
......
...D..

rezultatul e 4 ?

[•DraStiK]

Pentru exemplul

Cod:

6 6
...O..
......
...I..
......
......
...D..

rezultatul e 4 ?

Raspunsul nu este 4, ci 3.

[•PavelRazvan]

Multumesc
Am luat suta 

[•horeste12]

Imi poate trimite cineva daca se poate testul 3 si 9 pe [email protected] ? La testul 3 primesc TLE cred ca din cauza unui ciclu infinit, iar la 9 primesc killed by signal 11... si nu imi dau seama de ce ...

[•devilkind]

Testele din arhiva de probleme nu se fac publice.

[•Bit_Master]

O sa sune cam aiurea mesajul asta, dar am o sugestie de propozitie de adaugat la cerinta: "Lui Paftenie ii plac provocarile, asa ca doreste el sa gaseasca singur drumul. Asa ca va cere sa-i spuneti doar distanta minima posibila, ca sa incerce sa o obtina."

[•Teodor94]

iau 90 puncte cu WA pe testul 3.ca timp de executie are 4 ms,deci ar trebui sa fie un test mic.
aveti vreo idee?

[•chibicitiberiu]

Am o intrebare.
Daca drumul arata asa:

Cod:

..o...
ooo...
...D..

Cat e distanta?
In mod normal ar fi sqrt(2);
Dragonii pot arunca flacari si pe diagonale? Sau pe linii frante???

[•eudanip]

Am o intrebare.
Daca drumul arata asa:

Cod:

..o...
ooo...
...D..

Cat e distanta?
In mod normal ar fi sqrt(2);
Dragonii pot arunca flacari si pe diagonale? Sau pe linii frante???

Nu, nu pot nici pe diagonala si nici prin pereti.

[•chibicitiberiu]

Aha, dar care e distanta in cazul asta?

[•PlayLikeNeverB4]

2

[•chibicitiberiu]

Aha, merci. Cred ca am inteles acum  .

[•tinky]

se poate lua 100 pe problema si fara cautare binara (sau testele nu sunt indeajuns de stricte), folosind o matrice in care in v [ x ] [ y ] se tine minte valoarea minim de pe drumul pana in punctul de coordonate x si y

[•PlayLikeNeverB4]

Merge cu doua parcurgeri in latime.