infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din August 30, 2005, 22:50:12

Titlul: 091 Gard3
Scris de: Mircea Pasoi din August 30, 2005, 22:50:12

Aici puteţi discuta despre problema Gard3 (http://infoarena.ro/problema/gard3).

Titlul: 091 Gard3
Scris de: u-92 din Decembrie 04, 2005, 22:06:43

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 :mrgreen:

Titlul: Răspuns: 091 Gard3
Scris de: Marius Stroe din August 31, 2007, 11:47:58

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 ?

Titlul: Răspuns: 091 Gard3
Scris de: Dan H Alexandru din Octombrie 24, 2013, 20:03:20

Mi se pare putin cam stransa limita de timp.