IdeaMonk

thoughts, ideas, code and other things...

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
#include <iostream>
#include <allegro.h>
#include <time.h>

using namespace std;
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};
double lim = 0;

unsigned int maxm(unsigned int n){
// 9400 - size of array
if (n<lim)
return a[n];

unsigned int p;
p = n/2 + n/3 + n/4;

if (p>n)
//sort of binary recursion which you should figure out to solve COINS
else
return n;
}

int main (){
unsigned int n=10,col2,col;
double x=0,px=1,py=760,y;
clock_t start ,stop;

allegro_init();
set_color_depth(32);
set_gfx_mode (GFX_AUTODETECT_WINDOWED,1024,768,0,0);

clear_to_color (screen,makecol(0,0,0));

while (lim<450){
col = makecol ((lim/450)*250+5, (lim/450)*255, 100);
col2=makecol (((lim/450)*250+5)/3, (lim/450)*255/3, 100/3);
while (n<310){
n+=1;
start = clock();
maxm(n*20000);
stop = clock();
// cout << stop <<" "<<start << endl;
y=760-((stop-start)*5);
rectfill (screen,px,760,px+3,y,col2);
line (screen,px,py,px+3,y,col);

px+=3;
py=y;
}
lim=lim+5;
x=0; px=1; py=760;
n=10;
cout << lim<<endl;
}
getchar();
}
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: , , , , , , , ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home