1300 Tamplar

[•klamathix]

Aici puteti discuta despre problema Tamplar.

[•vendetta]

Ceva idei pentru 100 ?
i-au 80 cu tle pe ultimele 2

[•Florian]

In ce baza lucrezi? Lucreaza intr-o baza mai mare. 

[•vendetta]

in baza 10.
am incercat si in 256 dar (cred ca greseala e a mea), pe testul maxim imi i`a mult mai mult decat in baza 10

[•scipianus]

Raspunsul pentru L=10000 in baza 10 are (din cate tin minte) vreo 35000 cifre. Pentru 100pct este recomandat sa faci inmultirile in baza 10^4

[•vendetta]

la fel si cu baza 10^4.

[•S7012MY]

Eu am lucrat in concurs cu o baza mai mare de 10^4 si tot nu intra in timp. Probabil trebuie sa precalculezi unele chestii

[•visanr]

Nu ai nevoie de precalculari, pur si simplu faci factorialul cu baza 10^4 si iei 100

[•Vman]

@Petru: tu pentru fiecare inmultire aloci cate un vector, il parcurgi pe tot ca sa il initializezi, si apoi il copiezi inapoi deci practic il parcurgi inca odata pe tot, faci de vreo 3-4 ori mai multe operatii decat este necesar.

Si ca observatie suplimentara nu iti recomand sa faci

Obiect ceva()
{
 Obiect a;
 bla bla bla;
 return a;
}

pt ca ai mari sanse fie sa o dai in balarii in functie de ce faci dupa, fie sa trebuiasca copiat un Obiect intreg ceea ce poate fi costisitor, pentru ca dupa iesirea din functie a este distrus, fiind alocat static.
E bine ca macar in arhiva de probleme sa incercati sa scrieti codul cap-coada, fara clase si template-uri de-a gata sau luate de prin arhiva educationala, pt ca la olimpiada aveti doar stl-ul si cam atat.

[•spatarel]

@Duta Vlad:
Eu sunt autorul clasei Huge la care ai facut referire. Cu certitudine mai poate fi imbunatatita.

Inteleg ca nu aprobi o implementare de forma:
Obiect ceva()
{
 Obiect a;
 bla bla bla;
 return a;
}
din motive de performanta.

Am doua intrebari:
(1) Cum poti implementa mai bine supraincarcarea operatorilor?
(2) La ce te referi cand spui ca "ai sanse mari sa o dai in balarii"? (presupunem constructorul de copiere implementat corect si eficient)

[•Vman]

Personal nu sunt de acord, de fapt sunt chiar impotriva supraincarcarii operatorilor. Mi se pare ca mai degraba duce la confuzii decat la un cod mai clar.

1. Respectand toata aritmetica operatiilor nu stiu daca se poate implementa mai bine. Daca vorbim de un proiect o clasa de numere mari e o abordare excelenta, dar pentru probleme de concurs se vede ca performanta nu e aceeasi. Si pana la urma intr-o problema e vorba de 2-3 operatii pe numere mari, ar trebui sa dureze maaaxim 2 minute implementarea fiecareia.

2. daca functioneaza corect constructorul de copiere nu ar trebui sa fie probleme, e doar mai lent (din nou vorbesc in contextul unui concurs de programare). Problema cu balariile e cand ai alocare dinamica in Obiect si copy-constructorul este cel default, sau cand dimensiunea variabilei Obiect depaseste limita stivei.

[•SpiderMan]

Uite sursa de 100 pct. http://infoarena.ro/job_detail/751912, am modificat doar baza 10⁴ si la oepratia de inmultire cu un numar din long long am facut int, ceea ce face mai rapide operatiile.

[•ctlin04]

Explicati-mi va rog si mie cum se face inmultirea in baza 10^4, dupa asta ar trebui de facut iarasi conversia in baza 10, care iarasi i-a ceva timp, sau nu-mi dau seama de anumite lucruri 

[•PlayLikeNeverB4]

Exact ca si la baza 10, doar ca pentru o cifra verifici daca nu depasesti 10^4 in loc de 10. La afisare trebuie sa pui niste 0-uri in fata cifrei daca valoarea ei nu are destule cifre (de exemplu, unde ai 1 vei afisa 0001).

[•ctlin04]

Ms mult acum am inteles 

[•AlexandruValeanu]

Imi poate spune si mie cineva cum imi poate da TLE pe ultimele 2 teste daca am implementat chiar si in baza 10^14 ?

[•misino]

Nu crezi ca e baza prea mare si operatiile pe long long se efectueaza mai greu?

[•AlexandruValeanu]

Si eu cred la fel dar cu orice baza mai mica iau ori WA ori TLE

[•danalex97]

@ Alexandru: Nu folosesti int in loc de long long si cred ca te complici cu codul de la inmultire. Ceva de genul ar fi mai usor:

Cod:

void mul(int A[], int B)
{
    int i, t = 0;
    for (i = 1; i <= A[0] || t; i++, t /= 10000)
        A[i] = (t += A[i] * B) % 10000;
    A[0] = i - 1;
}

Succes !

[•AlexandruValeanu]

Mersi de sugestie, am implementat-o dar tot 80p cu TLE pe ultimele 2 teste. 

[•danalex97]

Daca doresti iti pot trimite sursa mea. Totusi din cate vad ar fi in regula daca s-ar mari putin limita de timp. 

[•AlexandruValeanu]

Daca poti chiar te-as ruga sa-mi trimiti ceva corect ca de sursa mea dubioasa m-am saturat. Mersi!

[•fulgerulnegru]

Am facut rezolvarea cu java si iau doar 10p ((. E cu BigInteger si  e algoritmul standar la n factorial

[•Vman]

writer.close()

Daca nu inchizi descriptorul exista sansa ca ceea ce afisezi sa ramana in buffer