1140 Sir4

[•savim]

Aici puteţi discuta despre problema Sir4.

[•SpiderMan]

Vezi ca solutia este 7 10 2 8 15 (ai uitat un 5 si ai pus doar 1).

[•Steve]

Am si eu nevoie de un pic de ajutor la problema asta. Am gasit ca bugul provine la procedura de aflare a perioadei (perioada trece de M):

Cod:

void Find_Period ()
{
        Perioada = 1;
        i = (A * X0 + B) % M;
	while (i != X0)
	{
		i = (A * i + B) % M;
		Perioada++;
	}
}

Am demonstrat intai ca intregul graf X0 -> X1 -> X2 ->... este finit (si ciclic) si ca este defapt de forma X0, X1, X2 ... Xn, X0 din faptul ca daca 2 noduri pointeaza la un acelasi nod (exista o bucla interioara) atunci vom avea Xk == (A * Xi + B) % M == (A * Xj + B) % M, deci A * (Xj - Xi) = n * M, unde n este un nr. intreg, deci Xj - Xi == 0. Deci ar trebui ca sirul sa se inchida fara a exista vreo bucla interioara. Ce gresesc?  

LE: NVM, dupa vreo 2 ore, mi-am dat seama ca era de la un long long declarat int. 

[•lucian666]

Salutare
urmatoarea restricite: 0 ≤ Pi < 10^10000 am mai vazut-o in cateva probleme ....trebuie sa folosesc numere mari? ma gandesc ca 10 ^ 10000 e cam mare .
Multumesc anticipat!!!

[•soriyn]

Da, trebuie. Gandeste-te ca numarul ala are 10 000 de cifre iar long long poate retine un numar de maxim 18 cifre(aproximativ).

[•lucian666]

Da, trebuie. Gandeste-te ca numarul ala are 10 000 de cifre iar long long poate retine un numar de maxim 18 cifre(aproximativ).

deci p are maxim 10000 cifre
atunci cand calculez termenii si raspund la intrebari in O(1) cum as putea retine eu atatea pozitii? ?

[•tzipleatud]

Pai sirul X are o perioada, adica exista un i>=1 pentru care X_i=X₀, si atunci tu memorezi valorile X_j pentru j<i. In asa fel cand citesti un p pentru care trebuie sa afli X_p sti ca X_p=X_(p%i), deci tot ce trebuie sa faci e sa calculezi p%i. Bafta!

[•ctlin04]

Ce optimizari ati mai facut ca sa intre ultimele 2 teste 

[•alexalghisi]

Limita de timp este putin cam mica , inclusiv solutia oficiala de la Moisil ia 80 de puncte cu doua TLEuri 

[•klamathix]

Am pus limita la 0.6.

[•alevasluiale]

Salutare . Am nevoie de putin ajutor la aceasta problema , dupa vreo 15 surse trimise tot 40 iau cu 2 incorect si 4 killed by signal 11 si nu-mi dau seama de ce, pe toate testele de la moisil ruleaza perfect si afiseaza rezultatul corect fara sa se buseasca. Daca are timp cineva sa se uite putin peste sursa mea as raman dator : http://www.infoarena.ro/job_detail/1169832?action=view-source

LE: Mi-am dat seama

[•cojocarugabi]

cam mica e memoria am folosit un vector de int de marimea perioadei si altul char pentru query si aiu mle

[•klamathix]

Probabil ideea era să ai memorie constantă relativ la lungimea perioadei.