fork(11) download
  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
stdin
Standard input is empty
stdout
5786262651250961355183095522487676611342982173923354312876717511078556481507473305268873565249806196048269834749410505115300618376888302066036740458312255003934788090000646895854424610253117132012311432301484874414980944195126735980681941747106286987001178979695843065092536726850383005586307765915405562556950100206142044846832353213184885384980401548434324326181094013741147190341580390066623695053588747883468795320560254028238727208541006208672165854688536244787427232271690207624692871864759781427916257270136859107161356987468715878609022275861425159339681881150270587199427874032778021520821456150519326143397076569723136174525028629405795093823266234548015010134199308456783777537552422086201893814960174093996568663468149880629403962127833847877624042101660744750414912576646347304829160268321167166919659817468634217693889746434032981655979218859029596183422246563242658898077402592840912328842934658468092998447780785130155187089913137152988244716167674358959248021479845915671527299110122078542084388354835991791025693543043964394102164725128062860867187929939443827676489337757543772439204098230743163646438034929808866093497206224971190672790409025138041643970049775635120432858749936911528591840230646024687632067614461074590023309708208667297268185507066643090602952371432955809871094759613119466150743100502021593325068251112907438187780980966768890649400745591465684410170115985797685203764268335207426815872201700056263725306677139049353788239224729335108876922856279966506568847801183998506130211781540917665872435284965841741926890445105564399694958911587646500456934997056312701079256243862449265320246974457836720411589794015062014204400572473251679104316904410535820831477325535206977385317