•domino
|
|
« : Mai 23, 2005, 14:15:37 » |
|
Aici puteţi discuta despre problema Bombar.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #1 : Iunie 07, 2005, 23:01:09 » |
|
daca am o recurenta de grad 2, cum scot formula?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•domino
|
|
« Răspunde #2 : Iunie 07, 2005, 23:26:57 » |
|
Nu este nici o formula (cel putin nu cred eu). Daca ai probleme cu limita de timp, atunci incearca sa rezolvi problema "Iepuri" (daca nu stii s-o rezolvi gasesti un articol cu solutia sa pe info.devnet.ro)
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #3 : Iunie 08, 2005, 00:27:37 » |
|
E formula de genu a*x^n + b*y^n unde x si y sunt irationale ... deci formula nu te prea ajuta.
|
|
|
Memorat
|
|
|
|
|
•filipb
|
|
« Răspunde #5 : Iunie 09, 2005, 12:04:32 » |
|
Problema cere determinarea nr. de arbori partiali ai unui graf scara cu N noduri pe fiecare rand.. Formula foloseste si numere irationale... Da, merge ca in "iepuri" ( pe care inca nu am apucat sa o implementez k lumea ). Cu ridicarea la putere in timp logaritmic a unei matrici de genu din "iepuri" bubbleSORT
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #6 : Iunie 09, 2005, 12:21:05 » |
|
Tu repeti ce s-a zis mai sus sau mi se pare mie? Ori ai gasit acuma problema in Tomescu si nu vezi ca solutia se bazeaza pe rezolvarea unei recurente de gradul 2, adica ce am zis io mai sus ... Si despre iepuri a zis domino in primul post ...
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #7 : Iunie 09, 2005, 15:26:04 » |
|
Ei na... MS MULT! Eu am implementat recurenta ( pe numere mari ) si mi-a luat doar primele 4 teste, la restu' Time Limit Exceeded! Probabil trebuia sa folosesc o baza mai mare... (10000?) O stiam de mult. Si ce? Multe probleme date la baraje si la nationale (chiar si anu asta) sunt din Tomescu.... SI CE?
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #8 : Iunie 09, 2005, 18:13:35 » |
|
Ei na... MS MULT! Eu am implementat recurenta ( pe numere mari ) si mi-a luat doar primele 4 teste, la restu' Time Limit Exceeded! Probabil trebuia sa folosesc o baza mai mare... (10000?) O stiam de mult. Si ce? Multe probleme date la baraje si la nationale (chiar si anu asta) sunt din Tomescu.... SI CE? N-ai inteles despre ce e vorba.. ti s-a zis doar ca post-ul tau nu zicea nimic nou fata de ce se zisese deja inainte, asa ca inainte sa post-ezi ceva citeste ce s-a scris deja. Cat despre Tomescu, n-a zis nimeni ca e rau sau ceva de genul, poate chiar o sa facem un articol pe baza problemelor de acolo....
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #9 : August 23, 2005, 14:00:51 » |
|
ms mult. am invatat si eu cum sa ridic la putere o matrice in timp logaritmic, doar k am probleme cu implementarea operatiilor pe numere mari. :cry:
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
cristi8
Vizitator
|
|
« Răspunde #10 : August 23, 2005, 16:43:39 » |
|
cum se conjuga verbul "a coace" la perfectul simplu? eu copsei tu copseişi el/ea coapse noi copserăm voi copserăţi ei/ele copseră
|
|
|
Memorat
|
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #11 : August 23, 2005, 22:48:16 » |
|
am probleme cu implementarea operatiilor pe numere mari citeste o carte :lol: este una cu psihologia concursurilor de informatica are si operatii pe numere mari in legatura cu verbul la persoana a doua nu e copsesi
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
•wefgef
|
|
« Răspunde #12 : August 24, 2005, 15:18:37 » |
|
am auzit de ea. e scrisa de francu, nu?
nu stie nimeni unde as putea-o gasi?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•vladcyb1
|
|
« Răspunde #13 : August 24, 2005, 18:37:25 » |
|
Da e buna cartea. Eu o am de la PACO. Dar de ce nu te uiti la articole si o sa gasesti unul scris de domino, parca se numese "Multe shmenuri in C++" si acolo prezinta operatii pe numere mari, idei de la Radu Berinde. E bun articolul !
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #14 : Septembrie 13, 2005, 20:05:39 » |
|
Pentru cei care nu au reusit sa implementeze o ridicare la putere in timp logaritmic, garantez ca merge o implementare directa a recurentei de gradul 2. Totusi, ca sa intre in timp trebuie sa faci mai multe optimizari la operatiile pe numere mari (de exemplu, folosirea unei baze cat mai mari, cam 10^8, si cand reactualizezi numarul, incearca sa nu faci impartiri). Asa poti sa intri in 0.5 secunde pe orice test. Nu ar trebui sa nu merga, pentru ca asimptotic, daca nu folosesti un algoritm super avansat de inmultire, ca Karatsuba sau FFT, tot O(N^2) ai complexitate.
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #15 : Noiembrie 08, 2005, 12:38:05 » |
|
Cum ai reusit tu sa implementezi recurentza direct ? Pt n=20000 numaul are cam 1400*9 de cifre daca faci in baza 1 miliard. Programul arata cam asa: for i:=3 to n do v :=numere mari (O(1400))
=> 28 milioane de operatii
Ziceai de optimizari... Ce optimizari ca nu fac impartiri nimic, doar o adunare pe numere mari...
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #16 : Noiembrie 08, 2005, 21:24:51 » |
|
Vorbeam de impartirile care trebuie sa le faci atunci cand reactualizezi numarul tau mare. O impartire se face de 10 ori mai incet decat o adunare sau inmultire pe numere intregi (e ceva de procesor, nu stiu de ce). Uite bucata esentiala din sursa mea: procedure calc(var a,b,c:numar); var i:longint; begin for i:=1 to b[0] do c[i]:=x*b[i]-y*a[i]; {recurenta, dar nu zic x si y} c[0]:=b[0]; for i:=1 to c[0] do begin while c[i]>=base do begin inc(c[i+1]); dec(c[i],base); end; if (c[i]<0) then begin inc(c[i],base); dec(c[i+1]); end; end; if c[c[0]+1]>0 then inc(c[0]); end;
Chiar daca e in pascal, cu cateva mici trucuri, sursa imi merge in 0.3 secunde pentru n=20.000.
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #17 : Noiembrie 08, 2005, 21:57:30 » |
|
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #18 : Noiembrie 08, 2005, 22:22:15 » |
|
Am irosit cateva ore din viata mea pentru a ajunge la codul asta. E ce se intampla cand esti in vacanta la tara si te plictisesti rau de tot .
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #19 : Noiembrie 17, 2005, 11:45:02 » |
|
si eu cred ca a facut descantece
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•crus
Strain
Karma: 3
Deconectat
Mesaje: 44
|
|
« Răspunde #20 : Mai 19, 2008, 13:39:08 » |
|
nu prea ma prind ce e pe aici: pentru n=4 va da 54 n=5 va da 189?
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #21 : Martie 12, 2010, 10:53:01 » |
|
Mie pentru 4 imi da 58 si pentru 5 imi da 229 Imi poate spune cineva daca sunt corecte si acestea si urmatoarele: 16->954437182 235-> 67746279303732470299079800993775310454613674971028019766908788186314490859803941408868095282875861796837441649610812260296869722067770248839
Multumesc anticipat! Foloseste tag-ul [ code ] [/ code ] cand postezi teste.
|
|
« Ultima modificare: Martie 12, 2010, 16:55:02 de către Paul-Dan Baltescu »
|
Memorat
|
|
|
|
•savim
|
|
« Răspunde #22 : Martie 12, 2010, 14:05:58 » |
|
Mie imi da asa (cu sursa de 100) : 16 -> 408855776 235 -> 73804534825890393758958534554281659036254934031449983136927666079997660107220317885305632560044534873988231090645656846779386438574191
Apropo, pentru 4 trebuie sa dea 56 iar pentru 5 raspunsul este 209. Spor la treaba! Foloseste tag-ul [ code ] [/ code ] cand postezi teste.
|
|
« Ultima modificare: Martie 12, 2010, 16:55:42 de către Paul-Dan Baltescu »
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #23 : Martie 12, 2010, 21:08:33 » |
|
Ms pentru raspuns. Am luat 100, se pare ca gresisem recurenta.
|
|
|
Memorat
|
|
|
|
|