infoarena

Aici puteţi discuta despre problema Zota & Chidil (http://infoarena.ro/problema/zc).

In enunt se precizeaza ca daca celula de pornire este afectata, nu este nevoie de praf magic. Dar daca Chidil se intoarce si trece din nou prin ea, atunci este nevoie de praf magic?

Nu...

De ce imi da INVALID MEMORY REFERENCE???  ](*,)  Sunt disponibili 64 de mega (parca) shi eu folosesc doar vreo 20. Any ideas?  :(

e ceva special la testu 10 ? am trimis sursa de tz ori si iau doar 90 :( plz help  [-o<  [-o<  [-o<

E cel mai mare si mai nashpa test :). Se pica daca nu esti atent la partea cu "Chiar daca celula de pornire este afectata NU e nevoie de praf magic cand se trece peste ea". Tin minte ca luam si eu 90 din cauza asta.

:-k foarte dubios... io scot celula 0,0 din vectorul cu pozitii afectate

A si eu o nelamurire.
In enunt coordonatele sunt de forma x y.
Oricum as numara imi da 7 6 si 11 13 nu 5 6 si 12 10. Ma lamureste si pe mine cineva.
M-am lamurit singur. Neatent.
El porneste din (0,0) si de aia imi da cu unu mai mare. Mersi oricum. =D>

In acea figura axa Ox este axa orizontala si Oy este cea verticala.. Eu cand am rezolvat problema am citit coordonatele ca y x  :-' Depinde cum iti e tie mai usor

Iau 40 de puncte.( 6 TLE-uri )

Am rezolvat ca in solutia oficiala, dar fara STL .
Va rog sa imi spuneti exact pasii care i-ati facut, ca am impresia ca as putea optimiza putin aici la mine.
Eu fac asa:
Citesc m, n si coordonatele celor n puncte capcane.Imediat dupa aceea calculez punctele in vectorul de capcane si le sortez ( Qsort de mana ).Apoi citesc cate o directie, si ma duc la fiecare pas cerut in directie si aplic cautarea binara pentru fiecare punct( dat de directia curenta )

Imi pare rau ca am detaliat asa metoda *( care ar putea parea evidenta  :oops: ),dar sunt chiar nedumerit.. :sad:.Sa fie oare de la faptul ca nu am tinut coordonatele in doi vectori x[] si y[] ci le am  intr-o structura ? ( astfel ca nu am facut decat o singura cautare binara ... :-s )

Any ideas ?  :?

1. Ar fi bine sa folosesti sortul din STL.
2. Ar fi bine sa nu folosesti structuri [mai ales in Pascal].
//Asta te-ar costa maxim 20 de puncte
3. Nu trebuie sa faci cautarea binara pentru fiecare punct. Ajunge de doua ori pe fiecare noua directie.

Sunt in C++.( ba chiar C, in sursa de fata  :ok: )
Inainte sa trec sursa in STL, as vrea insa sa ma lamuresti la ceva.

Cum adica ? Ca eu din ce ai spus as intelege ceva de genul : daca sunt la punctul curent (i,j), si citesc o noua directie, calculez punctul final conform directiei ( i',j') si caut binar cate numere din vectorul de capcane se afla intre cele doua puncte ( i,j ), si ( i',j' ) pe aceeasi axa evident.
Am inteles bine ? ???  ???

da dar ideea este ca tu nu cauti binar un punct, ci un interval. Cauti binar limita stanga si limita dreapta a intervalului si vezi cate numere ai intre acestea, cam asta ar fi ideea ;)

Zonele afectate din jurul punctelor capcana se pot suprapune ? Daca da, atunci cand efectuezi o cautare binara poti numara de mai multe ori o casuta. Daca elimini dupa sortare, e O(N^2). Daca le elimini inainte, trebuie un hash. Se poate altfel ?

Din cate imi amintesc eu am pus punctele intr-un vector si le-am sortat. Apoi, am parcurs vectorul si daca a[ i ] era egal cu a[ i-1 ], nu-l puneam in vectorul b. In vectorul b vei avea apoi doar punctele distincte. Cred ca e cam extrem hash :)

Ce varzik sunt. Am imbatranit ..  :aha:

Cat va da pentru :

14

Salut ! Am ceva probleme cu timpul.

N-am inteles exact ce fel de cautare binara trebuie sa fac. Eu am retinut punctele afectate de capcane intr-un struct, am sortat dupa x, avand grija ca fiecare punct sa apara exact o data. Apoi caut binar fiecare pas pe care il face Chidil.

Daca am punctul de dinainte de calculare a directiei (i, j) si calculez pozitia unde va ajunge dupa ce stabilesc directia (i', j'), eu ce trebuie sa caut binar ?

Daca Chidil se depleaseaza N sau S, atunci noua pozitie va fi de forma (i, j') (presupunand ca a plecat din (i,j)). Pozitiile cu capcane prin care trece el pe drum formeaza o secventa consecutiva in vectorul de bombe (sortat dupa x). Daca stii pozitia p a lui (i, j) in vector (pe care o determini cautand binar), pozitia p' a lui (i, j') (idem), atunci numarul de bombe de pe drum este |p-p'| +/- 1.

Deplasarea spre V sau E, se trateaza in mare la fel. N-o sa-ti stric placerea sa te mai gandesti un pic. :)

Nu inteleg cum vine!

Daca coordonatele sunt (x, y), atunci pe exemplul dat se merge in pozitiile:
(0,0) (0,-3) (6,-3) (6,-10) (8,-10) (8,-7) (14,-7) (14,-13) (11,-13)

Daca capcanele sunt in (5,6) si (12,10) atunci drumul nu se apropie niciodata  :-s.

Nu mai inteleg nimic!!!

In figura coordonatele par a fi *-1, adica (-5, -6)

mhm mie citirea +sortare casute afectate cu stl imi iese din timp pe 4 teste :?