114 Muzeu

[•pauldb]

Ideea ta nu duce la complexitatea optima. Daca sunt N^2 paznici, atunci o sa ai complexitate O(N^4) si de aceea iei TLE. Ca sa optimizezi, poti pune toti paznicii in coada la inceput si sa faci un singur Lee. Astfel ai complexitate O(N^2).

Motivul pentru care iei Incorect este, cel mai probabil, faptul ca ai implementat gresit.

[•costyv87]

  deci nush c are am facut lee si imi da 9 teste nu-mi da testul 7 spune k e incorect        
 
chiar nu imi dau seama c nu poate sa imi dea

am pus intr-o coada toti pasnicii si cred k este bn adik 9teste /10 chiar nush ..

[•gabor_oliviu1991]

Ai grija sa pui coada de 100 000 (nevoie e doar de aprox 65 000 dar daca memoria iti permite  ) si matricea sa fie de 255 pe 255.  Eu cand aveam matricea de 251 luam doar 70 de pct

[•blue_phoenix]

Nici mie nu-mi da testul 7. Oricum, eu aveam o gresala (dupa ce am reparat-o,tot 90 am luat...). S-ar pare ca nici un test nu verifica ce se intampla daca nu sunt deloc paznici.

Exista vreo sansa ca "o insula" de camere libere sa se transforme in camere inchise, doar pentru ca sunt inconjurate din toate partile
de camere inchise?("`#' pentru camera inchisa (prin care nu pot trece nici paznicii, dar in care nu pot intra nici hotii)";daca o zona e "bordata" de # nu poate sa intre nici hoti nici paznici...deci e inchisa?)

[editat de moderator] iti mai spun o data: nu mai posta consecutiv, ci editeaza-ti mesajele anterioare

[•SpiderMan]

Buna. Am facut problema si imi da incorect la 3 teste. Care este problema ? http://infoarena.ro/job_detail/393084

[•popoiu.george]

De unde sa stim care este problema? Explica macar cum faci...poate e gresit algoritmul.

[•SpiderMan]

Am descoperit greseala , am retinut ca si caractere si pentru numarul 10 spre exemplu nu il tinea ca si caracter. Dar am transformat totul in int si am reusit 

[•paul992]

Imi poate spune cineva dece la toate testele inafara de primul primesc Killed by signal 11(SIGSEGV)? Eu iau cate un lee din fiecare P. Am inteles ca se poate face mai optim daca pui paznicii in coada la inceput.Dar nu prea stiu asa.

[•dornescuvlad]

Eu am pus pozitiile primilor doi paznici in coada, si am dat drumul la lee.S-ar putea sa nu fi declarat cozile indeajuns de mari.

[•nbibest]

Vai....ii cam puscat asta de commuri...am atasat ceva nesuportat si nu o tinut minte ce am scris...vai.....de la capat. Salut tuturor. Am incercat si eu sa fac acest program si in afara de primele 3 teste imi da time limit exceded. Eu nu am memorat nicio pozitie pt niciun paznic...doar am facut pur si simplu lee sa actioneze in stilul clasic, iar in matricea folosita am initializat paznicii cu 0, camere interzise cu -2 si restul cu -1, mai apoi sa fie schimbate in cadrul lee. E cam suspect totusi ca numai pt citirea si afisarea fisierelor text la cel mai "mancator" test imi ia 28 de ms....apoi la lee cat sa mai zic ca ii ia... ....apropo eu folosesc fpc  asa ca daca e vreun binevoitor astept sfaturi. va multumesc, am atasat si programul.

[•SpiderMan]

M-am uitat peste sursa ta, greseala ta este ca trebuie sa folosesti o coada in care sa bagi pozitiile celor doi paznici, si sa faci Lee atata timp cat nu mai ai elemente in coada. Asa e varianta optima .

[•gabitzish1]

M-am uitat peste sursa ta, greseala ta este ca trebuie sa bagi in coada pozitiile celor doi paznici, si sa faci Lee atata timp cat nu mai ai elemente in coada.

Peste ce sursa te'ai uitat? Nu e nicio coada acolo.

@ Neagu Bogdan

Ai complexitate prea mare: O(N^2 * distantaMaxima), de aceea iei TLE. Ca sa iti intre in timp, trebuie sa folosesti algoritmul lui Lee (probabil asta incerca sa zica Robert Simoiu in postul anterior).

L.E. @Robert : Tu vezi greseli care nu exista.

[•SpiderMan]

Stiu ca nu are coada, aia ziceam si eu 

[•nbibest]

Nu prea inteleg ce coada (adica vector ma gandesc) mai trebuie sa folosesc...si nici cu complexitatile nu le stiu   . Dar am mai facut o versiune care dupa parerea mea ar trebui sa fie mult mai rapida....am mai pus 2 vectori, in primu iau poz paznicilor, apoi in al doilea pun pozitiile unde am incrementat, apoi in primu pun tot ce ii in 2 si tot asa...acum nu mai ia fiecare element la cautat ci stie sigur care le are de incrementat ...dar tot 30 de pct iau... il atasez...si daca puteti da mai multe detalii vas fi recunoscatori... eu din ce am vazut lee nu era numa cu matrice si altfel nu am vazut...insa cred ca asta e una dintre cele mai neoptimizate metode. Astept raspunsuri in continuare si va multumesc pentru ajutor.

[•Florian]

Din spusele tale, observ ca tu nu cunosti notiunea de coada. Daca nu stii sa folosesti o coada, atunci nu poti face nici Lee. Iar faptul ca nu stii Lee, implica faptul ca nu poti rezolva corect si eficient problema asta. Concluziile ( doar una adevarata ):
1. invata coada, apoi Lee .
2. observatia mea e gresita ( si imi cer scuze )

[•nbibest]

Din spusele tale, observ ca tu nu cunosti notiunea de coada. Daca nu stii sa folosesti o coada, atunci nu poti face nici Lee. Iar faptul ca nu stii Lee, implica faptul ca nu poti rezolva corect si eficient problema asta. Concluziile ( doar una adevarata ):
1. invata coada, apoi Lee .
2. observatia mea e gresita ( si imi cer scuze )

pai coada nu e un vector? ai vazut programul meu? Daca poti imi explici te rog cum ce este acea "coada"? si indicatii pentru rezolvarea problemei?

[•popoiu.george]

Cred ca faci confuzie. Da, coada o poti implementa ca un vector.

Daca stii ce este o stiva poti face o analogie.

Daca tii un vector asupra caruia tu impui niste restrictii si il folosesti intr-un anumit fel, poti sa spui ai o stiva sau o coada, etc.

Daca vrei sa intelegi mai bine structurile astea iti sugerez sa incerci sa le folosesti din STL sau sa le implementezi tu (daca stii sa aloci dinamic memorie sau OOP) , atunci cred ca vei intelege cu adevarat semnficatia lor.

[•nbibest]

Cred ca faci confuzie. Da, coada o poti implementa ca un vector.

Daca stii ce este o stiva poti face o analogie.

Daca tii un vector asupra caruia tu impuii niste restrictii si il folosesti intr-un anumit fel, poti sa spui ai o stiva sau o coada, etc.

Daca vrei sa intelegi mai bine structurile astea iti sugerez sa incerci sa le folosesti din STL sau sa le implementezi tu (daca stii sa aloci dinamic memorie sau OOP) , atunci cred ca vei intelege cu adevarat semnficatia lor.

  mai cam lasat in ceata... nu stiu cei ala STL...daca e ceva din C++, eu folosesc fpc. Sa aloc dinamic memorie nu stiu dar nu e asa de greu din cate am vazut in help, insa nu stiu cu ce m-ar ajuta, iar OOP iar nu am nici cea mai vaga idee ce este 

[•Florian]

Atunci ia-ti un manual de info ( a-10a, a-11a ) si spor la invatat.  Apoi, revino la problema "muzeu". Deja suntem off topic. 

[•nbibest]

si...inca o intrebare...cam tarziu dar mia dat-o profa problema sa o fac insa nu stiu cat de mult s-a uitat la ea...pentru ce clasa e? Ca eu sunt doar a 9a

[•dornescuvlad]

Lee-ul e in programa de intensiv  la a clasa a 10-a

[•nbibest]

nu stiti cumva unde as putea gasi un algoritm lee asemanator cu cel folosit in aceasta problema sau rezolvarea la aceasta problema pentru ca nu o gasesc niciunde, iar rezolvarile facute de ceilalti nu le pot downloada 

[•SpiderMan]

Ti-as putea da eu, ti-am trimis P.M.

[•vladtarniceru]

trebuie afisat ordonat ca in exemplu?(adica de exemplu:

 1 -2  3 -2
-2  3  4  5

?

[•SpiderMan]

Trebuie sa afisezi matricea exact cum era ea initial, doar ca trebuie pus in loc de ziduri o cifra etc .