fork(12) download
copy 
  1. #include <stdio.h>  // printf
  2. #include <stdlib.h> // malloc, free
  3.  
  4. typedef unsigned long long ull;
  5. typedef unsigned int ui;
  6.  
  7. ull MAX_HEAT_LEVEL = 7712; // max heat level
  8.  
  9. typedef struct
  10. {
  11. 	char* digits;
  12. 	ui lastDigit;
  13. } bignum;
  14.  
  15. #define max(X,Y) ((X) > (Y) ? (X) : (Y))
  16.  
  17. #define TRUE 1
  18. #define FALSE 0
  19.  
  20. const ui MAX_ULL_DIGIT_COUNT = 20;
  21. const ui BASE = 10;
  22.  
  23. void init_bignum(bignum* num, ui numDigits)
  24. {
  25. 	ui i;
  26. 	num->lastDigit = numDigits;
  27. 	// get the next biggest power of 2 above numDigits + 1, powers of 2 can be moved faster to/from ram
  28. 	numDigits = numDigits | (numDigits >> 1);
  29. 	numDigits = numDigits | (numDigits >> 2);
  30. 	numDigits = numDigits | (numDigits >> 4);
  31. 	numDigits = numDigits | (numDigits >> 8);
  32. 	numDigits = numDigits | (numDigits >> 16);
  33. 	++numDigits;
  34. 	num->digits = malloc(sizeof(char)* numDigits);
  35. 	for (i = 0; i < numDigits; ++i)
  36. 		num->digits[i] = 0;
  37. }
  38.  
  39. void free_bignum(bignum* num)
  40. {
  41. 	free(num->digits);
  42. }
  43.  
  44. void print_bignum(bignum* num)
  45. {
  46. 	int i;
  47. 	for (i = num->lastDigit - 1; i >= 0; --i)
  48. 		printf("%c", '0' + num->digits[i]);
  49. 	printf("\n");
  50. }
  51.  
  52. void remove_leading_zeroes(bignum* num)
  53. {
  54. 	ui trimmedZeroes = FALSE;
  55. 	while ((num->lastDigit > 0) && (num->digits[num->lastDigit] == 0))
  56. 	{
  57. 		trimmedZeroes = TRUE;
  58. 		num->lastDigit--;
  59. 	}
  60. 	if (trimmedZeroes == TRUE)
  61. 		++(num->lastDigit);
  62. }
  63.  
  64. char get_digit(bignum* num, ui index)
  65. { // this is to ensure that garbage in a digit past the bignum's last digit isn't used, return 0 instead
  66. 	return index < num->lastDigit ? num->digits[index] : 0;
  67. }
  68.  
  69. void add_bignum(bignum* a, bignum* b, bignum* ret)
  70. {
  71. 	ui carry, i;
  72. 	char aDigit, bDigit, tmp;
  73. 	i = max(a->lastDigit, b->lastDigit) + 1;
  74. 	init_bignum(ret, i);
  75.  
  76. 	carry = 0;
  77.  
  78. 	for (i = 0; i < (ret->lastDigit); ++i)
  79. 	{
  80. 		aDigit = get_digit(a, i);
  81. 		bDigit = get_digit(b, i);
  82. 		tmp = (char)(aDigit + bDigit + carry);
  83. 		ret->digits[i] = tmp % BASE;
  84. 		carry = tmp / BASE;
  85. 	}
  86. 	remove_leading_zeroes(ret);
  87. }
  88.  
  89. void subtract_bignum(bignum* a, bignum* b, bignum* ret) // this function expects the smaller bignum in b
  90. {
  91. 	unsigned int borrow, i;
  92. 	char aDigit, bDigit;
  93. 	int v; // placeholder digit
  94. 	init_bignum(ret, max(a->lastDigit, b->lastDigit));
  95. 	for (i = 0, borrow = 0; i <= (ret->lastDigit); ++i)
  96. 	{
  97. 		aDigit = get_digit(a, i);
  98. 		bDigit = get_digit(b, i);
  99. 		v = (aDigit - borrow - bDigit);
  100. 		if (aDigit > 0)
  101. 			borrow = 0;
  102. 		if (v < 0)
  103. 		{
  104. 			v += BASE;
  105. 			borrow = 1;
  106. 		}
  107. 		ret->digits[i] = (char)v % BASE;
  108. 	}
  109. 	remove_leading_zeroes(ret);
  110. }
  111.  
  112. void multiply_bignum(bignum* a, bignum* b, bignum* ret) // this function expects the smaller bignum to be in b
  113. {
  114. 	ui i;
  115. 	if (b->lastDigit == 1)
  116. 	{ // normal multiplication
  117. 		ui carry;
  118. 		char aDigit, bDigit, tmp;
  119. 		i = max(a->lastDigit, b->lastDigit) + 1;
  120. 		init_bignum(ret, i);
  121. 		ret->lastDigit = i;
  122.  
  123. 		carry = 0;
  124. 		bDigit = b->digits[0];
  125.  
  126. 		for (i = 0; i <= (ret->lastDigit); ++i)
  127. 		{
  128. 			aDigit = get_digit(a, i);
  129. 			tmp = (char)((aDigit * bDigit) + carry);
  130. 			ret->digits[i] = tmp % BASE;
  131. 			carry = tmp / BASE;
  132. 		}
  133. 	}
  134. 	else
  135. 	{ // multiplication by 10
  136. 		init_bignum(ret, a->lastDigit + 1);
  137. 		ret->digits[0] = 0;
  138. 		for (i = 0; i < a->lastDigit; ++i)
  139. 			ret->digits[i + 1] = a->digits[i];
  140. 	}
  141. 	remove_leading_zeroes(ret);
  142. }
  143.  
  144. void multiply_powers_of_ten_bignum(bignum* a, bignum* b, bignum* ret) // both bignums have to be a power of 10
  145. {
  146. 	ui digitCount = (a->lastDigit + b->lastDigit) - 1;
  147.  
  148. 	init_bignum(ret, digitCount); // initializes all digits to 0
  149. 	ret->digits[digitCount - 1] = 1;
  150. }
  151.  
  152. void subtract_one_from_power_of_ten_bignum(bignum* a, bignum* ret)
  153. {
  154. 	ui i;
  155. 	init_bignum(ret, a->lastDigit - 1);
  156. 	for (i = 0; i < a->lastDigit - 1; ++i)
  157. 		ret->digits[i] = 9;
  158. }
  159.  
  160. void copy_bignum(bignum* src, bignum* dest)
  161. {
  162. 	ui i;
  163. 	init_bignum(dest, src->lastDigit);
  164. 	for (i = 0; i < src->lastDigit; ++i)
  165. 		dest->digits[i] = src->digits[i];
  166. }
  167.  
  168. void ull_to_bignum(ull s, bignum* num)
  169. {
  170. 	init_bignum(num, MAX_ULL_DIGIT_COUNT);
  171.  
  172. 	num->lastDigit = 0;
  173.  
  174. 	while (s > 0)
  175. 	{
  176. 		++(num->lastDigit);
  177. 		num->digits[num->lastDigit - 1] = s % BASE;
  178. 		s /= BASE;
  179. 	}
  180. }
  181.  
  182. ull bignum_to_ull(bignum* num)
  183. {
  184. 	ull ret = 0;
  185. 	ull curDigVal = 1;
  186. 	ui i;
  187. 	for (i = 0; i < num->lastDigit; ++i)
  188. 	{
  189. 		ret += num->digits[i] * curDigVal;
  190. 		curDigVal *= BASE;
  191. 	}
  192. 	return ret;
  193. }
  194.  
  195. int main()
  196. {
  197. 	ull curLevel;                                  // the level of blocks currently being calculated. Level 1 is 10 x 10, 2 is 100 x 100 etc
  198. 	ull targetLevel;                               // last level that needs to be calculated
  199. 	ull i;                                         // fill level of blocks in curLevel
  200. 	ull d;                                         // the current diagonal
  201. 	ull s;                                         // the index into the array of the block size for the current diagonal
  202. 	ull a;                                         // intermediate value in calculation of how many edge blocks to subtract
  203. 	ull b;                                         // intermediate value in calculation of how many edge blocks to subtract
  204. 	ull c;                                         // intermediate value in calculation of how many edge blocks to subtract
  205. 	bignum curBlockWidth;                          // the width of a block currently being calculated. e.g 10, 100, 1000 etc
  206. 	bignum prevBlockWidth;                         // the width of the previous size block
  207. 	bignum blocksToAdd;                            // the number of blocks to add to the current running total   
  208. 	bignum* temp = malloc(sizeof(bignum));         // intermediate value in calculation of block sizes
  209. 	bignum fullBlockSize;                          // the size of a completely filled block at the current level
  210. 	bignum edgeBlockSubtractionFactor;             // the number of blocks to subtract (because they are on an axis and shouldn't be double counted)
  211. 	bignum blocksAfterEdgeSubtraction;             // the block count after subtracting blocks on axes
  212. 	bignum blocksAfterMultiplyingByFour;           // the block count after multiplying by 4 (because all values calculated are only for one quadrant of the space)
  213. 	bignum finalBlockCount;                        // the answer
  214. 	bignum* runningTotal = malloc(sizeof(bignum)); // stores the total when calculating curBlockSizes[i]
  215. 	bignum relevantBlockSizeMinusOne;              // the relevant quadrant block size minus one (for (0, 0))
  216. 	bignum** prevBlockSizes;                       // stores the previous block sizes
  217. 	bignum** curBlockSizes;                        // stores the current block sizes
  218. 	bignum** swapHolder;                           // stores prevBlockSizes when swapping prev and curBlockSizes
  219. 	bignum diagonals[19];                          // stores the number of tiles added at each diagonal across a block
  220.  
  221. 	temp->digits = NULL; // set to null to avoid run time error when free is called on temp later
  222.  
  223. 	prevBlockSizes = malloc(sizeof(bignum) * 30);
  224. 	curBlockSizes = malloc(sizeof(bignum) * 30);
  225.  
  226. 	for (i = 0; i < 30; ++i)
  227. 	{
  228. 		prevBlockSizes[i] = malloc(sizeof(bignum));
  229. 		curBlockSizes[i] = malloc(sizeof(bignum));
  230. 		curBlockSizes[i]->digits = NULL; // set to null to avoid run time error when free is called on curBlockSizes[i] later
  231. 	}
  232.  
  233. 	init_bignum(runningTotal, 1);
  234. 	runningTotal->digits[0] = 0;
  235.  
  236. 	bignum one;
  237. 	init_bignum(&one, 1);
  238. 	one.digits[0] = 1;
  239.  
  240. 	bignum four;
  241. 	init_bignum(&four, 1);
  242. 	four.digits[0] = 4;
  243.  
  244. 	bignum ten;
  245. 	init_bignum(&ten, 2);
  246. 	ten.digits[0] = 0;
  247. 	ten.digits[1] = 1;
  248.  
  249. 	// set up the diagonals array to contain
  250. 	//{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
  251. 	ui j, dif, tmp;
  252. 	for (j = 1, dif = 0; j <= 19; ++j)
  253. 	{
  254. 		bignum cur;
  255. 		tmp = j <= 10 ? j : j - (dif += 2);
  256. 		if (tmp < 10)
  257. 		{
  258. 			init_bignum(&cur, 1);
  259. 			cur.digits[0] = tmp;
  260. 		}
  261. 		else
  262. 		{ // value of 10			
  263. 			init_bignum(&cur, 2);
  264. 			cur.digits[1] = 1;
  265. 			cur.digits[0] = 0;
  266. 		}
  267. 		diagonals[j - 1] = cur;
  268. 	}
  269.  
  270. 	init_bignum(&curBlockWidth, 2); // set curBlockWidth to 10
  271. 	curBlockWidth.digits[1] = 1;
  272. 	curBlockWidth.digits[0] = 0;
  273. 	copy_bignum(&curBlockWidth, &prevBlockWidth); // set prevBlockWidth to 10 also
  274.  
  275. 	// fill in the block sizes for 10 x 10 blocks
  276. 	// first block has size 1, not using the 0 index of either cur or prevBlockSizes
  277. 	init_bignum(curBlockSizes[2], 1);
  278. 	curBlockSizes[2]->digits[0] = 1;
  279. 	for (i = 2; i < 20; ++i)
  280. 		add_bignum(curBlockSizes[i], &diagonals[i - 1], curBlockSizes[i + 1]);
  281. 	for (i = 20; i < 30; ++i)
  282. 	{ // set the rest equal to 100 - full block size
  283. 		bignum* cur = malloc(sizeof(bignum));
  284. 		init_bignum(cur, 3);
  285. 		cur->digits[0] = 0;
  286. 		cur->digits[1] = 0;
  287. 		cur->digits[2] = 1;
  288. 		curBlockSizes[i] = cur;
  289. 	}
  290.  
  291. 	for (i = 1; i < 30; ++i)
  292. 	{
  293. 		bignum* cur = malloc(sizeof(bignum));
  294. 		init_bignum(cur, 1);
  295. 		cur->digits[0] = 0;
  296. 		prevBlockSizes[i] = cur;
  297. 	}
  298.  
  299. 	if (MAX_HEAT_LEVEL < 9)
  300. 	{
  301. 		bignum maxHeatLevel;
  302. 		init_bignum(&maxHeatLevel, 1);
  303. 		maxHeatLevel.digits[0] = MAX_HEAT_LEVEL + 1;
  304.  
  305. 		bignum answer;
  306. 		subtract_bignum(curBlockSizes[MAX_HEAT_LEVEL + 2], &maxHeatLevel, &answer);
  307.  
  308. 		bignum answer2;
  309. 		multiply_bignum(&answer, &four, &answer2);
  310.  
  311. 		add_bignum(&one, &answer2, &finalBlockCount);
  312. 	}
  313. 	else
  314. 	{
  315. 		targetLevel = (MAX_HEAT_LEVEL / 9);
  316. 		curLevel = 1;
  317.  
  318. 		while (curLevel <= targetLevel)
  319. 		{ // swap arrays
  320. 			swapHolder = prevBlockSizes;
  321. 			prevBlockSizes = curBlockSizes;
  322. 			curBlockSizes = swapHolder;
  323. 			for (i = 1; i <= 29; ++i)
  324. 			{
  325. 				free_bignum(curBlockSizes[i]);
  326. 				init_bignum(curBlockSizes[i], 1);
  327. 				curBlockSizes[i]->digits[0] = 0;
  328. 			}
  329. 			multiply_powers_of_ten_bignum(&curBlockWidth, &curBlockWidth, &fullBlockSize);
  330. 			for (i = 1; i < 28; ++i)
  331. 			{
  332. 				for (d = 0, s = i + 9; d < i && d < 19; ++d, --s)
  333. 				{ // this section multiplies the number of diagonal smaller blocks times their size
  334. 			      // and adds the result to the running total
  335. 					multiply_bignum(s < 30 ? prevBlockSizes[s] : &fullBlockSize,
  336. 						&diagonals[d], &blocksToAdd);
  337.  
  338. 					add_bignum(curBlockSizes[i], &blocksToAdd, temp);
  339.  
  340. 					free_bignum(&blocksToAdd);
  341.  
  342. 					free_bignum(curBlockSizes[i]);
  343.  
  344. 					copy_bignum(temp, curBlockSizes[i]);
  345.  
  346. 					free_bignum(temp);
  347. 				}
  348. 			}
  349. 			copy_bignum(&curBlockWidth, &prevBlockWidth);
  350. 			multiply_powers_of_ten_bignum(&curBlockWidth, &ten, &curBlockWidth);
  351. 			multiply_powers_of_ten_bignum(&curBlockWidth, &curBlockWidth, curBlockSizes[29]); // full block size
  352. 			subtract_one_from_power_of_ten_bignum(curBlockSizes[29], curBlockSizes[28]); // full block minus one in the corner
  353. 			++curLevel;
  354. 		}
  355. 		// the next section multiplies the block number by 4 and subtracts tiles on the axes, then adds one for (0, 0)
  356. 		a = (curLevel - 1) * 9;
  357.  
  358. 		b = ((MAX_HEAT_LEVEL + 2) - a);
  359.  
  360. 		c = (bignum_to_ull(&prevBlockWidth) * b) - 2;
  361.  
  362. 		ull_to_bignum(c * 4, &edgeBlockSubtractionFactor);
  363.  
  364. 		subtract_bignum(curBlockSizes[(MAX_HEAT_LEVEL - a) + 2], &one, &relevantBlockSizeMinusOne);
  365.  
  366. 		multiply_bignum(&relevantBlockSizeMinusOne, &four, &blocksAfterMultiplyingByFour);
  367.  
  368. 		subtract_bignum(&blocksAfterMultiplyingByFour, &edgeBlockSubtractionFactor, &blocksAfterEdgeSubtraction);
  369.  
  370. 		add_bignum(&blocksAfterEdgeSubtraction, &one, &finalBlockCount);
  371. 	}
  372. 	print_bignum(&finalBlockCount);
  373. 	return 0;
  374. }
Success #stdin #stdout 4.79s 5024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5786262651250961355183095522487676611342982173923354312876717511078556481507473305268873565249806196048269834749410505115300618376888302066036740458312255003934788090000646895854424610253117132012311432301484874414980944195126735980681941747106286987001178979695843065092536726850383005586307765915405562556950100206142044846832353213184885384980401548434324326181094013741147190341580390066623695053588747883468795320560254028238727208541006208672165854688536244787427232271690207624692871864759781427916257270136859107161356987468715878609022275861425159339681881150270587199427874032778021520821456150519326143397076569723136174525028629405795093823266234548015010134199308456783777537552422086201893814960174093996568663468149880629403962127833847877624042101660744750414912576646347304829160268321167166919659817468634217693889746434032981655979218859029596183422246563242658898077402592840912328842934658468092998447780785130155187089913137152988244716167674358959248021479845915671527299110122078542084388354835991791025693543043964394102164725128062860867187929939443827676489337757543772439204098230743163646438034929808866093497206224971190672790409025138041643970049775635120432858749936911528591840230646024687632067614461074590023309708208667297268185507066643090602952371432955809871094759613119466150743100502021593325068251112907438187780980966768890649400745591465684410170115985797685203764268335207426815872201700056263725306677139049353788239224729335108876922856279966506568847801183998506130211781540917665872435284965841741926890445105564399694958911587646500456934997056312701079256243862449265320246974457836720411589794015062014204400572473251679104316904410535820831477325535206977385317
https://ideone.com/vECpmq
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!