091 Gard3

[•domino]

Aici puteţi discuta despre problema Gard3.

[u-92]

cam ce complexitate se asteapta la problema asta? eu am rezolvat-o in n^4 (fara numere mari) si am folosit baza 10^9.. se poate mai bine de atat? (stiu ca solutia oficiala tot n^4 e)

later edit: nevermind, e n^4 numai ca trebuia sa ma 'zgarcesc' putin la memorie ca sa intre in timp  

[•Marius]

Daca la functia de inmultire a doua numere mari, modific asa:

Cod:

void mul(int A[], int B[])
{
	int i, j, tr, C[NR_CIFRE] = {0};

	for (i = 1; i <= A[0]; ++ i) {
		for (tr = 0, j = 1; (j <= B[0]) || (tr); ++ j, tr /= BASE)
			C[i+j-1] = (tr += C[i+j-1] + A[i] * B[j]) % BASE;
		if (C[0] < i+j-2)
			C[0] = i+j-2;
	}
	memcpy(A, C, sizeof(int) * (C[0] + 1));
}

Sa copiez exact numarul de cifre al rezultatului, am Killed by signal 11(SIGSEGV). Cu memcpy(A, C, sizeof(C)), merge. Ce poate sa fie ?

[•danalex97]

Mi se pare putin cam stransa limita de timp.