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, <ngg@ngg.hu>:
Hi!

Talaltam egy szerintem nagyon kiraly feladatot, oldjatok meg :P
http://projecteuler.net/index.php?section=problems&id=337

ha vkit a matekos resze elriaszt, az fogja fel ugy hogy amit ott
fi-vel jelol fuggveny, az egy elore megadott vektor, nem kell rola
kihasznalni semmilyen tulajdonsagot, csak minden n-re fel van sorolva
fi(n)

elso megoldom (nagyon butus) 8 magon futott 72 orat :P
masodik megoldom, amire azthittem hogy vegre rajottem hogyan kell es
nagyon fasza, az futott 5 orat 1 magon
ezekutan galad modon elolvastam hogy mas hogyan csinalta meg, es
csinaltam egy harmadik megoldot azok alapjan, kevesebb mint 1 perc
alatt lefut nagyon siman, ezt kene kitalalnotok

ngg
_______________________________________________
acm-valogato mailing list
acm-valogato@sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato