|
Titlul: 156 Reg Scris de: Mircea Pasoi din Decembrie 12, 2005, 00:21:54 Aici puteţi discuta despre problema Reg (http://infoarena.ro/problema/reg).
Titlul: 156 Reg Scris de: Vlad Berteanu din Ianuarie 03, 2006, 16:02:33 calculul x=(x[i-1]*a+b*i) mod c poate fi facut intr-un mod inteligent ceva ? pt ca eu il fac pe int64 si imi mananca mult timp. Poate sa fie si de la solutie care e T*N*logK :?
Titlul: 156 Reg Scris de: Tiberiu-Lucian Florea din Ianuarie 03, 2006, 21:24:22 Nu-i buna complexitatea.
Titlul: 156 Reg Scris de: Gogu Marian din Ianuarie 04, 2006, 17:57:12 Eu am facut in O(T*N*logN) si a mers dar la limita initial. Mie imi mergea acasa destul de bine dar pe infoarena era extrem de incet din cauza compilatorului freepascal. Mi-am dat seama ca nu face operatia mod bine la int64 asa ca pana la urma am facut ceva de genul asta:
Cod: exp:=(a*x[i-1]+b*i); La mine acasa merge chiar mai incet asa dar se pare ca pe infoarena merge de cam 3 ori mai repede. E un bug tampit de compilator. Titlul: 156 Reg Scris de: Valentin Stanciu din Ianuarie 04, 2006, 18:15:45 interesant acest "bug".. dar nu uita ca pe infoarena se compileaza cu optimizarile activate! Acasa ai incercat cu ele activate? De multe ori schimbari mici de cod, pot duce la schimbari mari de timpi din cauza optimizarilor (compilatorul "vede" ca poate aplica optimizari in noul caz)
hint: treci pe C :) Titlul: 156 Reg Scris de: Tiberiu-Lucian Florea din Ianuarie 04, 2006, 19:12:37 Nu e bug... pur si simplu modul in care compilatorul decide ce optimizari sa faca este foarte ciudat, de unde si deviza programatorilor de C: "daca nu merge baga niste instructiuni vide in locuri aleatoare si compileaza din nou". :p
Titlul: 156 Reg Scris de: Gogu Marian din Ianuarie 04, 2006, 20:31:34 Sincer, nu cred ca operatorul mod ar fi ceva caruia i-ar trebui optimizari extraordinare si nu ar trebui sa fie influentat in nici un fel de optiuni de compilare (decat daca e dupa un div, caz in care se calculeaza si restul si catul simultan). Acasa am compilat cu fpc 2.0, cu si fara optimizari la optiuni de compilare si am scos timpi aproape identici. La infoarena se compileaza cu versiunea 1.9.4, care cred ca are mult bug-uri. Odata am luat chiar o eroare de compilare si cauza care am vazut-o in borderou era:
Cod: Free Pascal Compiler version 1.9.4 [2004/08/12] for i386 Va rog sa faceti un update la fpc 2.0 si gcc 4.0. Titlul: Raspuns: 156 Reg Scris de: Paul-Dan Baltescu din Februarie 20, 2007, 15:18:53 Imi puteti spune cat da pe testul urmator?
5 7 5 11 100 4 6 6 17 100 9 21 6 19 1000 13 3 2 31 1000 5 9 1 37 2000 7 Titlul: Raspuns: 156 Reg Scris de: Adrian Diaconu din Februarie 20, 2007, 19:14:26 Cod: 18 Titlul: Raspuns: 156 Reg Scris de: Airinei Adrian din Februarie 20, 2007, 20:37:12 Chiar, acum se poate pune si limita aia la memorie :)
Titlul: Raspuns: 156 Reg Scris de: Filip Cristian Buruiana din Februarie 20, 2007, 21:02:19 fixed
Titlul: Raspuns: 156 Reg Scris de: Bogdan-Cristian Tataroiu din Februarie 20, 2007, 21:22:02 Pai acum ar trebui reevaluate si toate sursele..
Titlul: Raspuns: 156 Reg Scris de: Mircea Pasoi din Februarie 20, 2007, 21:39:03 Vom reevalua, dar doar cele din infoarena 2 (restu s-au pierdut).
Titlul: Raspuns: 156 Reg Scris de: Gheorghe Cosmin din Februarie 20, 2007, 22:05:02 pare cam aiurea sa puneti alte limite... pare ok faza cu teste schimbate... dar asa... nu stiu... mie asa mi se pare... sa isi zica si altii parerea :)
plus ca eu daca am sursa de pe infoarena1 tot cu 100 raman.. si nu ar trebui, pentru ca am sursa care folosea mai mult de 7mb. Titlul: Raspuns: 156 Reg Scris de: Mircea Pasoi din Februarie 20, 2007, 22:35:20 Daca vrei sa ramai cu 100 de puncte, poti s-o lasi asa:)
Titlul: Răspuns: 156 Reg Scris de: Dragos Oprica din Martie 17, 2010, 17:16:24 Știu ca topicul acesta e foarte vechi, dar am o mare nelămurire:
Cum as putea obține 100p dacă doar declararea unui vector int de 2000000 îmi depășește memoria pe 3 teste. :) |