•domino
|
|
« : Noiembrie 03, 2005, 02:13:54 » |
|
Aici puteţi discuta despre problema Geamuri.
|
|
|
Memorat
|
|
|
|
andreit1
Vizitator
|
|
« Răspunde #1 : Noiembrie 06, 2005, 21:21:43 » |
|
Cam in ce complexitate ar trebui sa rezolv problema, tinand cont ca citirea si afisarea unui 0 pentru fiecare intrebare dureaza 0.12 secunde pe ultimul test( stiu ca timpii din monitor sunt orientativi, dar probabil se apropie de realitate)? Sursa folosita: var fi,fo:text; i,x1,y1,x2,y2,c,n,x:word; begin assign(fi,'geamuri.in'); reset(fi); assign(fo,'geamuri.out'); rewrite(fo); readln(fi,c); readln(fi,n); for i:=1 to n do readln(fi,x1,y1,x2,y2); readln(fi,n); for i:=1 to n do begin readln(fi,x); writeln(fo,0); end; close(fo); end.
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #2 : Noiembrie 07, 2005, 00:14:18 » |
|
Am schimbat limita la 0.2s
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #3 : Noiembrie 08, 2005, 20:54:44 » |
|
O(N log^2 C + M) ajunge? :cry:
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #4 : Noiembrie 08, 2005, 21:46:25 » |
|
Nu stiu, dar cred ca a fost data la C^2 + N + M.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•filipb
|
|
« Răspunde #5 : Noiembrie 09, 2005, 11:36:44 » |
|
Da, asa e
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #6 : Decembrie 12, 2005, 22:36:24 » |
|
Fiecare geam ce contine acel punct se va sparge In problema nu se intelege ca tu vrei un punct inclus in ki dreptunghiuri, daca glontul i sparge geamuri atunci glontul i + 1 va sparge din geamurile ramase ... nu tot din geamurile initiale, enuntul induce in eroare pe cei ce vreau sa rezolve problema !!!!!!!!!
|
|
|
Memorat
|
|
|
|
•y2k
Strain
Karma: -3
Deconectat
Mesaje: 22
|
|
« Răspunde #7 : Februarie 11, 2006, 10:28:55 » |
|
Ce e gresit in codul asta? (poate sunt eu prost si nu-mi dau seama, dar mi se pare corect). La codu' asta iau 0 punct. #include<fstream> #define IN_FILE "geamuri.in" #define OUT_FILE "geamuri.out" std::ifstream IN; std::ofstream OUT; long n,m,c,a[1025][1025],b[50001]; void adaugaGeam(int x1, int y1, int x2, int y2) { int i,j; for(i=y1; i<=y2; ++i) for(j=x1; j<=x2; ++j) { --b[a[i][j]]; ++a[i][j]; ++b[a[i][j]]; } } void citire() { IN>>c; IN>>n; int i,x1,y1,x2,y2; for(i=1; i<=n; ++i) { IN>>x1; IN>>y1; IN>>x2; IN>>y2; adaugaGeam(x1,y1,x2,y2); } IN>>m; for(i=1; i<=m; i++) { IN>>x1; OUT<<b[x1]<<"\n"; } } int main() { IN.open(IN_FILE); OUT.open(OUT_FILE); citire(); IN.close(); OUT.close(); return 0; } Sa-mi spuneti daca e gresti, nu vreau sa-mi spuneti ce am gresit, o sa ma gandesc eu la asta
|
|
|
Memorat
|
|
|
|
•danielp
|
|
« Răspunde #8 : Februarie 11, 2006, 11:15:47 » |
|
Pai daca iei 0 puncte nu e clar ca e gresit? Poate doresti sa iti spunem ce ai gresit:)
|
|
|
Memorat
|
I can't get a life if my heart's not in it
|
|
|
•y2k
Strain
Karma: -3
Deconectat
Mesaje: 22
|
|
« Răspunde #9 : Februarie 11, 2006, 11:27:05 » |
|
ai dreptate... poate imi spui
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #10 : Februarie 11, 2006, 23:56:48 » |
|
Asteapta sa-ti depaneze altii codul, si o sa ajungi departe.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
ditzone
Vizitator
|
|
« Răspunde #11 : Februarie 12, 2006, 09:32:08 » |
|
In primul rand sunt convins ca iei destule TLE si ar trebui sa te gandesti la o alta complexitate si in al doilea rand.. esti sigur ca raspunzi corect la intrebarile pentru K=0 ?
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #12 : Mai 02, 2007, 21:01:12 » |
|
la primu query in exemplu zice ca ar fi un singur punct si anume: (5 4). Mie mi se pare ca si (5 3) e corect deci ar fi 2 puncte. Ce nu am inteles bine??
|
|
|
Memorat
|
|
|
|
•DITzoneC
|
|
« Răspunde #13 : Mai 06, 2007, 18:17:18 » |
|
Pai daca tragi din (5,3) nu atingi ultimul geam, atingi doar primele 2.
|
|
|
Memorat
|
|
|
|
•Andrei1998
|
|
« Răspunde #14 : Martie 16, 2013, 13:08:27 » |
|
Sunt si eu curios de ceva legat de problema: Daca Geminski are doua variante de a trage primul glont pe care o va alege? Intreb asta deoarece Cosmin Negrusesti a spus ca dupa ce se trage primul glont, geamurile sparte de el dispar si astfel raspunsurile pentru urmatoarele gloante pot diferi in functie de ce alegere face Geminski pentru glontul cu 2 variante. Ex. Se poate sa dispara puncte unde se sparg 4 geamuri daca alegem o varianta de la glontul 1 sau sa nu dispara daca o alegem pe cealalta. Multumesc anticipat. Mentionez ca am gasit rezolvarea cu Smenul lui Mars deja. L.E.: Rezolvat!
|
|
« Ultima modificare: Iunie 24, 2013, 09:15:16 de către Constantinescu Andrei Costin »
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #15 : Iunie 20, 2013, 14:03:27 » |
|
Cred ca ar trebui marita un pic limita . Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M).
|
|
|
Memorat
|
|
|
|
•Magnvs
Strain
Karma: 56
Deconectat
Mesaje: 15
|
|
« Răspunde #16 : Iunie 21, 2013, 17:00:40 » |
|
Cred ca ar trebui marita un pic limita . Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M). merge fara parsare. tu aloci prea multa memorie si de-aia iesi din timp cred. vezi ca poti sa tii S in A, avand in vedere ca nu mai folosesti A odata ce iti creezi S.
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #17 : Iunie 23, 2013, 12:37:59 » |
|
Mersi, asa este, alocam prea multa memorie si in plus parcurgeam matricea de 2 ori, in loc de o singura data. Dar la sursa asta ce este gresit: http://www.infoarena.ro/job_detail/965110?action=view-source ? Iau doar 70p desi folosesc doar matricea A si o parcurg o singura data
|
|
|
Memorat
|
|
|
|
•Magnvs
Strain
Karma: 56
Deconectat
Mesaje: 15
|
|
« Răspunde #18 : Iunie 23, 2013, 21:31:07 » |
|
tu parcurgi coloana cu coloana. trebuie sa parcurgi linie cu linie ca sa nu spargi cache-ul.
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #19 : Iunie 23, 2013, 23:37:00 » |
|
Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?
|
|
|
Memorat
|
|
|
|
•Magnvs
Strain
Karma: 56
Deconectat
Mesaje: 15
|
|
« Răspunde #20 : Iunie 24, 2013, 12:10:13 » |
|
Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?
matricile in c/c++ sunt retinute linie cu linie, iar cand pargurgi linie cu linie tu treci la elementul cu 1 poz in dreapta, dar coloana cu coloana sari vreo 1000 de elemente in cazul de fata. cacheul e niste memorie care poate fi accesata rapid, iar tu cand accesezi un element al unui vector procesorul presupune ca o sa ai nevoie si de urmatoarele elemente si ti le baga in cache.
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #21 : Iunie 25, 2013, 11:04:07 » |
|
Nu stiam. Thanks!
|
|
|
Memorat
|
|
|
|
|