IdeaMonk

thoughts, ideas, code and other things...

Thursday, October 30, 2008

Adding large numbers in C++

Just wrote a C++ snippet to add huge numbers using strings -
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. string add (string &s1, string &s2){  
  5. int carry=0,sum,i;  
  6.   
  7. string  min=s1,  
  8.  max=s2,  
  9.  result = "";  
  10.   
  11. // Finds the bigger string  
  12. if (s1.length()>s2.length()){  
  13.  max = s1;  
  14.  min = s2;  
  15. else {  
  16.  max = s2;  
  17.  min = s1;  
  18. }  
  19.   
  20. // Fills the result for overlapping regions of sum  
  21. for (i = min.length()-1; i>=0; i--){  
  22.  sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';  
  23.   
  24.  carry = sum/10;  
  25.  sum %=10;  
  26.   
  27.  result = (char)(sum + '0') + result;  
  28. }  
  29.   
  30. // Summates the previous carry and the remaining digits of bigger string  
  31. i = max.length() - min.length()-1;  
  32.   
  33. while (i>=0){  
  34.  sum = max[i] + carry - '0';  
  35.  carry = sum/10;  
  36.  sum%=10;  
  37.   
  38.  result = (char)(sum + '0') + result;  
  39.  i--;  
  40. }  
  41.   
  42. // Adds the carry if remaining to the last digit e.g 999+1=1000  
  43. if (carry!=0){  
  44.  result = (char)(carry + '0') + result;  
  45. }  
  46.   
  47. return result;  
  48. }  
  49.   
  50. int main (){  
  51. // implementation  
  52. string a,b;  
  53. cin >> a >> b;  
  54. cout << add (a,b)<<endl;  
  55. return 0;  
  56. }  

Output :

32485689234981709712094710984091842358764876328746187648716462938589273589723895789237587238947189748917894718973891728937189478913277893257891749817984719287439812789473289475328975981723894718927489127894712894

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

32485689234981709712094710984091842358764876328746187648716462938589273599723895789237587238947189748917894718973891728937189478913277893257891749817984719287439812789473289475328975981723894718927489127894712893

Labels: , ,

Wednesday, October 01, 2008

Optimization by Memoization ( not memorization )

To iterate is Human, to Recurse, to Recurse, Divine - unknown

Solving COINS at spoj was a great lesson in recursion. Beautiful may the recursive code seem, but in some cases it is slow as a snail in worst case scenario. Consider finding nth Fibonacci by recursion as an example! And in some cases as in finding p^q, recursion is truly divine god's gift ;P.
Same is the case with COINS, its pretty easy to figure out the function that gets the job done... but give it something like n = 1000000000, poof! it vanishes into a deep slumber!
So, how can we make it work faster... ?
Have you ever noticed that, kids are asked to remember multiplication tables from 2 to 10 when in primary mathematics classes! Ever wondered why to do this mugging up at such a tender age. The answer is in... how we multiply two big numbers (abcd * pqrs). Here every digit i & j is in range of 0 through 9. So, if you've memorized multiplication table for 2 to 9, it will be very easy to get through (abcd * pqrs).
Thats exactly what we will do here. Basically as the problem gets solved for bigger numbers, loads of steps trickle down to maxm() function for small numbers, just like end of roots of a tree. So, here again we will pre-calculate and store maxm(n) in an array for 1<n<9400. Why 9400? Have a look at http://www.spoj.pl/problems/COINS/, you can't write more that 50KB of code! So this weekend I decide to see the real consequence of memoization. Here's the allegro code I wrote to plot time against my COIN's solution. Memoization 9400 values works for the spoj judge. And it seems even memorizing 450 values works amazingly for my Athlon 64 :P
  1. #include <iostream>  
  2. #include <allegro.h>  
  3. #include <time.h>  
  4.   
  5. using namespace std;  
  6. unsigned int a[]={0,1,2,3,4,5,6,7,8,9,10,11,13,13,14,15,17,17,19,19,21,22,23,23,27,27,27,28,30,30,32,32,35,36,36,36,41,41,41,41,44,44,46,46,48,49,49,49,57,57,57,57,57,57,60,60,63,63,63,63,68,68,68,69,74,74,76,76,76,76,76,76,87,87,87,87,87,87,87,87,92,93,93,93,98,98,98,98,101,101,104,104,104,104,104,104,119,119,119,120,120,120,120,120,120,120,120,120,129,129,129,129,134,134,134,134,134,134,134,134,144,144,144,144,144,144,147,147,155,155,155,155,160,160,160,161,161,161,161,161,161,161,161,161,185,185,185,185,185,185,185,185,185,185,185,185,185,185,185,185,193,193,197,197,197,197,197,197,207,207,207,207,207,207,207,207,212,212,212,212,221,221,221,221,221,221,221,221,221,222,222,222,250,250,250,250,250,250,253,253,253,253,253,253,253,253,253,253,253,253,253,253,253,253,253,253,276,276,276,276,276,276,276,276,284,284,284,284,284,284,284,284,284,284,284,284,284,284,284,284,304,304,304,305,305,305,305,305,305,305,305,305,314,314,314,314,327,327,327,327,327,327,327,327,337,337,337,337,337,337,341,341,341,341,341,341,341,341,341,341,341,341,341,341,341,341,341,341,391,391,391,391,391,391,391,391,391,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,392,405,405,405,405,419,419,419,419,419,419,419,419,419,419,419,419,439,439,439,439,439,439,439,439,439,439,439,439,439,439,439,439,447,447,447,447,447,447,447,447,469,469,469,469,469,469,469,469,469,469,469,469,469,469,469,469,469,469,473,473,473,473,473,473,524,524,524,524,524,524,524,524,524,524,524,524,533,533,533,533,533,533,533,533,533,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,534,590,590,590,590,590,590,590,590,590,590,590,590,590,590,590,590,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,603,641,641,641,641,641,641,646,646,646,646,646,646,646,646,646,646,646,646,646,646,646,646,646,646,668,668,668,668,668,668,668,668,689,689,689,689,689,689,689,689,689,689,689,689,689,689,689,689,709,709,709,709,709,709,709,709,709,709,709,709,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,723,724,724,724,724,724,724,724,724,724,826,826,826,826,826,826,826,826,826,826,826,826,826,826,826,826,826,826,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,830,851,851,851,851,851,851,851,851,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,892,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,930,943,943,943,943,943,943,943,943,943,943,943,943,943,943,943,943,994,994,994,994,994,994,994,994,994,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,995,1009,1009,1009,1009,1009,1009,1009,1009,1009,1009,1009,1009,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1101,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1123,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1128,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1257,1258,1258,1258,1258,1258,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1279,1350,1350,1350,1350,1350,1350,1350,1350,1350,1350,1350,1350,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1370,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1421,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1455,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1493,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1533,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1538,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1741,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1755,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1756,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1790,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1901,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1972,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,1993,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2104,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2110,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2150,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2314,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2365,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2385,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2386,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2673,2678,2678,2678,2678,2678,2678,2678,2678,2678,2678,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2712,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2842,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,2908,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3019,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3074,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3145,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3250,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3251,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3271,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3668,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3708,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3714,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,3769,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4050,4051,4051,4051,4051,4051,4051,4051,4051,4051,4051,4051,4051,4051,4051,4051,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4181,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4215,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4448,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4475,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4580,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4870,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,4981,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5046,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5052,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5671,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5691,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5746,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5747,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,5982,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6179,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6412,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6501,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6631,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6887,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6894,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,6959,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7723,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7828,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7855,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7856,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,7945,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8624,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8630,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8865,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,8920,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9394,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9493,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,9749,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10258,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10491,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10681,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10682,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,10709,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12012,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12077,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12166,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12173,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,12593,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13137,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13138,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13612,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13756,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,13991,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14585,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14620,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,14810,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261,16261};  
  7. double lim = 0;  
  8.   
  9. unsigned int maxm(unsigned int n){  
  10. // 9400 - size of array  
  11. if (n<lim)  
  12.  return a[n];  
  13.   
  14. unsigned int p;  
  15. p = n/2 + n/3 + n/4;  
  16.   
  17. if (p>n)  
  18.  //sort of binary recursion which you should figure out to solve COINS  
  19. else  
  20.  return n;  
  21. }  
  22.   
  23. int main (){  
  24. unsigned int n=10,col2,col;  
  25. double x=0,px=1,py=760,y;  
  26. clock_t start ,stop;  
  27.   
  28. allegro_init();  
  29. set_color_depth(32);  
  30. set_gfx_mode (GFX_AUTODETECT_WINDOWED,1024,768,0,0);  
  31.   
  32. clear_to_color (screen,makecol(0,0,0));  
  33.   
  34. while (lim<450){  
  35.  col = makecol ((lim/450)*250+5,  (lim/450)*255, 100);  
  36.  col2=makecol (((lim/450)*250+5)/3,  (lim/450)*255/3, 100/3);  
  37.  while (n<310){  
  38.   n+=1;  
  39.   start = clock();  
  40.   maxm(n*20000);  
  41.   stop = clock();  
  42.   //  cout << stop <<" "<<start << endl;  
  43.   y=760-((stop-start)*5);  
  44.   rectfill (screen,px,760,px+3,y,col2);  
  45.   line (screen,px,py,px+3,y,col);  
  46.    
  47.   px+=3;  
  48.   py=y;  
  49.  }  
  50.  lim=lim+5;  
  51.  x=0; px=1; py=760;  
  52.  n=10;  
  53.  cout << lim<<endl;  
  54. }  
  55. getchar();  
  56. }  
  57. END_OF_MAIN();  

And here's the plot! amazing visible differences...
checkout the drastic improvement from lim=0 to lim=450!
That's all for the Friday research folks!

Labels: , , , , , , , ,