infoarena > infoarena - concursuri, probleme, evaluator, articole > Arhiva de probleme > Subiect: 198 Custi
Pagini: [1] 2 3   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: 198 Custi  (Citit de 17340 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« : Martie 18, 2006, 12:50:28 »
Aici puteţi discuta despre problema Custi.
Memorat
•azotlichid
Echipa infoarena
Nu mai tace
*****

Karma: 50
Deconectat Deconectat

Mesaje: 260



Vezi Profilul
« Răspunde #1 : Martie 18, 2006, 13:53:30 »
As avea de obiectat in ceea ce priveste aspectul enuntului si erorile gramaticale care nu fac, din pacate, decat sa degradeze imaginea celui care a propus-o. Propunatorii sunt rugati ca de acum incolo sa aiba putina grija la asta.
In rest, keep up the good work!  Thumb up
Memorat
vladut.forum
Vizitator
« Răspunde #2 : Martie 18, 2006, 14:47:52 »
Tongue dap, adevarat.... my bad

o sa am grija pe viitor!!!  Cool
Memorat
cristi8
Vizitator
« Răspunde #3 : Martie 18, 2006, 18:01:18 »
cum ati facut problema de obtineti timpii asa mici ? (sub 0.3 sec)
eu nu imi dau seama cum as mai putea imbunatatii sursa mea si ajung peste 0.3 secunde (am trimis de 2 ori, nu e din cauza "timpilor orientativi")

eu fac asa: citesc element cu element, nu-l retin intr-o matrice, ci intr-o variabila locala, fac O(1) calcule sa obtin o valoare care o pun intr-o matrice.
dupa aia fac N operatii, dupa care afisez solutia
Memorat
•gogu
Client obisnuit
**

Karma: 42
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #4 : Martie 18, 2006, 18:11:22 »
La o complexitate O(input) factorul dominant tot timpul e citire datelor. Ca sa citesti N*N numere iti ia mult mai mult decat sa faci ceva cu ele in RAM.
Fa o citire cu fread si cred ca o sa ai timpi mult mai mici.
Memorat
•Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #5 : Martie 18, 2006, 18:40:20 »
Citat din mesajul lui: gogu
La o complexitate O(input) factorul dominant tot timpul e citire datelor. Ca sa citesti N*N numere iti ia mult mai mult decat sa faci ceva cu ele in RAM.
Fa o citire cu fread si cred ca o sa ai timpi mult mai mici.

Ce vrei sa zici cu citirea fread ? Scuze.  Eh?
Memorat
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
•gogu
Client obisnuit
**

Karma: 42
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #6 : Martie 18, 2006, 19:00:10 »
fread e o functie C asemanatoare cu blockread in pascal care citeste in bucati mari din fisiere. Citesti intr-un buffer si trebuie sa parcurgi buffer-ul ca si cand citesti caracter cu caracter numerele.
Merge mult mai repede decat o citire standard dar e mai incomod de folosit.
Memorat
cristi8
Vizitator
« Răspunde #7 : Martie 18, 2006, 22:00:29 »
eh, nu vreau sa fie tras de par timpul cu chestii de-astea.. vreau daca stiti alta idee de rezolvare, sau un smen sau ceva.. pentru ca am vazut ca ceilalti care au trimis aproximativ odata cu mine (m-am uitat la vreo 2 solutii de 100 la Monitorul de evaluare) au avut timpi cam egali ei si sub 0.3 secunde.. si nu cred ca au stat sa citeasca mai mult odata din fisier si dupa aia sa parseze.
Memorat
•wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #8 : Martie 19, 2006, 19:33:39 »
pai mai bine de n^2 nu ai cum sa scoti.
Memorat
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
spx4
Vizitator
« Răspunde #9 : Martie 19, 2006, 21:23:00 »
aici as vrea sa dau doar o posibila idee...nu m-am gandit la consecinte
sau la o generalizare...insa aceste submatrice se numesc si minori(la mate).
(desi minorii sunt o notiune mai larga decat aceste "submatrici")
o idee interesanta ar fi aceea ca daca exista o submatrice  de ordin i atunci
automat in acesta exista 4 de ordin i-1.
daca exista 2 astfel de submatrici disjuncte(adica nu au in comun mai mult de i-2 coloane sau linii) atunci in ele vor exista 2*4 minori de ordin i-1.
deasemeni ar mai fi de remarcat ca pentru un exemplu de forma
11111
11111
11011
11111
11111
acel 0 de la mijloc provoaca disparitia oricarei submatrici de ordin 4.
mai precis ordinul maxim al submatricelor poate fi marginit in functie
de pozitia acelui 0.
poate ceva cu principiu includerii si excluderii...

sper sa am timp sa ma gandesc mai mult la problema...o sa postez ceva mai detaliat peste vreo zi doua
Memorat
u-92
Vizitator
« Răspunde #10 : Martie 19, 2006, 21:27:29 »
te complici prea mult cu includere sau minori.. chiar si n*n*logn mi-a intrat mie in timp Tongue
Memorat
•filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #11 : Martie 19, 2006, 21:54:35 »
Citat
sper sa am timp sa ma gandesc mai mult la problema...o sa postez ceva mai detaliat peste vreo zi doua


Pai daca chiar e ceva interesant, poti sa faci si un articol pe info.devnet.ro decat sa postezi mesaj cu mesaj pe forum.
Memorat
vladut.forum
Vizitator
« Răspunde #12 : Martie 20, 2006, 10:58:37 »
eu am obtinut urmatorii timpi

TEST 1   ...[0.02s]...   OK!
TEST 2   ...[0.01s]...   OK!
TEST 3   ...[0.01s]...   OK!
TEST 4   ...[0.01s]...   OK!
TEST 5   ...[0.05s]...   OK!
TEST 6   ...[0.04s]...   OK!
TEST 7   ...[0.04s]...   OK!
TEST 8   ...[0.03s]...   OK!
TEST 9   ...[0.04s]...   OK!
TEST 10   ...[0.04s]...   OK!

 Cool
Memorat
•devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #13 : Martie 20, 2006, 16:48:12 »
Stau, ma uit ... shi nu inteleg.

   Cum v-a intrat voua in timp chiar n*n*log n cand eu cu n^2 nu iau decat 60 de pct shi nu am decat 2 atribuiri shi o comparatie pe O(n^2)
 Brick wall  Brick wall  Brick wall  Brick wall  Brick wall
Memorat
vladut.forum
Vizitator
« Răspunde #14 : Martie 20, 2006, 16:58:31 »
sincer: teoretic un n^2 intra fara probleme, practic nu stiu ce ai in codul tau...

ar trebuii sa te uiti mai atent prin cod, sigur ai bushit ceva!
Memorat
u-92
Vizitator
« Răspunde #15 : Martie 20, 2006, 17:04:52 »
daca citesti cu stream`uri e explicabil, incearca sa folosesti printf/scanf
Memorat
cristi8
Vizitator
« Răspunde #16 : Martie 20, 2006, 18:41:47 »
Citat din mesajul lui: vladut.forum
eu am obtinut urmatorii timpi
TEST 1 ...[0.02s]... OK!
TEST 2 ...[0.01s]... OK!
TEST 3 ...[0.01s]... OK!
TEST 4 ...[0.01s]... OK!
TEST 5 ...[0.05s]... OK!
TEST 6 ...[0.04s]... OK!
TEST 7 ...[0.04s]... OK!
TEST 8 ...[0.03s]... OK!
TEST 9 ...[0.04s]... OK!
TEST 10 ...[0.04s]... OK!
 Cool

m-ai provocat.. Very Happy
eu am luat:
Cod:
TEST 1	...[0.01s]...	OK!
TEST 2	...[0.00s]...	OK!
TEST 3	...[0.01s]...	OK!
TEST 4	...[0.00s]...	OK!
TEST 5	...[0.03s]...	OK!
TEST 6	...[0.02s]...	OK!
TEST 7	...[0.02s]...	OK!
TEST 8	...[0.02s]...	OK!
TEST 9	...[0.02s]...	OK!
TEST 10	...[0.02s]...	OK!

TOTAL: 100

 Boo hoo!
Memorat
•gogu
Client obisnuit
**

Karma: 42
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #17 : Martie 20, 2006, 18:49:25 »
Cred ca e nevoie de un top dupa timpii solutilor de 100 la fiecare problema. Poate se straduieste lumea sa optimizeze mai mult.
Memorat
•greco
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« Răspunde #18 : Martie 20, 2006, 18:52:16 »
Si ce formula propui ? Cel mai mic timp maxim ? Suma timpilor minima ?
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.
•gogu
Client obisnuit
**

Karma: 42
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #19 : Martie 20, 2006, 18:57:14 »
Cred ca dupa suma timpilor e cel mai bine. Sau se pot face 2 topuri, dupa ambele criterii.  Smile
Memorat
vladut.forum
Vizitator
« Răspunde #20 : Martie 20, 2006, 19:30:49 »
o formula complicata... ca pe tc...  Very Happy

eu am vazut pe un site: era facuta suma timpilor  Cool
Memorat
•filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #21 : Martie 20, 2006, 20:09:40 »
Cum ati scos voi timpp aia? Ati citit cu fgets si ati parsat voi? Sau cum?
Memorat
•fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #22 : Martie 21, 2006, 10:29:42 »
da. cu fgets merge mai repede  Boo hoo!
Memorat
Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
•devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #23 : Martie 21, 2006, 13:39:06 »
nu mai folosesc streamuri, folosesc fscanf shi fprintf. Doar ca akuma mi-am dat seama ca e n^3 nu n^2, gresheala mea, scuze.
Memorat
•ciprianf
De-al casei
***

Karma: 11
Deconectat Deconectat

Mesaje: 104



Vezi Profilul
« Răspunde #24 : August 20, 2008, 22:03:40 »
vreo sugestie pt rezolvarea in O(N^2) ?
E: Never mind, am rezolvat
« Ultima modificare: August 21, 2008, 06:29:20 de către Farcasanu Alexandru Ciprian » Memorat
Pagini: [1] 2 3   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Arhiva de probleme > Subiect: 198 Custi
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines