801 Recurenta

[•wefgef]

Aici puteti discuta despre problema Recurenta.

[•Horica]

Cumva elementele din D trec de long long?
Ca imi da killed by signal si nu stiu unde a-si putea avea probleme cu memoria.

[•wefgef]

E de la citire. Trebuie sa pui & inainte de numele variabilei: scanf("%d", &n);

[•Horica]

Mersi
m-am grabit si am uitat sa pun
si nu mi-a dat nici eror

[•SpiderMan]

Imi puteti da cateva teste, va rog
[LE] imi puteti spune cum pot optimiza, am facut cu numere mari si am 40 pct. din cauza memoriei ....

[•Florian]

Foloseste o baza mai mare pentru operatiile pe numere mari. Vad ca eu am folosit 10 ^ 9. Iar deque-ul, trebuie sa il tii dinamic [ poti folosi deque din STL ].

[•SpiderMan]

Am luat 100 fara deque .... doar cu o baza mai mare

[•SpiderMan]

Am incercat sa refact pb. folosind un deque , dar nu stiu, la mine pe Pc imi merge orice test ( am facut teste cu sursa de 100 pct ) , dar aici imi da incorect .... Care sa fie problema ?

[•dariusdarius]

Imi puteti spune si mie cat da pe testele:

1000 20
10000 1000 ?

mie imi da:
6061446318778313137136775020482719917352618716033276537975378557927425
respectiv
7659711931412362235013830992583100008231141863988257964981975126299562382214508392048042027885944222653446967978944298759089129504795404255226628712665642500433201664066622579919649736202238390876748603836808223536364963987061928528170183342096263981046074314740066532981072895425938096589993635276347217750768419875364312449025

Nu am nici o idee de ce nu imi da. Am folosit numere mari pe baza 10^9 si un vector circular doar cu k elemente. Pot avea mai mult de 4000*9 cifre numerele?

[•romircea2010]

Si eu am folosit baza 10^9 la calcule si am declarat vectorii de 2800.
Vezi sa ai grija daca nu ai vectorii long long sa pui macar unsigned int ca e posibil sa depaseasca la adunare cand aduni la transport.
Pe testele

Cod:

1000 20

trebuie sa dea

Cod:

194066487527903105737948928252375622545469717012214359895206056585227436625505425163864144573012864365700468199558901272705615645803499703652393803870912035846906039795084174500773448912813172245671155653158930257810741924710795826997648499744793584558728085314076552644028998543537975378557927425

iar pe

Cod:

10000 1000

trebuie sa dea

Cod:

1860057903778844423181595300495822540412462200738543986011148445577848210955128493768178969018022053708594094348519805877623467830849131105741610821463989981351910340242278810288320015061010687751700581465389740926935845544174187666298008503016548655036866509395263838863883710312904625516934062101877664898997356574926627866387418715102505518011028644160878273360554908868528073989920008619862291541710361941144330716023271212143410789048037207503040405625755367406078367554424650274398702923737073562110738590856291027720912336183601059745825341012130557977946931915832103342350285163755915440428844308416462712815290905577679213793317239641523175379336436522829653899507817846720867244424101863725252364083595856338017015375011493882253577471437158045064707202511809554489007657153394283938639051682637165053670011136338776898064452478412765539956108526845807827427905501771946480107553675986514097892028469058893409076817469578900610441917743536149031967211261207580810502546525588050128254096730581593285342225448557854329821225352782372176664817733315661225362303350555188577092563668562412123158420204416638780402850184615537248284715737316654235726570002967370550999740884302977667492940126918048531808383572743879426552890283232605306203165319613905713836676070362176112264494039605357893586573690747147694145406690208303947890249574980359075837517200103304020406812076526594291542043332971269077144149452981123716946937520226974019454068954247966807498119964093764281360945118751976462322603115775794056753835362707174413880986860471536201619611595480869060416715036719546161241549313105486276266097897463114866261273766022980342943349795232245056417488149658134910862203708082125336981473373935085016580452414060361182670939066175101530837114355394844814764217281136116486650334004012340301086430926764965156064221819741695221839402190372366842906752392784178068996676535879090040067517359321779340637151110290371539023266808952932289481700548730110809738821658228754086717341439294255504239405034279880461404795623248203557089835628265626545038755382405332107994216946693114265430538549651998684822376197648760221934081432203689091552080694106806149253620862566120567987144951269903895332888012583998672574589878569596322484773555694053617032087745042591089469577519769607576716601978815027397094810485131549387859842074273793081135992323696249733752562444555193305581620374826709566213931589800058585938784254178058265911326236874216219904617377447036070192509393869187155581761656541557423487847398652467238755123989818660821493709222781437687866836865943161787345065550131617208324608883063040426022892197088702066254440088734525909071167547532171914408106098396015535502245008984019875364312449025

Bafta