•Marius
|
![](/forum/Themes/default/images/post/xx.gif) |
« : Ianuarie 04, 2010, 18:56:18 » |
|
Aici puteţi discuta despre problema Al k-lea termen Fibonacci.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•Robytzza
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #1 : Martie 03, 2010, 16:53:22 » |
|
cine imi explica si mie de ce sursa asta ia 100-a : http://infoarena.ro/job_detail/380187?action=view-source #include<fstream> using namespace std; int main() { fstream in("kfib.in",ios::in),out("kfib.out",ios::out); int x=0,y=1,z,k; in>>k; while(k--%1332028)z=(x+y)%666013,x=y,y=z; out<<x<<endl; }
aha ms
|
|
« Ultima modificare: Martie 03, 2010, 17:36:36 de către Ionescu Robert Marius »
|
Memorat
|
|
|
|
•klamathix
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #2 : Martie 03, 2010, 17:33:22 » |
|
Numerele Fibonacci sunt periodice modulo m . Cel mai probabil 1332028 este lungimea perioadei pentru m = 666013.
|
|
|
Memorat
|
|
|
|
|
•Cosmin
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #4 : Martie 08, 2010, 16:20:07 » |
|
Nu prea ai ce face cu formula pt problema asta pt ca ti-ar trebui calcule cu numere reale de precizie mare.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #5 : Martie 08, 2010, 16:20:59 » |
|
Nu cred ca merge cu numere mari ![Confused](http://www.infoarena.ro/forum/Smileys/default/unsure.gif)
|
|
|
Memorat
|
|
|
|
•yo_s_canta
Strain
Karma: -2
Deconectat
Mesaje: 2
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #6 : Martie 08, 2010, 23:03:50 » |
|
N-am incercat sa implementez... dar banuiesc ca daca folosesti round() o sa dea bine
|
|
|
Memorat
|
|
|
|
•Cosmin
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #7 : Martie 08, 2010, 23:40:14 » |
|
Ia incearca, ca sa intelegi mai bine ce se intampla.
|
|
|
Memorat
|
|
|
|
•otilia_s
Strain
Karma: 0
Deconectat
Mesaje: 12
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #8 : Martie 23, 2010, 12:51:53 » |
|
Puteti sa imi explicati si mie va rog cum functioneaza "1LL" din expresia: C [j] = (C[j] + 1LL * A[k] * B[k][j]) % mod; Presupun ca transforma in long long, pentru cazul in care A[k]*B[k][j] depaseste tipul int. Dar mi-ar placea sa inteleg mai bine ce se intampla cu expresia si in ce context ar mai putea fi folosit. Multumesc! ![Very Happy](http://www.infoarena.ro/forum/Smileys/default/biggrin.gif)
|
|
|
Memorat
|
|
|
|
•wefgef
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #9 : Martie 23, 2010, 13:58:02 » |
|
1LL înseamna valoarea 1 reținută pe 64 de biți. Când înmulțești un long long cu un int, se va face cast la long long. Astfel, dacă vrei să înmulțești două variabile A și B de tip int, iar produsul lor intră doar pe long long, poți face ca mai sus: 1LL * A * B. O altă varianta ar fi să scrii tu castul de mână: (long long)(A) * B.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•otilia_s
Strain
Karma: 0
Deconectat
Mesaje: 12
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #10 : Martie 23, 2010, 14:28:27 » |
|
Am inteles! ![Smile](http://www.infoarena.ro/forum/Smileys/default/smile.gif) Multumesc!
|
|
|
Memorat
|
|
|
|
•S7012MY
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #11 : Iunie 06, 2010, 19:39:49 » |
|
Ar mai fi aici si problema nkbiti
|
|
|
Memorat
|
|
|
|
•caen1
Client obisnuit
![*](/forum/Themes/default/images/star.gif)
Karma: 22
Deconectat
Mesaje: 75
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #12 : Aprilie 24, 2011, 18:46:04 » |
|
Exista vreun mod prin care sa determini (rapid) perioada in astfel de cazuri, sau metoda simpla nu este practica in timpul unui concurs? Multumesc!
|
|
|
Memorat
|
|
|
|
•scipianus
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #13 : Noiembrie 03, 2011, 20:29:00 » |
|
Cred ca este o problema cu timpii la evaluator la problema aceasta,intrucat observ in monitor foarte multe surse de 0.30-0.50kb care implementeaza fibonacci in mod clasic, liniar,surse care iau 100pct,desi se zice ca ar trebui sa ia vreo 20pct ![Read This!](http://www.infoarena.ro/forum/Smileys/default/icon_readthis.gif)
|
|
|
Memorat
|
|
|
|
•klamathix
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #14 : Noiembrie 03, 2011, 21:00:26 » |
|
Cred ca este o problema cu timpii la evaluator la problema aceasta,intrucat observ in monitor foarte multe surse de 0.30-0.50kb care implementeaza fibonacci in mod clasic, liniar,surse care iau 100pct,desi se zice ca ar trebui sa ia vreo 20pct ![Read This!](http://www.infoarena.ro/forum/Smileys/default/icon_readthis.gif) Mnop. Sursele alea se folosesc de periodicitatea numerelor Fibonacci modulo n. Pentru n-ul din problema asta, perioada e mica (2 * n parca ) si poate fi calculata liniar.
|
|
|
Memorat
|
|
|
|
•NicuCJ
Strain
Karma: 6
Deconectat
Mesaje: 44
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #15 : Aprilie 17, 2013, 14:56:09 » |
|
Merge cu o idee asemanatoare sa faci in timp logaritmic si al k-lea termen fibonacci de 3, 4, 5 s.a.m.d. ?(fib de 3 fiind Fn=Fn-1+Fn-2+Fn-3)
|
|
|
Memorat
|
|
|
|
•pauldb
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #16 : Aprilie 17, 2013, 14:58:53 » |
|
Da.
|
|
|
Memorat
|
Am zis ![Mr. Green](http://www.infoarena.ro/forum/Smileys/default/mrgreen.gif)
|
|
|
•NicuCJ
Strain
Karma: 6
Deconectat
Mesaje: 44
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #17 : Aprilie 17, 2013, 22:49:22 » |
|
Imi poti spune te rog cum arata matricea fixata pentru fib de 3? Nu gasesc niciun pattern fata de fib de 2.
|
|
|
Memorat
|
|
|
|
•klamathix
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #18 : Aprilie 17, 2013, 23:12:47 » |
|
Iti spunem duminica la 00:00:00 daca vrei ![Very Happy](http://www.infoarena.ro/forum/Smileys/default/biggrin.gif) . L.E: Sarumana, Craciun ![Smile](http://www.infoarena.ro/forum/Smileys/default/smile.gif) .
|
|
« Ultima modificare: Aprilie 18, 2013, 01:25:01 de către Mihai Calancea »
|
Memorat
|
|
|
|
•deneo
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #19 : Aprilie 18, 2013, 00:38:58 » |
|
@Mihai Cred ca vrei sa zici duminica ![Tongue](http://www.infoarena.ro/forum/Smileys/default/tongue.gif)
|
|
|
Memorat
|
|
|
|
•NicuCJ
Strain
Karma: 6
Deconectat
Mesaje: 44
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #20 : Aprilie 18, 2013, 08:18:17 » |
|
![Smile](http://www.infoarena.ro/forum/Smileys/default/smile.gif) ) Ok. L.E.: Am reusit dupa cateva zile de inmultit matrici pe la scoala sa ajung la un rezultat. Parca ma simt mai bine decat daca mi-ati fi trantit rezultatul in fata ![Smile](http://www.infoarena.ro/forum/Smileys/default/smile.gif) ) Deci, multumesc!
|
|
« Ultima modificare: Aprilie 20, 2013, 18:16:31 de către Nicu B. »
|
Memorat
|
|
|
|
•Andrei1998
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #21 : Iulie 08, 2013, 21:51:55 » |
|
Am facut si eu problema asta si am luat pe ea 100p, explicatia este foarte bine realizata! (mai ales ca poate fi usor generalizata rezolvarea problemei pentru Fn=aFn-1+bFn-2) ![Thumb up](http://www.infoarena.ro/forum/Smileys/default/thumbsup.gif) La restrictii scrie ca "0 ≤ K ≤ 1 000 000 000." Cazul k=0 nu se afla in testele problemei desi este particular si multe surse (inclusiv prima pe care am trimis-o) dau raspuns gresit sau se blocheaza pe acest caz. Eu am tratat cazul printr-un simplu if. Cred ca ar trebui incurajata o rezolvare corecta a problemei caci in timpul unui concurs o sursa ce nu trateaza cazul k=0 poate duce la pierderea de puncte valoroase. Toate cele bune.
|
|
|
Memorat
|
|
|
|
•Magnvs
Strain
Karma: 56
Deconectat
Mesaje: 15
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #22 : Iulie 09, 2013, 19:11:22 » |
|
f[-1]= 1 si toate cazurile tale particulare dispar dar e o idee buna sa fie modificata restrictia in 1<=k<=10^9
|
|
|
Memorat
|
|
|
|
•sauron
Strain
Karma: 0
Deconectat
Mesaje: 1
|
![](/forum/Themes/default/images/post/xx.gif) |
« Răspunde #23 : Mai 07, 2014, 10:49:46 » |
|
testele dau 100 de puncte la implementarea directa ![Exclamation](http://www.infoarena.ro/forum/Smileys/default/exclamation.gif)
|
|
|
Memorat
|
|
|
|
|