Re: [acm-valogato] projecteuler 337

Csá! Első nekifutásra: Legyen f(x) az x-el kezdődő, legfeljebb 20.000.000-val végződő, a második tulajdonságnak eleget tevő sorozatok száma: - 20.000.000-nél nagyobb számokra ez 0, különben: - f(x) = 1 + szumma(f(y)), ahol fi(x) < fi(y) < x Már csak egy hatékony módszert kéne találni a szumma kiszámítására. Legyen A tömb, A(x) = szumma(f(y)), ahol fi(y) = x. Elég lenne, ha hatékonyan tudnánk 'A' elemeit módosítani és egy intervallumon az elemek összegét lekérdezni. A Fenwick-fa megoldja mindkettőt log(n) időben. A megoldás tehát: elindulunk 20.000.000-tól lefelé egy üres Fenwick-fával. Minden x indexre kiszámítjuk f(x)-et (1+a fában a fi(x)..x nyílt intervallum összege), majd a fában megnöveljük a fi(x)-hez tartozó értékeket f(x)-el. A megoldás f(6), a futásidő O( n*log(n) ). (Megj.: A számítások maradékosztály felett történnek, és a prímek kihagyhatóak.) Vélemény? Üdv, Peti u.i.: nem unatkozom, csak vizsgára készülök Nekem úgy tűnik, hogy Fenwick-fával megoldható. 2011. május 30. 15:59 NGG írta, &lt;ngg(a)ngg.hu&gt;hu>: