Programming Contest for Newbies 2005

[Per]

Doesn't Java come with a built-in bignum library?

Yeah, but here a very restricted variant of an old version of Java is used, coupled with a buggy compiler which produces incorrect code for some perfectly fine constructs. So for instance, the BigInteger/BigDecimal classes are not allowed (or do not exist, I forget which).

[Larry]

Ya, Problem A would've been trivial using Java.. real Java anyhow..

[Destination Goa]

Check this (written during the contest). Just compare matching leading digits, or subtract without comparison at righter offset. It's O(N*(N-M)*B) division for base B (10 here). Long division is very very simple thing when you have dig_cmp and dig_sub as sub-routines.

Code: Select all

void clean(int* d, int& nd)
{
	memset(d, 0, nd*sizeof(d[0]));
}

int dig_cmp(int* d1, int* d2, int nd)
{
	int i;
	for(i=nd-1;i>=0;i--)
	{
		if(d1[i] != d2[i])
			return d1[i] - d2[i];
	}

	return 0;
}

void dig_sub(int* d1, int* d2, int nd)
{
	int i;
	for(i=0;i<nd;i++)
	{
		d1[i] -= d2[i];

		if(d1[i] < 0)
			d1[i] += 10, d1[i+1]--;
	}
}

int qd[1024];
int nqd;

// qd|nqd = d1|nd1 / d2|nd2
// d1|nd1 = d1|nd1 % d2|nd2
void div(int* d1, int& nd1, int* d2, int nd2)
{
	clean(qd, nqd);

	if(nd1 < nd2)
		return;

	nqd = nd1 - nd2 + 1;

	for(;;)
	{
		int off = nd1 - nd2;

		if(off>=0 && dig_cmp(d1+off, d2, nd2) >= 0)
			dig_sub(d1+off, d2, nd2), qd[off]++;
		else if(off>=1)
			dig_sub(d1+off-1, d2, nd2), qd[off-1]++;
		else
			break;

		while(nd1 && d1[nd1-1]==0)
			nd1--;
	}

	while(nqd && qd[nqd-1]==0)
		nqd--;
}

[/code]

[Observer]

Hey, wouldn't that be too much a hint?

Never mind. This is supposed to be a give-away question anyway. Division of two big numbers is really not hard...

[Destination Goa]

Yes, it's not hard. But I still remember myself when I debugged this routine for about 15-20 minutes each contest I needed it. So, here is its state when I don't make anymore mistakes with long division. In fact, if this works for 144/12 and for 9801/99, it usually works for all.

Other ways of writing always gave me some WA or TL only with tricky input, and of course only after submission. The way I suggested it here, it either fails the simplest test or works for any data.

It's not a hint, it's a gift