#include <stdio.h>  // printf
#include <stdlib.h> // malloc, free

typedef unsigned long long ull;
typedef unsigned int ui;

ull MAX_HEAT_LEVEL = 7712; // max heat level

typedef struct
{
	char* digits;
	ui lastDigit;
} bignum;

#define max(X,Y) ((X) > (Y) ? (X) : (Y))

#define TRUE 1
#define FALSE 0

const ui MAX_ULL_DIGIT_COUNT = 20;
const ui BASE = 10;

void init_bignum(bignum* num, ui numDigits)
{
	ui i;
	num->lastDigit = numDigits;
	// get the next biggest power of 2 above numDigits + 1, powers of 2 can be moved faster to/from ram
	numDigits = numDigits | (numDigits >> 1);
	numDigits = numDigits | (numDigits >> 2);
	numDigits = numDigits | (numDigits >> 4);
	numDigits = numDigits | (numDigits >> 8);
	numDigits = numDigits | (numDigits >> 16);
	++numDigits;
	num->digits = malloc(sizeof(char)* numDigits);
	for (i = 0; i < numDigits; ++i)
		num->digits[i] = 0;
}

void free_bignum(bignum* num)
{
	free(num->digits);
}

void print_bignum(bignum* num)
{
	int i;
	for (i = num->lastDigit - 1; i >= 0; --i)
		printf("%c", '0' + num->digits[i]);
	printf("\n");
}

void remove_leading_zeroes(bignum* num)
{
	ui trimmedZeroes = FALSE;
	while ((num->lastDigit > 0) && (num->digits[num->lastDigit] == 0))
	{
		trimmedZeroes = TRUE;
		num->lastDigit--;
	}
	if (trimmedZeroes == TRUE)
		++(num->lastDigit);
}

char get_digit(bignum* num, ui index)
{ // this is to ensure that garbage in a digit past the bignum's last digit isn't used, return 0 instead
	return index < num->lastDigit ? num->digits[index] : 0;
}

void add_bignum(bignum* a, bignum* b, bignum* ret)
{
	ui carry, i;
	char aDigit, bDigit, tmp;
	i = max(a->lastDigit, b->lastDigit) + 1;
	init_bignum(ret, i);

	carry = 0;

	for (i = 0; i < (ret->lastDigit); ++i)
	{
		aDigit = get_digit(a, i);
		bDigit = get_digit(b, i);
		tmp = (char)(aDigit + bDigit + carry);
		ret->digits[i] = tmp % BASE;
		carry = tmp / BASE;
	}
	remove_leading_zeroes(ret);
}

void subtract_bignum(bignum* a, bignum* b, bignum* ret) // this function expects the smaller bignum in b
{
	unsigned int borrow, i;
	char aDigit, bDigit;
	int v; // placeholder digit
	init_bignum(ret, max(a->lastDigit, b->lastDigit));
	for (i = 0, borrow = 0; i <= (ret->lastDigit); ++i)
	{
		aDigit = get_digit(a, i);
		bDigit = get_digit(b, i);
		v = (aDigit - borrow - bDigit);
		if (aDigit > 0)
			borrow = 0;
		if (v < 0)
		{
			v += BASE;
			borrow = 1;
		}
		ret->digits[i] = (char)v % BASE;
	}
	remove_leading_zeroes(ret);
}

void multiply_bignum(bignum* a, bignum* b, bignum* ret) // this function expects the smaller bignum to be in b
{
	ui i;
	if (b->lastDigit == 1)
	{ // normal multiplication
		ui carry;
		char aDigit, bDigit, tmp;
		i = max(a->lastDigit, b->lastDigit) + 1;
		init_bignum(ret, i);
		ret->lastDigit = i;

		carry = 0;
		bDigit = b->digits[0];

		for (i = 0; i <= (ret->lastDigit); ++i)
		{
			aDigit = get_digit(a, i);
			tmp = (char)((aDigit * bDigit) + carry);
			ret->digits[i] = tmp % BASE;
			carry = tmp / BASE;
		}
	}
	else
	{ // multiplication by 10
		init_bignum(ret, a->lastDigit + 1);
		ret->digits[0] = 0;
		for (i = 0; i < a->lastDigit; ++i)
			ret->digits[i + 1] = a->digits[i];
	}
	remove_leading_zeroes(ret);
}

void multiply_powers_of_ten_bignum(bignum* a, bignum* b, bignum* ret) // both bignums have to be a power of 10
{
	ui digitCount = (a->lastDigit + b->lastDigit) - 1;

	init_bignum(ret, digitCount); // initializes all digits to 0
	ret->digits[digitCount - 1] = 1;
}

void subtract_one_from_power_of_ten_bignum(bignum* a, bignum* ret)
{
	ui i;
	init_bignum(ret, a->lastDigit - 1);
	for (i = 0; i < a->lastDigit - 1; ++i)
		ret->digits[i] = 9;
}

void copy_bignum(bignum* src, bignum* dest)
{
	ui i;
	init_bignum(dest, src->lastDigit);
	for (i = 0; i < src->lastDigit; ++i)
		dest->digits[i] = src->digits[i];
}

void ull_to_bignum(ull s, bignum* num)
{
	init_bignum(num, MAX_ULL_DIGIT_COUNT);

	num->lastDigit = 0;

	while (s > 0)
	{
		++(num->lastDigit);
		num->digits[num->lastDigit - 1] = s % BASE;
		s /= BASE;
	}
}

ull bignum_to_ull(bignum* num)
{
	ull ret = 0;
	ull curDigVal = 1;
	ui i;
	for (i = 0; i < num->lastDigit; ++i)
	{
		ret += num->digits[i] * curDigVal;
		curDigVal *= BASE;
	}
	return ret;
}

int main()
{
	ull curLevel;                                  // the level of blocks currently being calculated. Level 1 is 10 x 10, 2 is 100 x 100 etc
	ull targetLevel;                               // last level that needs to be calculated
	ull i;                                         // fill level of blocks in curLevel
	ull d;                                         // the current diagonal
	ull s;                                         // the index into the array of the block size for the current diagonal
	ull a;                                         // intermediate value in calculation of how many edge blocks to subtract
	ull b;                                         // intermediate value in calculation of how many edge blocks to subtract
	ull c;                                         // intermediate value in calculation of how many edge blocks to subtract
	bignum curBlockWidth;                          // the width of a block currently being calculated. e.g 10, 100, 1000 etc
	bignum prevBlockWidth;                         // the width of the previous size block
	bignum blocksToAdd;                            // the number of blocks to add to the current running total   
	bignum* temp = malloc(sizeof(bignum));         // intermediate value in calculation of block sizes
	bignum fullBlockSize;                          // the size of a completely filled block at the current level
	bignum edgeBlockSubtractionFactor;             // the number of blocks to subtract (because they are on an axis and shouldn't be double counted)
	bignum blocksAfterEdgeSubtraction;             // the block count after subtracting blocks on axes
	bignum blocksAfterMultiplyingByFour;           // the block count after multiplying by 4 (because all values calculated are only for one quadrant of the space)
	bignum finalBlockCount;                        // the answer
	bignum* runningTotal = malloc(sizeof(bignum)); // stores the total when calculating curBlockSizes[i]
	bignum relevantBlockSizeMinusOne;              // the relevant quadrant block size minus one (for (0, 0))
	bignum** prevBlockSizes;                       // stores the previous block sizes
	bignum** curBlockSizes;                        // stores the current block sizes
	bignum** swapHolder;                           // stores prevBlockSizes when swapping prev and curBlockSizes
	bignum diagonals[19];                          // stores the number of tiles added at each diagonal across a block

	temp->digits = NULL; // set to null to avoid run time error when free is called on temp later

	prevBlockSizes = malloc(sizeof(bignum) * 30);
	curBlockSizes = malloc(sizeof(bignum) * 30);

	for (i = 0; i < 30; ++i)
	{
		prevBlockSizes[i] = malloc(sizeof(bignum));
		curBlockSizes[i] = malloc(sizeof(bignum));
		curBlockSizes[i]->digits = NULL; // set to null to avoid run time error when free is called on curBlockSizes[i] later
	}

	init_bignum(runningTotal, 1);
	runningTotal->digits[0] = 0;

	bignum one;
	init_bignum(&one, 1);
	one.digits[0] = 1;

	bignum four;
	init_bignum(&four, 1);
	four.digits[0] = 4;

	bignum ten;
	init_bignum(&ten, 2);
	ten.digits[0] = 0;
	ten.digits[1] = 1;

	// set up the diagonals array to contain
	//{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ui j, dif, tmp;
	for (j = 1, dif = 0; j <= 19; ++j)
	{
		bignum cur;
		tmp = j <= 10 ? j : j - (dif += 2);
		if (tmp < 10)
		{
			init_bignum(&cur, 1);
			cur.digits[0] = tmp;
		}
		else
		{ // value of 10			
			init_bignum(&cur, 2);
			cur.digits[1] = 1;
			cur.digits[0] = 0;
		}
		diagonals[j - 1] = cur;
	}

	init_bignum(&curBlockWidth, 2); // set curBlockWidth to 10
	curBlockWidth.digits[1] = 1;
	curBlockWidth.digits[0] = 0;
	copy_bignum(&curBlockWidth, &prevBlockWidth); // set prevBlockWidth to 10 also

	// fill in the block sizes for 10 x 10 blocks
	// first block has size 1, not using the 0 index of either cur or prevBlockSizes
	init_bignum(curBlockSizes[2], 1);
	curBlockSizes[2]->digits[0] = 1;
	for (i = 2; i < 20; ++i)
		add_bignum(curBlockSizes[i], &diagonals[i - 1], curBlockSizes[i + 1]);
	for (i = 20; i < 30; ++i)
	{ // set the rest equal to 100 - full block size
		bignum* cur = malloc(sizeof(bignum));
		init_bignum(cur, 3);
		cur->digits[0] = 0;
		cur->digits[1] = 0;
		cur->digits[2] = 1;
		curBlockSizes[i] = cur;
	}

	for (i = 1; i < 30; ++i)
	{
		bignum* cur = malloc(sizeof(bignum));
		init_bignum(cur, 1);
		cur->digits[0] = 0;
		prevBlockSizes[i] = cur;
	}

	if (MAX_HEAT_LEVEL < 9)
	{
		bignum maxHeatLevel;
		init_bignum(&maxHeatLevel, 1);
		maxHeatLevel.digits[0] = MAX_HEAT_LEVEL + 1;
		
		bignum answer;
		subtract_bignum(curBlockSizes[MAX_HEAT_LEVEL + 2], &maxHeatLevel, &answer);

		bignum answer2;
		multiply_bignum(&answer, &four, &answer2);

		add_bignum(&one, &answer2, &finalBlockCount);
	}
	else
	{
		targetLevel = (MAX_HEAT_LEVEL / 9);
		curLevel = 1;

		while (curLevel <= targetLevel)
		{ // swap arrays
			swapHolder = prevBlockSizes;
			prevBlockSizes = curBlockSizes;
			curBlockSizes = swapHolder;
			for (i = 1; i <= 29; ++i)
			{
				free_bignum(curBlockSizes[i]);
				init_bignum(curBlockSizes[i], 1);
				curBlockSizes[i]->digits[0] = 0;
			}
			multiply_powers_of_ten_bignum(&curBlockWidth, &curBlockWidth, &fullBlockSize);
			for (i = 1; i < 28; ++i)
			{
				for (d = 0, s = i + 9; d < i && d < 19; ++d, --s)
				{ // this section multiplies the number of diagonal smaller blocks times their size
			      // and adds the result to the running total
					multiply_bignum(s < 30 ? prevBlockSizes[s] : &fullBlockSize,
						&diagonals[d], &blocksToAdd);

					add_bignum(curBlockSizes[i], &blocksToAdd, temp);

					free_bignum(&blocksToAdd);

					free_bignum(curBlockSizes[i]);

					copy_bignum(temp, curBlockSizes[i]);

					free_bignum(temp);
				}
			}
			copy_bignum(&curBlockWidth, &prevBlockWidth);
			multiply_powers_of_ten_bignum(&curBlockWidth, &ten, &curBlockWidth);
			multiply_powers_of_ten_bignum(&curBlockWidth, &curBlockWidth, curBlockSizes[29]); // full block size
			subtract_one_from_power_of_ten_bignum(curBlockSizes[29], curBlockSizes[28]); // full block minus one in the corner
			++curLevel;
		}
		// the next section multiplies the block number by 4 and subtracts tiles on the axes, then adds one for (0, 0)
		a = (curLevel - 1) * 9;

		b = ((MAX_HEAT_LEVEL + 2) - a);

		c = (bignum_to_ull(&prevBlockWidth) * b) - 2;

		ull_to_bignum(c * 4, &edgeBlockSubtractionFactor);

		subtract_bignum(curBlockSizes[(MAX_HEAT_LEVEL - a) + 2], &one, &relevantBlockSizeMinusOne);

		multiply_bignum(&relevantBlockSizeMinusOne, &four, &blocksAfterMultiplyingByFour);

		subtract_bignum(&blocksAfterMultiplyingByFour, &edgeBlockSubtractionFactor, &blocksAfterEdgeSubtraction);

		add_bignum(&blocksAfterEdgeSubtraction, &one, &finalBlockCount);
	}
	print_bignum(&finalBlockCount);
	return 0;
}