infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Mai 23, 2005, 14:15:37

Titlul: 063 Bombar
Scris de: Mircea Pasoi din Mai 23, 2005, 14:15:37

Aici puteÅ£i discuta despre problema Bombar (http://infoarena.ro/problema/bombar).

Titlul: 063 Bombar
Scris de: Andrei Grigorean din Iunie 07, 2005, 23:01:09

daca am o recurenta de grad 2, cum scot formula? :oops:

Titlul: 063 Bombar
Scris de: Mircea Pasoi din 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)

Titlul: 063 Bombar
Scris de: Cosmin Negruseri din 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.

Titlul: 063 Bombar
Scris de: Cosmin Negruseri din Iunie 08, 2005, 20:52:35

Daca vrei sa vezi cum se deduce formula pentru recurente de gradul doi te poti uita aici: http://mathworld.wolfram.com/LinearRecurrenceEquation.html

Titlul: <none>
Scris de: Filip Cristian Buruiana din 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 :oops: ). Cu ridicarea la putere in timp logaritmic a unei matrici de genu din "iepuri"

bubbleSORT

Titlul: 063 Bombar
Scris de: Cosmin Negruseri din 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 ...

Titlul: ?
Scris de: Filip Cristian Buruiana din 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?

Titlul: Re: ?
Scris de: Mircea Pasoi din Iunie 09, 2005, 18:13:35

Citat din mesajul lui: filipb

[-X
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.... :-'

Titlul: 063 Bombar
Scris de: Andrei Grigorean din 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:

Titlul: 063 Bombar
Scris de: cristi8 din August 23, 2005, 16:43:39

Citat din mesajul lui: wefgef

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ă

Titlul: 063 Bombar
Scris de: Oltean Dorin din August 23, 2005, 22:48:16

Citat

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

Titlul: 063 Bombar
Scris de: Andrei Grigorean din August 24, 2005, 15:18:37

am auzit de ea. e scrisa de francu, nu?

nu stie nimeni unde as putea-o gasi?

Titlul: 063 Bombar
Scris de: Vlad Berteanu din 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 ! :wink:

Titlul: 063 Bombar
Scris de: Gogu Marian din 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.

Titlul: 063 Bombar
Scris de: Vlad Berteanu din 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...

:-k

Titlul: 063 Bombar
Scris de: Gogu Marian din 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:

Cod:

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.

Titlul: 063 Bombar
Scris de: Vlad Berteanu din Noiembrie 08, 2005, 21:57:30

:o Ma... Tu sigur nu ai facut ceva descantece la liniile alea de cod ? Exact la fel fac si eu, chiar redusesem la un singur for procedura si luam TLE... Am inlocuit cu liniile tale si timpul e sub 0.6... =D> =D> =D>

Titlul: 063 Bombar
Scris de: Gogu Marian din 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 . :D

Titlul: 063 Bombar
Scris de: Andrei Grigorean din Noiembrie 17, 2005, 11:45:02

si eu cred ca a facut descantece :P

Titlul: RÄƒspuns: 063 Bombar
Scris de: Rus Cristian din 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?

Titlul: Răspuns: 063 Bombar
Scris de: Adrian Budau din 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:

Cod:

16->954437182
235-> 67746279303732470299079800993775310454613674971028019766908788186314490859803941408868095282875861796837441649610812260296869722067770248839

Multumesc anticipat!

Foloseste tag-ul [ code ] [/ code ] cand postezi teste.

Titlul: Răspuns: 063 Bombar
Scris de: Serban Andrei Stan din Martie 12, 2010, 14:05:58

Mie imi da asa (cu sursa de 100) :

Cod:

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.

Titlul: RÄƒspuns: 063 Bombar
Scris de: Adrian Budau din Martie 12, 2010, 21:08:33

Ms pentru raspuns. Am luat 100, se pare ca gresisem recurenta. :yahoo: