[JAVA] 동적프로그래밍(DP) "N으로 표현하기"

https://programmers.co.kr/learn/courses/30/lessons/42895

 

아래와 같이 number 와 N이 주어지면 N을 몇번을 사용해서 number값을 만들어 낼 수 있는지 구하는 문제이다.

<number=12,  N=5인 경우>

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

 

 

아래와 같은 코드는 점화식을 이용하여, 완전탐색을 하는 방식이다.

아마도 DFS 방식이 이 방식이 아닌가 싶다. 아직은 DFS에 대해 다뤄보지 않아서, 추후 코멘트를 남기겠다.

유사, Combination을 떠오르게 하는 점화식이다.

 

 

• Set을 배열로 각각의 인덱스Set에 여러개의 값이 들어갈 수 있다는 방식을 알아야한다.

Set<Integer>[] setArr = new HashSet[9];

 

* : combination을 이용하여 각각의 연산기호에 따른 값을 넣는다.

(A[2] * A[1]) + (A[3] * A[1]) + (A[3] * A[2]) + ... + (A[n] * A[n-m]) + ...(A[n] * A[n]) 

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        Set<Integer>[] setArr = new HashSet[9];//1~9까지
        int t = N;
        for(int i = 1; i < 9; i++) {
            setArr[i] = new HashSet<>();
            setArr[i].add(t);// 5 55 555 5555....
            t = t * 10 + N;
        }
        //모든경우의 수를 구하는 방법이다.
        for(int i = 1; i < 9; i++) {
            for(int j = 1; j < i; j++) {
                for(Integer a : setArr[j]) {
                    //각각의 setArr[j] 배열에 대하여
                    for(Integer b : setArr[i - j]) {
                        //setArr[] 배열에 모든 경우를 구한다.
                        setArr[i].add(a + b);//5+5=10
                        setArr[i].add(a - b);//5-5=0
                        setArr[i].add(b - a);//5-5=0
                        setArr[i].add(a * b);//5*5=25
                        if(b != 0) {
                            setArr[i].add(a / b);//5/5=1
                        }
                        if(a != 0) {
                            setArr[i].add(b / a);//5/5=1
                        }
                    }
                }
            }
            //탐색을 바로바로 하게 하여 실행속도 향상
            if(setArr[i].contains(number)) {
                answer = i;
                //오름차순으로 탐색하여,
                // i번째에 해당 number가 포함되어있으면 i번의 실행이 최소 횟수이다.
                break;
            }
        }

		
       /* for(int i = 1; i < 9; i++) {
            if(setArr[i].contains(number)) {
                answer = i;
                //오름차순으로 탐색하여,
                // i번째에 해당 number가 포함되어있으면 i번의 실행이 최소 횟수이다.
                break;
            }
        }*/
        return answer;
    }
}

 

이처럼 setArr[i]인 HashSet에 각각의  계산값을 add해주면  아래와 같이 Set에 들어간다.

 

setArr[1] 부터 setArr[9] 까지 출력한 결과이다.

 

출력

[5] \\\\\\\\\\\\\ [0, 1, 55, 25, 10] \\\\\\\\\\\\\ [0, 2, -4, -5, 4, 5, 6, 555, 11, 15, -50, 50, 275, -20, 20, 60, 125, 30] \\\\\\\\\\\\\ [0, -1, 1, -3, 2, 130, 3, -4, -5, 4, 5, -6, 6, 7, -9, 9, -10, 10, 11, 12, -270, 270, -15, 15, 16, -20, 20, 150, -24, -25, 280, 24, 25, 26, -30, 30, 35, -550, 550, -45, 300, 45, 560, 50, 5555, -54, -55, 54, 55, 56, 65, 75, 80, 3025, 2775, 1375, -100, 100, 110, 111, 625, -120, 120, -250, 250] \\\\\\\\\\\\\ [0, -1, -2, 1, 2, -3, -4, 3, -5, 4, 5, -6, 6, -7, -8, 7, 8, -9, 9, -10, 10, -11, 11, 12, -13, -14, 13, -15, 14, 15, 16, 17, -530, -19, 530, -20, 19, 20, -21, 21, 22, -23, -24, 23, -25, 24, 25, 26, 27, -29, -30, 29, 30, 31, -545, 545, -35, 35, 36, 550, -40, 40, -554, -555, 554, 555, -44, -45, 556, 44, 45, -49, -50, 49, 50, -51, 51, 13875, -53, -54, 565, 3125, 53, 54, -55, 55, 56, 57, -59, 59, -60, 60, 61, 66, 580, -70, 70, -75, 75, -1100, 1100, 80, 85, 1111, -600, 600, 605, -95, 95, 610, -100, 100, -105, 105, -106, 106, -620, 620, -110, 110, 112, -115, 1650, 115, 116, 630, -120, 120, -124, -125, 124, 125, 126, 27775, 130, 135, 650, -145, 145, -150, 150, 155, 175, 180, -2750, 2750, -200, 200, -2770, 2770, 6875, -220, 2780, 220, -225, 225, -1250, 1250, 3300, 750, 2800, -245, 245, -250, 250, -255, 255, 55555, -265, 265, -270, 270, -274, -275, 274, 275, 276, 15125, 280, 285, -295, 295, 300, 305, 825, 30525, -1350, 325, 1350, 330, -1370, 1370, 1380, 375, 1400, 400, -5550, 5550, 5560, -3020, 3020, 3030, 1500, -500, 500] \\\\\\\\\\\\\ [0, -1, -2, 1, -3, 2, 3, -4, -5, 4, 5, -6, 6, -7, 7, -8, 8, -9, 3080, -10, 9, 10, -11, 11, -12, 12, -13, 13, -14, -15, 14, 15, -16, 16, -17, 17, -18, 18, -19, -20, 19, 20, -21, 21, -22, 22, -23, -24, 23, -25, 24, 25, -26, 26, -27, 27, -28, -3100, 28, -29, 3100, -30, 29, 4125, 30, -31, 31, 32, -34, -35, 34, 35, 36, 37, -39, -40, 39, 40, 15400, 41, -43, -44, 43, -45, 44, 45, -46, 46, -48, -3120, -49, 3120, 48, -50, 49, 50, -51, 51, -52, 152625, 52, -53, -54, 53, -55, 54, 55, -56, 56, -58, 57, 58, -59, 3130, 8250, 59, -60, 60, -61, 61, 62, -64, -65, 64, 65, 66, 67, -68, 68, -70, 70, -1095, 71, 1095, -74, -75, 74, 75, -1100, 1100, 76, 3150, -79, -80, 79, 80, -1105, 30800, 1105, -1106, 81, 1106, -85, 85, -1110, -86, 1110, 86, 1112, -90, 90, 1116, 92, -95, 95, -99, -100, 99, 100, -101, -1125, 101, 1125, -27750, 27750, -105, -106, 105, -6250, 106, -107, 6250, 107, -109, 109, -110, 110, -111, 111, 112, 113, -114, -115, 114, 115, 116, 16500, 117, -119, -120, 119, 120, -121, 121, -27770, 122, 27770, -123, -124, 123, -125, 124, 125, 126, 127, -129, 129, -130, 130, 131, 27780, 8325, 135, 136, 137, -138, 138, -140, 140, -145, 145, -149, -150, 149, 150, 151, 27800, -155, 155, 160, -165, 165, 166, -170, 170, -2220, 2220, -175, 175, -1200, 1200, 3250, 180, 185, -195, 195, -200, 200, -1225, 1225, -205, 205, -215, 215, -220, 220, -1245, 1245, 222, -3295, 3295, -225, 225, -1250, 1250, -230, 230, -1255, 1255, 3305, -240, 240, -245, 245, -249, -250, 249, 250, -1275, -251, 1275, 251, -55550, -255, 55550, 255, 3330, -260, 260, -264, -265, 55560, 264, 15625, 265, 16650, 277775, -269, -270, 269, 270, -271, 271, -273, -274, 273, -275, 274, 275, 276, 1300, 277, -279, 279, -280, 280, 281, 285, 286, -290, 290, -295, 295, -1320, 1320, -299, -300, 299, 300, -1325, 1325, 301, 302, 4400, -305, 305, 310, -320, -1345, 320, 1345, -325, -1350, 325, 1350, -330, 330, -1355, 1355, 7500, 335, -1365, 1365, -1370, 1370, -350, -1374, 350, -1375, 1374, 1375, 1376, 355, 1380, 360, 1385, -370, 305525, 370, -1395, 1395, -375, 375, 1400, -5500, 5500, 380, 1405, 385, -395, 395, -400, 400, 1425, 405, 1430, -5530, 5530, -5545, 425, 5545, -2475, 2475, -430, 430, -5554, -5555, 5554, 5555, 5556, -13750, 13750, 5565, -450, -1475, 450, 1475, -2500, 2500, -6600, 6600, 5580, -1495, 1495, -475, 475, -1500, 1500, 5600, 1505, 166375, 5610, -495, 495, -500, 500, 1525, 3575, -505, 505, -14850, 14850, -525, 525, 3600, -530, 530, 33300, -535, 535, -13850, 13850, -540, 540, -544, -545, 544, 545, -549, -550, 549, 550, -551, 551, -553, -554, -30250, 553, 554, 30250, -555, 555555, 555, 556, -13870, 557, -559, 13870, 559, -560, 560, 561, 566, 13880, -570, 570, -575, 575, 580, 34375, 585, 13900, -595, 595, -600, 600, -2650, 1625, 2650, -604, -605, 604, 605, -6750, 6750, 606, 610, -615, 615, -620, -1645, 620, 1645, -624, -625, 624, 625, -1650, 1650, 626, 630, 1655, 138875, 635, -645, 645, 650, -2700, 2700, 655, 660, -2720, 2720, 675, -2725, 2725, 3750, 680, 14000, -2745, 2745, -2750, 2750, -6850, -2755, 6850, 2755, -2765, 2765, -2770, 2770, -725, 725, -6870, -2774, -2775, 6870, 2774, 2775, 2776, 2780, 6880, 2785, -745, 745, -2795, 2795, -750, 750, 2800, 755, 6900, 2805, -15100, 15100, 69375, 775, 1800, 2825, 2830, -15120, 15120, 15130, 800, 15150, -820, 820, -30520, 30520, -825, 825, 308025, 830, 30530, 1875, 2900, 7000, -11100, 11100, 11111, 75625, 875, 880, 900, 1925, -2970, 2970, 6050, -3000, 3000, -3015, 3015, -3024, 2000, -3025, 3024, 3025, 3026, 6105, 3035, -1000, 1000, 3050, 7150] \\\\\\\\\\\\\ [0, -1, -2, 1, 2, -3, 3, -4, -4100, -5, 4, 4100, 5, -6, 6, -7, 7, -8, 8, -9, -10, 9, 10, -11, 1540125, 11, -12, 12, -13, 13, -14, -15, 14, 15, -16, 16, -17, 17, -18, 18, -19, -20, 19, 20, -21, 21, -22, 22, -23, 23, -24, -4120, -25, 24, 4120, 25, -26, 26, -27, 27, -28, 28, -29, -4125, -30, 29, 4125, 30, -31, 31, -32, 32, -33, -8225, 33, -34, 8225, -35, 34, 4130, 35, -36, 36, -37, 37, -38, -39, 38, -40, 39, 40, -41, 41, -42, 42, -43, -44, 43, -45, 44, 45, -46, 46, -47, -48, 47, 48, -49, -50, 49, 50, -51, 51, -52, -53, 52, -8245, 53, -54, 8245, -55, 54, 4150, 55, -56, 56, -57, 57, -58, -8250, 58, -59, 8250, -60, 59, 60, -61, 61, -62, -63, 62, 63, -64, 8255, -65, 64, 65, -66, 66, -67, 67, -68, -69, 68, -70, 69, 70, -71, 71, 72, -73, 73, -74, -75, 74, 75, -76, 76, 77, -78, -79, 78, -80, 79, 80, -81, 81, 82, -84, 8275, -85, 84, 85, -86, 86, -87, -12375, 87, 12375, -89, -90, 89, 90, -91, -16475, 91, 16475, -92, 92, -94, 93, -95, 94, 95, -96, 96, 97, -98, -99, 98, -100, 99, 100, -101, 101, -102, 102, -104, -105, 104, 4200, 105, -106, 106, -107, 107, -108, 108, -109, -110, 109, 110, -111, -16495, 111, -112, 16495, 112, -113, -114, 113, -115, 114, 115, -116, -16500, 116, -117, 16500, 117, -118, 118, -119, -120, 119, 120, -121, 121, 16505, -122, 122, -123, -124, 123, -125, 124, 125, -126, 126, 127, -128, -8320, 128, -129, 8320, -130, 129, 130, -131, 131, -132, 132, -133, -8325, -134, 133, 8325, -135, 134, 135, 136, -137, 137, -138, 8330, 138, -139, -140, 139, 140, 141, 16525, 142, -143, 143, -144, -145, 144, 145, 20625, -146, 146, -148, -149, 148, -150, 149, 150, -151, 151, 152, -154, -155, 154, 155, -156, 156, -160, 160, -161, 161, -164, -165, 164, 165, 61605, 166, 167, -170, 170, 171, -174, -175, 174, 175, 176, -179, -180, 179, 180, 181, -185, 185, -190, 190, -195, 195, -199, -200, 199, 200, -201, 201, -205, 205, 8400, -210, 210, -12500, 12500, -215, 215, -216, -217, 216, 217, -219, -220, 219, 220, -221, 221, -222, 222, 223, -224, -225, 224, 225, -226, 226, 227, -230, 229, 230, -33000, 33000, -235, 235, 236, -239, -240, 239, 240, -244, -245, 244, 245, -246, 246, -248, -249, 248, -250, 249, 250, -251, 251, -252, 252, -254, -255, 254, 255, -256, 256, -259, -260, 259, 260, -16645, -261, 16645, 261, -263, -264, 263, -265, 264, 265, -266, -16650, 16650, 266, -268, -269, 268, -270, 269, 270, -271, 16655, 271, -272, 272, -273, -274, 273, -275, 274, 275, -276, 276, -277, -278, 277, 278, -279, -280, 279, 4375, 280, -281, 281, 282, -284, 284, -285, 285, 286, 287, -289, -290, 289, 290, 41250, 291, -294, -295, 294, 295, -296, 296, -297, 297, -298, -4395, -299, 298, -300, 4395, 299, 300, 78125, 301, -302, 302, -304, 303, -305, 304, 4400, 305, 306, 307, 4405, -310, 310, 311, 312, -315, 315, -320, 45375, 320, -324, -325, 324, 325, 326, -329, -330, 329, 330, 331, 8525, -335, 335, 336, -340, 340, -343, 343, -345, 345, -350, 350, 1388875, -355, 355, -360, 360, -365, 365, -370, 70000, 370, -374, -375, 374, 375, 376, -380, 380, -385, 385, 386, -390, 390, 16775, -395, 395, -399, -24975, -400, 831875, 399, 24975, 400, 401, -405, 4500, 405, 410, 16800, -420, 420, -425, 425, -430, 430, -435, 435, -440, 440, -444, 444, -445, 445, -450, 450, -455, 455, 460, 462, -470, 470, -475, 475, -29150, 29150, -480, 480, -490, 490, -495, 495, -499, -500, 499, 500, -501, 501, -505, 504, 505, -111100, 33275, -510, 111100, 510, 111111, -520, -74250, 520, 74250, -525, 525, -33295, 33295, -529, -530, 529, 530, -531, 531, -535, 535, 33305, -539, -540, 539, 540, -543, -544, 543, -545, 544, 545, -546, 546, -548, -549, 548, -550, 549, 550, -551, 551, -552, 552, -553, -554, 553, -555, 554, 555, -556, 556, -558, 557, 558, -559, 559, -560, 560, -561, 561, 562, 33330, -564, 564, -565, 565, 566, 567, -570, 570, 571, -575, 575, -579, -580, 579, 4675, 580, 82500, 581, -585, 585, -590, 590, -594, -595, 594, 595, -599, -600, 599, 600, -601, 601, -603, 603, -604, -605, 604, 605, 606, 607, -609, 609, -610, 610, 611, -614, -615, 614, 615, 616, -619, -620, 619, 620, -621, 621, -623, -624, 623, 624, -625, 625, 626, 627, -629, 629, -630, 630, 631, 635, 37500, 636, -640, 90750, 640, -645, 645, 2777775, -649, -650, 649, 650, 651, -655, 655, -659, 659, 660, 661, 41625, 665, 666, -670, 670, -675, 675, 680, 685, 687, 8880, -690, 690, -693, 693, -695, 695, -700, 700, 4800, 705, -715, 715, -720, 720, -725, 725, -730, 730, -740, 740, -745, 745, -749, -750, 749, 750, 751, -755, 755, -756, 756, 760, -770, 770, -775, 775, 780, 33550, -795, 795, 152350, -152350, -800, 800, -805, 805, 9000, -810, 810, -815, 815, 308020, -820, 820, -308020, -824, -825, 824, 825, 308030, 826, -830, 830, 33600, 835, 840, -850, 850, 855, -870, 870, -875, 875, 880, 885, -895, 895, -4995, 4995, -900, 900, -5000, 5000, 905, 925, 935, -950, 950, 960, -13250, 13250, -975, 975, -33750, 33750, -995, 995, -1000, 1000, -1005, 1005, 1010, -1025, 1025, -13320, 13320, -1045, -152600, 1045, -1050, 152600, 1050, -1056, 1056, -1060, 1060, -66600, -152620, 66600, 152620, -1075, 1075, 152630, -1080, 1080, -1086, 1086, -1090, 1090, -1095, 1095, 152650, -1099, -1100, 1099, 1100, -1101, 1101, -1105, 1105, -1106, -1107, 1106, 1107, -1109, -1110, 1109, 1110, -1111, 1111, 1112, 1113, -1115, 1115, 1116, 1117, -1120, 1120, 1121, 1122, -1125, 1125, -5225, -1130, 5225, 1130, 1136, -1150, 1150, -1155, 1155, 1160, 1166, 1180, 9375, -5280, 5280, -13475, 13475, -1195, 1195, -1200, 1200, -5300, -1205, 5300, 1205, 1210, -13500, 13500, -1220, 1220, 1221, -1225, 1225, -1230, 1230, -1240, 1240, -1245, 1245, -1249, -1250, 1249, 1250, -1251, 1251, -1255, 1255, -1260, 1260, -1265, 1265, -1270, 1270, -1275, 1275, 763125, 181500, -1280, 1280, 378125, -1295, 1295, -29970, 29970, -1300, 1300, -29975, 29975, -5400, -1305, 5400, 1305, -13600, 13600, -1315, 1315, -1320, 1320, -1325, 1325, -1330, 1330, 83250, -34100, 34100, -5430, 5430, 5555555, -13625, 13625, -1340, 1340, -1345, 1345, -1349, -1350, 1349, 1350, -1351, 152900, 1351, -5450, -1355, 5450, 1355, -1360, 1360, -1364, -1365, 1364, 1365, -1369, -1370, 1369, 1370, -1371, 1371, -1373, -1374, 1373, -1375, 1374, 1375, 1376, 1377, -5475, -1379, 5475, 1379, -1380, 1380, 1381, 1385, 1386, 1387, -1388, 1388, -1390, 1390, -1395, 1395, -5495, -1399, -1400, 5495, 1399, 1400, 1401, -5500, 5500, -1405, 83325, 1405, -5505, 5505, 1410, -13700, 13700, -1420, 1420, -1425, 1425, -5525, 5525, 1430, -5530, 9625, 5530, 1435, -13725, 13725, -5535, 5535, -1440, 1440, -5540, 5540, -1445, 1445, -5544, 5544, -1450, 1450, -5549, -5550, 5549, 5550, -5551, 5551, 1455, -13745, -5553, -5554, 13745, 5553, 5554, -5555, 5555, 5556, -13750, 5557, -5559, 13750, 5559, -5560, 5560, 5561, -13755, 13755, -1470, 1470, 5566, -1475, 5570, 1475, -5575, -1480, 5575, 1480, -34250, 34250, 5580, 1485, -13775, 13775, 5585, -1490, 1490, 17875, -1495, 1495, -5595, -1499, -1500, 5595, 1499, 1500, 1501, -5600, -1505, 5600, 1505, -5605, 5605, 1510, 1512, 13800, 5615, -1520, 22000, 1520, 333300, -1525, 1525, -30200, -5625, 30200, 5625, 1530, -13820, 13820, -13825, 13825, 1550, 5650, 1555, -13845, 13845, 1560, -13850, 13850, -13855, 13855, -30245, 30245, -13865, 13865, 30250, -34350, -13870, -30255, 34350, 13870, 30255, 5680, -13874, -13875, 13874, 13875, 13876, 13880, -1595, 1595, 13885, -1600, 1600, -34370, 34370, -13895, 13895, 34380, 13900, 18000, 13905, -1620, 1620, -75350, 75350, -1625, 1625, 30300, 1630, 34400, 13925, -1640, 1640, 13930, -1645, 1645, -1649, -1650, 1649, 1650, 1651, -1655, 1655, 1660, -1665, 1665, 1675, -5775, 5775, 1680, -13975, 13975, 5800, 1705, -13995, 13995, 9900, -14000, 14000, 14005, 34500, -5830, 5830, -14025, 14025, -22220, 22220, -1750, 1750, 18150, -75500, 75500, 1775, -1795, 1795, -30470, 30470, -1800, 1800, 1805, 10000, -30500, 30500, 14125, -30515, 30515, -1850, 1850, -30524, -30525, 30524, 30525, 30526, 14150, 30535, -1870, -75600, 1870, 75600, -1875, 1875, 30550, 1880, 34650, -75620, 75620, 1900, -6000, 75630, 6000, 30580, -1920, 1920, 75650, -1925, 1925, 1930, -6045, 6045, 1950, -6050, 6050, 6055, -1975, 1975, 1980, -1995, 1995, -2000, 2000, -6100, 6100, 2005, -6104, 6104, 6105, 6106, 6110, 75750, 2025, -6125, 6125, 6160, 2100, -6200, 6200, -30795, 30795, 2125, -6225, 6225, 30805, 14430, -6245, 6245, -2150, -305250, 2150, 305250, -6250, 6250, 694375, -6255, 6255, 75900, -6275, 6275, -2200, 2200, 6300, 14500, -2215, 2215, -2220, 2220, 2222, -2225, 2225, -6325, 6325, 35000, -2240, 2240, -2250, 2250, -55500, 55500, -166100, 166100, -6375, 6375, -55530, 55530, 6380, -14575, 14575, -55545, 55545, -55554, -55555, 55554, 55555, 55556, 55565, 55580, 55600, 55610, 18750, -2375, 2375, 149850, -149850, -2400, 2400, 31075, -6500, 6500, 31080, -305520, -2420, 305520, 2420, 305530, -2450, 154000, 2450, -2470, 2470, -2475, 2475, -2480, 2480, -2495, 2495, -6595, 6595, -2500, 2500, -6600, 6600, -2505, 2505, -6605, 6605, 72150, -2525, 2525, -6625, 166370, 6625, -166370, 166380, -2550, 2550, -14845, 14845, -14850, 14850, 6660, -14855, 14855, -31250, 31250, -555550, 555550, 555560, -2600, 2600, -2625, 2625, -6725, 6725, -2645, 2645, -6745, -2650, 6745, 2650, -6750, 6750, -2655, 2655, -6755, 6755, 166500, -2675, 2675, -6775, 6775, -2695, 2695, -2700, 2700, 305800, -2705, 2705, -15000, 15000, -2715, 2715, -2720, 2720, -6820, -2725, 6820, 2725, -6825, 6825, -2730, 2730, -2740, 2740, -2745, 2745, -6845, -2749, -2750, 6845, 2749, 2750, -2751, 2751, -6850, 6850, -2755, 2755, -6855, 6855, -2760, 2760, -2764, -2765, 2764, 2765, -6865, -2769, -2770, 6865, 2769, 2770, -2771, 2771, -2773, -6870, -2774, 2773, 6870, -2775, 2774, 2775, 2776, -6874, 2777, -6875, -2779, 6874, 6875, 2779, -2780, 2780, 6876, 2781, -15070, 15070, 6880, 2785, -15075, 2786, 15075, 6885, -2790, 2790, -2795, 2795, -6895, -2799, -2800, 6895, 2799, 2800, 2801, 6900, -2805, 2805, -15095, 15095, -11000, 11000, 166650, 6905, 2810, -15100, 15100, 346875, -15105, 15105, -2820, 2820, -2825, 2825, -15115, 15115, 6925, 2830, -15120, 15120, 6930, 2835, -15124, -15125, 15124, 15125, 15126, 15130, 15135, -2850, 2850, 2855, -15145, 15145, 15150, 15155, -2875, 2875, -6975, 3083025, 6975, 15175, 15180, -2895, 2895, -6995, 6995, -2900, 2900, -11095, 11095, 7000, 2905, -11100, 11100, 7005, -11105, 11105, -11106, 11106, -2915, 2915, -11110, 11110, 11112, -27500, 27500, 11116, 2925, 7025, -2950, 2950, 15250, -2965, 2965, -2970, 2970, -2975, 2975, 35750, -2995, 2995, -3000, 3000, -3005, 3005, -11200, 11200, -3010, 3010, -3014, 3014, -3019, -3020, 3019, 3020, -3021, 3021, -3023, -3024, 3023, -3025, 3024, 3025, 3026, 3027, -3029, 7125, 3029, -3030, 3030, 3031, 3036, 3040, 19425, -3045, 3045, -7145, 7145, 3050, 3052, 7150, 3055, 7155, -3070, 3070, -27650, -3075, 27650, 3075, 3080, 3085, -3095, 3095, -3100, 3100, -7200, -3105, 7200, 3105, -15395, 15395, 15400, -3115, 3115, 15405, -3120, 3120, -3124, -27700, -3125, 3124, 27700, 3125, 3126, 3130, 3135, -27720, -3145, 27720, 3145, -27725, 27725, 3150, 3155, -60500, 60500, -27745, 27745, -27750, 27750, 3175, -27755, 27755, 3180, -27765, 27765, -27770, 27770, -27774, -27775, 27774, 27775, 27776, 27780, 27785, -15500, 15500, -68750, 68750, -27795, 27795, -3225, 27800, 3225, 31900, 27805, -3240, 3240, -3245, 3245, 27825, -3250, 3250, 27830, 3255, 77000, -3275, 3275, -7375, 7375, -3290, 3290, -3299, -3300, 3299, 3300, 3301, 36075, 3310, -15600, 15600, -277750, 277750, -3325, 27900, 3325, 7425, -3330, 3330, -15620, 15620, 3335, -277770, 15630, 277770, 277780, 3355, 3360, 15650, 277800, 3375, -7475, 7475, 15675, -7495, 7495, 3400, -7500, 7500, 7505, -28000, 28000, 7525, 44400, 15750, 28050, 7625, -3570, 3570, 138750, 3580, -138750, 1678875, -3595, 3595, -3600, 3600, 310800, 3605, -3625, 3625, 3630, 138850, -138850, 138870, -138870, 7800, 61050, -69250, 138880, 69250, -3725, 3725, 138900, -3745, 3745, -3750, 3750, 3755, 61105, 3775, 151250, -151250, -69350, 69350, -69370, 139000, 69370, 69380, -3850, 3850, 155400, 69400, 3875, -7975, 7975, 3885, 3900, -12100, 12100, -16200, 16200, 1527625, -16225, 171875, 16225, 16250, 69500, 3055525, -4000, 4000, -8100, 8100, 8125, -4050, 4050] \\\\\\\\\\\\\ [0, -1, -1540120, 155650, -2, 1, -3, 2, -8195, 3, -4, 8195, -5, 4, 5, -6, 6, -7, 7, -8, -8200, 8, -9, 8200, -10, 9, 10, -11, 11, -12, 12, -13, 13, -14, -15, 14, -40975, 15, -16, 1540120, 40975, 16, -17, 17, -18, 18, -19, 196625, -20, 19, 1540100, 20, -21, -1540100, 21, -22, 3080250, 22, -23, -3080250, 23, -24, -25, 24, 25, -26, 26, -27, 27, -28, -8220, 28, -29, 8220, -30, 29, 30, -31, 31, -32, 32, -33, -8225, 33, -34, 1540150, 8225, 344100, -35, 34, 35, -36, 36, -37, 393250, 37, -38, -8230, 38, 8230, -39, -344100, -40, 39, 40, -41, 41, -42, 42, -43, 9150625, 43, -44, -45, 44, 45, -46, 46, -47, 47, -48, -8240, 48, -49, 8240, -50, 49, 50, -51, 51, -52, 52, -53, -8245, 1540130, 53, -54, 8245, -55, 54, 55, -56, -16440, 56, -57, -8249, 16440, 57, -58, -8250, 8249, 58, 8250, -59, -60, 59, 8251, 60, -61, -16445, 61, -62, 16445, 16941375, 62, -63, -8255, 63, 8255, -64, -65, 64, 65, -66, -16450, 66, -67, 16450, 67, -68, 68, -69, 8260, -70, 69, 70, -71, 71, -72, 72, -73, 73, -74, -75, 74, 75, -76, 76, -77, 77, -78, -8270, 78, -79, 8270, -80, 79, 80, -81, 81, -82, 82, -83, -8275, 83, -84, 8275, -85, 84, 85, -86, -16470, 86, 16470, -87, 87, -88, -89, 8280, 88, -90, 89, 90, -91, -16475, 91, -92, 16475, 92, -93, -94, 93, -95, 94, 95, -96, -16480, 96, 16480, -97, 97, -98, -99, 98, -100, 99, 100, -101, 101, -102, 102, -103, 103, -104, -105, 104, 105, -106, -16490, 106, -107, 16490, 107, -108, -8300, -109, 108, 8300, -110, 109, 110, -111, -16495, 111, -112, 16495, 112, -113, 113, -114, 8305, -115, 114, -16499, 115, -116, -16500, 16499, 116, 16500, -117, 172150, 117, -118, 16501, -8310, 118, -119, 8310, -120, 119, 120, -121, -16505, 121, 16505, -122, 122, -123, -8315, 123, -124, 8315, -125, 124, 125, -126, 126, 16510, -127, 127, -128, -8320, 128, -129, 8320, -130, 129, 130, -131, 131, -132, -8324, 132, -133, -8325, 8324, 133, 8325, -134, -135, 134, 8326, 135, -136, -16520, 136, -137, 16520, 137, -138, -8330, 138, 8330, -139, -140, 139, -41100, 140, -141, 41100, 141, -142, 16525, 142, -143, 143, 8335, -144, -145, 144, 145, -146, 146, 16530, -147, 147, -148, 148, -149, 8340, -150, 149, 180375, 150, -151, 3055800, 151, -152, -153, 152, 153, -154, -155, 154, 155, -156, 156, -157, 157, -159, 8350, 158, -160, 159, 160, -161, 161, -162, 162, -163, 163, -164, -165, -41125, 164, 165, 41125, -166, 166, 16550, -167, 167, -168, -169, 168, -170, 169, 170, -171, 171, 16555, 172, -173, -174, -24750, 173, -175, 174, 24750, 175, -176, 176, 16560, 177, -178, -179, 178, -180, 179, 180, 181, -32950, 182, 32950, -183, -184, 8375, 183, -185, 184, 185, -186, 186, -187, 187, 8380, -189, -190, 189, 190, 191, 192, -193, -194, 193, -195, 194, 195, -196, 196, -197, 197, -198, -199, 198, -200, 199, 200, -201, 201, -202, -8395, 202, -204, 8395, -205, 204, 205, -206, 206, -32975, 32975, -208, -8400, -209, 8400, 208, -210, 209, 210, -211, -16595, -212, 211, 16595, 212, 8405, -214, 213, -215, 214, 215, -216, 216, -217, 217, -218, 218, -219, -220, 219, 220, -221, 221, -222, 222, -223, -224, 223, -225, 224, 225, -226, 226, -227, -32995, 16610, 227, 32995, -228, 7700625, 228, -229, -230, 229, 230, -231, 231, -33000, 232, 33000, -234, 233, -235, 234, 235, -236, -16620, -33005, 236, 16620, 33005, 237, -238, -239, 139500, 238, -240, 239, 240, -241, -16625, 241, 16625, -243, 242, -244, 243, -245, 244, 245, -246, 246, -247, 73975, 247, -248, -73975, -249, 248, -250, 249, 250, -251, 251, -252, -253, 252, 253, -254, 16637, -255, 254, 255, -256, -16640, 256, -257, 16640, -33025, 257, -258, 33025, -259, 258, 8450, -260, 259, 260, -261, -16645, 261, 16645, -262, -263, 262, -264, 263, -265, -41225, 264, -16649, 265, 41225, -16650, -266, 16649, 16650, 266, -267, -268, 267, 16651, 268, -269, -270, 269, 270, -271, -16655, 271, 16655, -272, -273, 272, 273, -274, -275, 274, 275, -276, 276, 16660, -277, 277, -278, 278, -279, -82200, -280, 279, 280, -281, -16665, 281, -282, 16665, 82200, 282, -283, 33050, 283, -284, 8475, -285, 284, -41245, 285, -286, 41245, 286, 287, -288, -289, 288, -290, -41250, 289, 290, 41250, -291, 291, -292, 16675, 292, -293, -294, 293, -295, 294, 295, 41255, -296, 296, -297, 16680, 297, -298, -299, 298, -300, 299, 360750, 300, -301, 301, -302, 302, -303, 303, -304, -305, 304, 82225, 305, -306, -82225, 306, -307, 307, -308, -309, 308, -310, 309, 310, 311, -312, 312, 313, -314, -315, 314, 315, 41275, 316, 317, -318, -319, 318, -320, 319, 320, -321, 321, 16705, -323, -324, 323, -325, 324, 325, -326, 326, -8520, -328, 327, -329, 8520, 328, -330, 329, 330, -331, 331, 332, -333, -8525, -334, 333, 8525, -335, 334, 335, -336, 336, -337, -338, 337, 8530, 338, -340, 340, 341, -342, 342, -343, 343, -345, 345, -348, 347, 348, 49500, -349, -350, 349, 350, -351, 351, -354, -355, 354, 355, -33125, 356, 33125, 357, -359, 8550, -360, 359, 360, -361, 361, 90475, -90475, -364, -365, 364, 365, 366, -369, -370, 369, 370, -371, 371, -373, -374, 373, -375, 374, 375, -376, 376, 377, -378, -379, 378, -380, 379, 380, -381, 381, -384, -385, 384, 385, -16770, 16770, 386, 387, -389, 8580, -390, 389, 390, -16775, 391, 16775, 392, -394, -24970, -395, 394, 24970, 395, -396, 16780, 396, -398, -24975, -399, 398, -400, 24975, 399, 400, -401, 401, 402, -404, -24980, -405, 404, 24980, 405, 406, -410, 410, -16795, 16795, -412, 411, 412, -415, 41375, 415, -16800, 16800, 416, -420, 420, 16805, -25000, -424, -425, 25000, 424, 425, 426, -429, -430, 429, 430, -431, 431, 432, -435, 435, -439, -440, 439, 440, 41400, -443, 443, -444, -445, 444, 445, -448, -449, 448, -450, 449, 450, -451, -33220, 451, 33220, -455, 82375, -82375, 455, -457, 457, -458, 458, -460, 460, -461, 461, -462, -66000, 462, -464, 463, -465, 464, 465, 66000, 466, 467, -470, 470, 172500, -33240, 33240, -474, -475, 474, 475, -476, 476, -33245, 33245, -480, 480, -484, -485, 484, 485, -486, -90600, 486, -489, -490, 489, 90600, 490, 16875, -494, -495, 494, 495, -496, 496, 74225, -74225, -498, -499, 498, -500, 499, 500, -501, -33270, 501, -502, 33270, 502, -503, -504, 503, -505, 504, 505, -506, -33274, 506, 33274, -33275, 33275, -8700, 33276, 8700, 508, -510, 509, 510, -511, 511, 33280, -514, -515, 514, 515, 74245, 16900, -74245, -519, -520, 519, 520, -74250, -33290, 33290, -524, 74250, -525, 524, 525, -526, 74255, 526, -74255, -528, -529, 528, -530, 529, 530, -531, -33299, -33300, 531, 33299, -532, 33300, 532, -533, -534, 33301, 533, -535, 534, 535, -536, 536, -538, -539, 538, -540, 539, 540, -541, 541, -542, 33310, -543, 542, -544, 543, -545, 544, 545, -546, 546, -547, 74275, -548, 547, -74275, 548, -549, -550, 549, 550, -551, 551, -552, -553, 552, 553, -554, -555, 82475, 554, -82475, 555, -556, 556, -557, -33325, 557, -558, 33325, -8750, 558, -559, 8750, -560, 559, 560, -561, 561, -562, -33330, -563, 562, 33330, 563, -564, -565, 564, 565, -566, 41525, 566, 16950, 567, 33335, -568, -569, 568, -570, 569, 570, -571, 571, 572, -574, -575, 574, 82495, 575, -82495, -576, 576, -578, 577, -82500, -579, 578, -580, 579, 580, -581, 82500, 581, -583, 582, -584, 583, -585, 584, 82505, 585, 586, 33355, -589, -590, 589, -41550, 590, 41550, 591, -593, 33360, -594, 593, -595, 594, 595, -596, 596, -598, -599, 598, -600, 599, 600, -601, 156250, 601, -602, 602, -603, -604, -156250, 603, -605, 82525, 604, 605, -606, 606, -608, 607, -8800, 608, -609, 8800, -610, 609, 610, -611, 611, 612, -613, -614, 613, -615, 614, 615, -616, 616, 17000, -617, -618, 617, -619, 618, -620, 619, 620, -621, 621, -622, 622, -623, -624, 623, -25200, -625, 624, 25200, 625, -626, 626, -628, 627, 628, -629, -630, 629, 630, -631, 361075, 631, 632, 90745, -634, -90745, 634, -635, 635, -636, 636, -90750, 637, -639, -640, -41600, 90750, 639, 640, 41600, 2777770, 641, 90755, -2777770, -644, -645, 644, 645, -646, 646, -648, 648, -649, -650, 649, 650, 651, 652, -654, -655, 654, 655, -656, 656, -658, -8850, 658, -659, 8850, -660, -41620, 659, 660, 41620, -661, 661, 662, -664, -665, -41625, 664, 665, 41625, 377500, -666, 666, 17050, 667, -670, 670, 2777780, 41630, -377500, 671, 672, -674, -675, 674, 675, 676, -679, -680, 679, 680, -682, 681, 682, -8875, 8875, -685, 685, -687, -688, 687, 688, 8880, -690, 41650, 690, -692, 692, -693, 8885, 693, -695, 695, 696, -698, 99000, 698, -700, 700, 2777750, -2777750, 82625, -705, 705, -710, 710, -66250, -714, -715, 714, 715, 66250, 716, 17100, -719, -720, 719, 720, 721, -724, -725, 724, 725, -726, 726, -730, 730, 1499850, -140000, -735, 735, -1499850, 736, 2777800, 140000, -739, -740, 739, 740, 41700, -744, -745, 744, 745, -746, 746, -748, -749, 748, -750, 749, 750, -751, 751, 752, -754, -755, 754, 755, -756, 756, -757, 757, -760, 760, -761, 761, -765, 765, 8960, -770, 770, -774, -775, 774, 775, -33545, 776, 33545, 777, -780, 780, -781, 781, -8975, 33550, 8975, 785, 33555, -790, 90900, 790, 793, -795, 795, 74525, -1663750, -74525, -799, -800, 799, 1663750, 800, 801, -8995, 8995, -805, 805, -9000, 9000, -810, 810, 9005, -814, -815, 814, 815, -819, -820, 819, 222000, 820, -821, 821, 17205, -823, -824, 823, 824, -825, 825, -826, 826, -33595, 33595, 827, -829, 829, -830, 830, 831, -33600, 832, 33600, 9025, -835, 835, -836, 836, 33605, -840, 840, -49995, 49995, -845, 845, 50000, -850, 850, -855, 82775, 855, -33625, 33625, -860, 860, -864, -865, 864, 865, -870, 870, -874, -875, 874, 875, 876, -879, 879, -880, 880, 881, 82800, -9075, 9075, -885, 885, -890, 890, -895, 895, 896, -899, -900, 899, 900, 901, -905, 905, 910, 91025, 915, -920, 920, -925, 925, 926, -930, 930, -58275, 58275, -935, 935, 9130, 940, -945, 945, -950, 950, -955, 955, -33725, 33725, 9150, 960, 965, -970, 970, -181200, -975, 975, -33745, 33745, 181200, -980, 980, -33750, 33750, 140250, -986, -33755, 986, 33755, -990, 990, -995, 995, -999, -1000, 999, 1000, -1001, 1001, 762850, -181225, -762850, 181225, -1005, 1005, -33775, 33775, -1008, 1008, -1010, 1010, 1015, 17400, 1017, -1020, 1020, -377850, 377850, -1025, 1025, -1030, 1030, -222220, -1040, 222220, 42000, 1040, -304150, -148500, 304150, -1045, 1045, 148500, -1050, 1050, -1051, 1051, -1055, 1055, -1056, 1056, -1057, -33825, -9250, 1057, 33825, 66595, 9250, -66595, -1060, -1061, 1060, 1061, -66600, -1065, 66600, 1065, 9259, 66605, -66605, -1070, 1070, -1075, 1075, -1080, 1080, -1081, 1081, -1085, 1085, -1086, 1086, -1087, 1087, 33855, -1089, -1090, 1089, -1091, 1090, 1091, -1094, -1095, 1094, 1095, -1096, 1096, -1098, -1099, 1098, -1100, 1099, 1100, -1101, -1102, 1101, 1102, -1104, -1105, 1104, 1105, -1106, 1106, -1107, -33875, 1107, -1108, 33875, -9300, 1108, -1109, 9300, -1110, 1109, 1110, -1111, 1111, -1112, 1112, -1114, 1113, 1114, -1115, 1115, -1116, 1116, -1117, 1117, 1118, -1119, -1120, 1119, 1120, -1121, 1121, 1122, 1123, -1124, -1125, 1124, 1125, 66660, -1126, 1126, 1127, -1130, 1130, -1131, 1131, 33900, -1135, 1135, 1136, 1137, 763000, -1140, 1140, 1141, -1145, 1145, -763000, -1150, 1150, -1155, 156800, 1155, -165000, -9350, 9350, -1160, 1160, -1161, 1161, 165000, -378000, -1165, 1165, -1166, -17550, 1166, 17550, 1167, -1170, 1170, 1171, 378000, -1175, 1175, -9370, 9370, -83100, -1180, 1180, 83100, -9375, 9375, 1185, 9380, -1190, 1190, -1195, 1195, 74925, -1199, -1200, 1199, 1200, -1201, 1201, -1205, 1205, 9400, -1209, -1210, 1209, 1210, 1211, -1215, 1215, -1216, -17600, 1216, 173250, 17600, -1220, 1220, 1221, 1222, -1224, -1225, 1224, 1225, -1226, 1226, -1230, 1230, -763100, 1232, -1235, 1235, 1236, -1239, -1240, 763100, 1239, 1240, -1244, 9435, -1245, 1244, 1245, -1246, 1246, -1248, -1249, 1248, -1250, 1249, 1250, -1251, 1251, -1252, -763120, 1252, -1254, -1255, 1254, 1255, -1256, 1256, -9450, 9450, -1260, 1260, -1261, 1261, 722150, -1264, -1265, 1264, 1265, 763130, 378100, -181495, -1270, 181495, 1270, -378100, -75000, 75000, -1274, -1275, 1274, 1275, 763120, -1276, 1276, -1280, 1280, -378120, 181505, -1285, 763150, 1285, -1290, -5555550, 1290, 5555550, 378120, -1295, 1295, -1296, 1296, -1299, -1300, 1299, 1300, 1301, 378130, -1305, 83225, -83225, 1305, 9500, -1310, 1310, -1315, 1315, 378150, -17700, 17700, -1319, -1320, 1319, 1320, -1321, 1321, -1324, -1325, 83245, 1324, 1325, -83245, -1326, -34095, 1326, 34095, -83250, -1330, 1330, 83250, -34100, 1332, 34100, -1335, 83255, 1335, -34105, 34105, -1339, -1340, 1339, 1340, 5555560, -1344, -1345, 1344, 1345, -1346, 1346, 75075, -75075, -1348, -1349, 1348, -1350, 1349, 1350, -1351, 1351, -1352, 1352, -1354, -1355, 83275, 1354, 1355, -1356, 1356, -34125, 34125, -1359, -1360, 1359, 1360, -1361, 1361, -1363, -1364, 1363, -1365, 1364, 1365, -1366, 1366, -1368, -1369, 1368, -1370, 1369, 1370, -1371, 1371, -1372, 1372, -1373, -1374, 1373, -1375, 1374, 1375, -1376, 1376, -1378, 1377, 1378, -1379, -1380, 1379, 1380, -1381, 1381, -1382, 1382, -1383, -1384, 1383, -1385, 1384, 1385, 1386, -1387, 1387, -1388, 1388, -1389, -1390, 1389, 1390, 1391, 1392, -1393, 1393, -1394, -1395, 1394, 1395, -1396, 198000, 1396, -1398, -83320, -1399, 1398, -1400, 1399, 1400, 763250, 83320, 1401, 1402, -1404, -1405, 1404, 83325, 1405, -83325, 1406, -9600, 9600, -1410, 1410, 83330, 1411, -1415, 1415, -1420, 1420, 378250, -1424, -1425, 1424, 1425, 1426, -9620, 9620, -1429, -1430, 1429, 1430, 1431, -9625, 9625, -1435, 1435, 9630, -1440, 1440, -1445, 1445, -1450, 206250, 1450, -1455, 1455, -34225, 1456, 34225, 9650, 1460, -1465, 1465, -17850, 17850, -1470, 1470, -1474, -1475, 1474, 1475, -1476, -34245, 1476, 34245, -1480, 1480, -34250, 83400, 34250, -1485, 1485, -17870, -58830, -34255, 17870, 58830, 1486, 34255, -1489, -1490, 1489, 1490, -17875, 17875, -1494, -1495, 1494, 1495, -1496, 17880, 1496, -1498, -1499, 1498, -1500, 1499, 1500, -1501, 1501, 1502, -1504, 1504, -1505, 1505, 1506, -1507, -34275, 1507, 34275, -1510, 1510, -1512, 1511, 1512, 1513, -1515, 1515, 17900, 1517, -1520, 1520, -1524, -1525, 1524, 1525, -1526, 1526, -1530, 1530, 1535, -1540, 763400, 1540, -1545, 1545, -26125, -1550, 26125, 181775, 1550, -34320, 34320, -1555, 1555, -34325, 34325, 9750, -1560, 1560, 1562, 1565, -1570, 1570, 378400, -1575, 1575, -34345, 34345, 181800, 1580, -34350, 34350, -34355, 34355, -1590, 1590, -17975, 17975, -1595, 1595, -34365, 34365, 99900, -1600, 1600, -34370, 34370, -1605, 1605, -34374, -34375, 34374, 34375, 34376, 9800, -17995, 17995, 34380, -1615, 1615, -18000, 75345, 18000, 34385, -75345, -1620, 1620, -75350, 18005, 75350, -1624, -1625, 1624, 1625, 75355, -34395, 1626, -75355, 34395, -1630, 1630, 34400, -1635, 1635, 34405, -1639, -1640, 1639, 1640, 18025, -1644, -1645, 1644, 1645, -1646, 1646, 75375, -75375, -1648, -1649, 1648, 1649, -1650, 1650, -1651, 1651, 1652, -1654, 1654, -1655, 1655, 1656, 34425, -1660, 1660, 1661, 34430, -67200, -1664, 1664, -1665, 1665, 42625, 67200, 1666, -1670, 1670, -1675, 1675, -1680, 1680, -9875, 9875, 1685, 1690, -1700, 1700, -9895, 9895, -1705, 1705, -34475, 34475, 9900, 1710, 9905, -1715, 1715, -1718, 1718, -1725, 1725, -34495, 34495, 34500, -18120, 18120, 34505, -1740, -18125, 1740, 18125, -1745, 1745, 75475, -75475, -1750, 1750, -1755, 1755, 34525, -18145, 1760, 18145, -18150, 18150, 75495, -75495, -1770, 1770, -75500, 18155, 75500, -1775, 1775, 1776, 75505, -75505, 1780, -9975, 9975, -1790, 1790, -1795, 1795, 75525, 18180, -75525, -1799, -1800, 1799, 1800, 1801, -9995, 9995, -1805, 1805, -10000, 10000, 1810, 10005, 18200, -1820, 1820, -26400, -1825, 26400, 1825, 1830, 10025, 67375, -67375, -75570, 75570, -1845, 1845, 75575, -75575, -1850, 1850, -1851, 1851, -1855, 1855, 34625, -1860, 1860, -1865, 1865, 75595, -304975, -75595, 304975, -1870, 1870, -75600, 75600, -1874, -1875, 1874, 1875, 75605, -34645, 1876, -75605, 34645, -1880, 1880, 34650, 1885, 75615, 34655, -75615, -1890, -75620, 1890, 75620, -1895, -75624, 1895, 75625, -75625, 75624, -1900, 75626, 1900, 75630, -1905, 1905, 75635, 10101, -1915, 1915, 378750, 75645, 18300, -75645, -1920, 1920, -26500, 75650, -1924, -1925, 26500, 1924, 1925, 75655, 1926, -1930, 1930, 10125, 1935, -1945, 1945, 75675, -1950, 1950, 75680, 83875, 1955, 1960, -67500, 67500, -1970, 1970, -1975, 1975, -1980, 1980, 10175, 1985, -165825, 165825, -1990, 1990, -1995, 124875, -124875, 1995, 75725, -75725, -1999, -2000, 1999, 2000, 2001, -2005, 2005, 2010, 75745, -75745, -2020, 2020, 75750, -2025, 2025, 75755, 2030, 34800, 2035, 444400, 18425, 75775, -2050, 2050, 2055, 2080, 84000, -305200, -2095, 2095, -2100, 2100, 305200, 2105, -34875, 34875, -2120, 2120, -2125, 2125, 2130, -305245, 305245, -149600, -2145, 2145, -305255, 75875, 149600, 305255, -2150, 2150, 305250, -2155, 2155, 34925, 2160, -2165, 2165, 75895, -75895, 75900, -2175, 2175, 75905, -2180, 2180, -346250, 346250, 305300, -2195, 2195, 616605, -2200, 2200, -2205, 2205, -34975, 34975, 10400, -2210, 2210, -2215, 2215, -2216, -18600, -2217, 2216, 18600, 2217, -2219, -2220, 2219, 2220, -2221, 2221, -2222, 2222, 2223, -2224, -2225, 2224, 2225, -34995, 2227, 34995, -2230, 2230, 35000, -2235, 2235, 35005, -2240, 2240, -18625, 18625, -2245, 2245, -133320, -2250, 2250, 133320, -166095, 166095, -2255, 2255, 35025, -2260, 2260, -141525, 141525, -166105, 166105, -2275, 2275, 313575, 1681650, -2300, 2300, 10500, 313600, 2310, 2312, -2320, 2320, 2325, -35100, 35100, 16803875, -18725, 18725, -2350, 2350, -10545, 10545, 35125, -166200, -18745, 18745, -305470, 305470, 166200, -2365, -18750, 2365, 18750, -2370, 2370, 18755, -2375, 2375, -2380, 2380, -149845, 149845, 18775, 149850, 305500, -2395, -149850, 2395, -149855, 149855, -2400, -305500, 2400, -2405, 2405, -10600, 321900, 10600, -305515, -2415, 305515, 2415, -149875, -305525, 305524, 149875, 305525, 305526, -2420, 2420, -27000, -305524, 27000, -2425, 2425, 305535, -2430, 2430, 10625, -2440, 2440, 305550, -2445, 2445, 76175, -2450, 2450, -2455, 2455, -68000, -2465, 68000, 2465, -2470, 2470, 305580, -2474, -2475, 2474, 2475, -2476, 2476, -166320, -2480, 2480, 166320, -2485, 2485, -2490, 2490, 18875, -2495, 2495, -2499, -2500, 2499, 2500, -2501, 2501, -2505, 2505, 166350, -2510, 2510, -166350, 18900, -2520, 2520, 76250, -2525, 2525, 158175, -166365, 166365, -2530, 2530, -166375, 166374, -10725, 166375, 10725, -166374, 166376, -2545, 2545, -363000, 166385, -2550, 2550, -2555, 2555, -10750, 1526250, 363000, -1526250, 10750, 166400, -2570, 2570, -27150, 27150, 756250, -756250, 68125, 166430, -68125, -2595, 2595, -2600, 2600, -2605, 2605, 10800, -371250, 371250, -27195, -2620, 27195, 2620, -27200, -2625, 27200, 2625, -2630, 2630, -166475, 166475, -2640, 2640, -27220, -2645, 27220, 2645, -2649, -27225, -2650, 2649, 27225, 2650, -2651, 2651, -166495, 166495, -2655, 2655, 764500, -166500, -2660, 2660, 166500, -2664, 2664, -2665, 379500, 2665, 166505, -2670, 2670, -27250, -2675, 27250, 2675, 338550, -2680, 2680, -346750, 346750, 166525, -2690, 2690, -2695, -305795, 2695, 305795, 305805, -2699, -2700, 2699, 2700, -2701, 2701, -2705, 2705, -35475, 35475, -10900, 10900, -2710, 2710, -2715, 2715, -2719, -2720, 2719, 2720, -2721, 2721, -2724, -2725, 2724, 2725, -2726, 2726, -2730, 2730, -2735, 2735, -2739, -2740, 2739, 2740, -2744, -2745, 2744, 2745, -2746, 2746, -2748, -2749, 2748, -2750, 2749, 2750, -2751, 2751, -2752, 2752, -2754, -2755, 2754, 2755, -2756, 2756, -10950, -2759, 10950, -2760, 2759, 2760, -2761, 2761, -2763, -2764, 2763, -2765, 2764, 2765, -2766, 2766, -2768, -2769, 2768, -2770, 2769, 2770, -2771, 2771, -2772, -2773, 2772, 2773, -2774, -2775, 2774, 2775, -2776, 2776, -2777, 2777, -2778, -2779, 2778, -2780, 2779, 2780, -2781, 2781, 2782, -2784, 2784, -2785, 2785, 2786, 1542900, 2787, -346850, -2789, -2790, 2789, 2790, 2791, 346850, -2794, -2795, 2794, 2795, -2796, 2796, -2798, -27375, -2799, 2798, -2800, 27375, 2799, 2800, -346870, 2801, -10995, 2802, -2804, 10995, 346870, -2805, 2804, 2805, 2806, -166645, -11000, 166645, 166650, 11000, -2810, 2810, 2811, -166650, -11005, 11005, 166655, -2815, 2815, -2820, 2820, 346880, -2824, -27400, -2825, 2824, 27400, 2825, 2826, -2829, -2830, 2829, 2830, 2831, 346900, 2835, 2840, -2845, 2845, -2850, 2850, 3083020, -3083020, -11045, 11045, -2855, 2855, 35625, -11050, 11050, -2860, 2860, -11056, 11056, -19250, 19250, -11060, 11060, -2870, 2870, 3083030, -27450, -2875, 27450, 2875, -2880, 2880, -60225, 60225, -11075, 11075, 2885, 2886, -11080, 11080, -2890, 2890, -11086, -2895, 11086, 2895, -11090, 412500, -27475, 11090, -2899, -2900, 27475, 2899, 2900, 2901, -11095, 11095, -2905, 2905, -11099, -11100, 11099, 11100, -11101, 11101, -2910, 2910, -11105, -11106, 11105, -2914, 11106, -2915, -11107, 2914, 2915, 11107, -2916, -11109, 2916, 11109, -11110, 11110, -11111, -27495, 11111, -2920, 27495, 2920, 11112, 11113, -11115, -27500, 11115, -2925, 27500, 11116, 183150, 2925, 11117, -11120, 11120, -27505, 27505, 11121, 11122, 2930, -11125, 11125, 68475, -68475, -2940, 2940, 347000, -2945, 11136, 2945, -27525, -2950, 27525, 2950, -2955, 2955, -35725, 35725, -2960, 2960, -68500, -11155, 166800, 11155, -2965, 68500, 2965, -2969, 11160, -2970, 2969, 2970, 175000, -2971, 2971, -27550, -2975, 11166, 27550, 2975, 306075, -35745, 35745, -2980, 2980, -35750, 35750, 35755, -2990, 2990, 19375, -2995, 2995, 76725, -76725, -2999, -3000, 2999, 3000, -3001, 3001, -11195, 11195, -3005, 3005, -11200, 35775, 11200, -3009, -3010, 3009, 3010, -11205, -3013, -3014, 11205, 3013, -3015, 3014, 3015, -3016, 3016, -3018, -3019, 3018, -3020, 3019, 3020, -3021, 3021, -3022, -3023, 3022, 3023, -3024, -27600, -3025, 3024, 27600, 3025, -3026, 3026, 3027, -3028, -3029, 3028, 3029, -3030, 3030, -3031, 3031, 3032, -3034, 3034, -3035, 3035, -19420, 3036, 19420, 3037, -3040, -44000, 3040, 44000, -19425, 3041, 19425, 666600, -3045, 3045, 19430, -3047, 3047, -27625, -3049, -3050, 27625, 3049, 3050, 3051, -3052, 3052, 3053, -666600, -3055, 3055, -60400, 60400, -11250, 3057, 11250, -3060, 3060, -3065, 3065, -27645, -3070, 27645, 3070, -27650, -3075, 27650, 3075, -27655, -3079, 27655, -3080, 3079, 3080, 3081, -11275, 11275, 3085, 166925, 68625, -68625, -3090, 3090, -3095, 3095, 7638125, -27675, -3099, -3100, 27675, 3099, 3100, -3101, 3101, -3105, 3105, -11300, 11300, -3110, 3110, 830500, -3114, -3115, 3114, 3115, 19500, -3119, -27695, -3120, -830500, 3119, 27695, 3120, -3121, 3121, -3123, -27700, -3124, 3123, -3125, 27700, 3124, 3125, 3126, 3127, -3129, -27705, 3129, 27705, -3130, 3130, 3131, 3135, 3136, -27715, -3140, 27715, 3140, 19525, -27720, -3145, 27720, 3145, -27725, -3149, -3150, 27725, 3149, 3150, -60495, 60495, 3151, -27730, 27730, -3155, 3155, -60500, 60500, 3160, -60505, 60505, -68700, -27740, 27740, 68700, -27745, 27745, -3170, 3170, -27749, -27750, 27749, 27750, -3175, -27751, 3175, 27751, -27755, 27755, -3180, 3180, -27760, 453750, 27760, 3185, -27764, -27765, 68725, 27764, -68725, 27765, -3190, 3190, -27769, -27770, 27769, 27770, -27771, -3195, 27771, 3195, -27773, -27774, 27773, -27775, 27774, -3200, 27775, 3200, 27776, 27777, -27779, 27779, -27780, 27780, 27781, 3205, 68745, 27785, -68745, 27786, -68750, -27790, 27790, 68750, 19600, -27795, 68755, 27795, -68755, -3220, 3220, 847000, -27799, -27800, 27799, -3225, 27800, 3225, 27801, -27805, 27805, -3230, 3230, -36000, 36000, 27810, -3235, 3235, 68775, -68775, -3240, 3240, -27820, -3245, 27820, 3245, 76975, -76975, -27825, -3249, -3250, 27825, 3249, 3250, 3251, 27830, -3255, 3255, -60600, 60600, 36025, 27835, 3260, 68800, 76995, -76995, -3270, 3270, 77000, -3275, 27850, 3275, 77005, -3280, 27855, 3280, -68820, -3285, 3285, 68820, -3289, 3289, -3294, -3295, 3294, 3295, -3296, 77025, 3296, -3298, -3299, -27875, 3298, 3299, -3300, 27875, 3300, 3301, -36070, 36070, 3302, -3304, 3304, -3305, 3305, 3306, 3311, 36080, 3315, -27895, -3320, 27895, 3320, -3324, 27900, -3325, 3324, 3325, 208125, -3329, 3329, -3330, 27905, 3330, 3331, -3335, 3335, 3336, 68875, -68875, 3340, -3350, 27925, 3350, -3355, 3355, -3360, 3360, 3365, -3370, 3370, -27950, -3375, 27950, 3375, 3380, 3385, 3390, -3395, 3395, -27975, 27975, 3400, 3405, -11600, 11600, 3410, 19800, -27995, 27995, 3420, -28000, 28000, 3425, -28005, 28005, -60775, 60775, 347500, -44395, 3435, 44395, 3437, 44400, 44405, -28025, -3450, 28025, 3450, -11655, -69000, 11655, -3465, 3465, 69000, -3468, -28045, 3468, 28045, -3475, 28050, 3475, 28055, 3480, -60830, 60830, 69025, -69025, -3500, 28075, 3500, 110000, -3510, 3510, 13888875, -150975, 150975, -3520, 3520, 3525, 36300, -3540, 3540, -151000, -3545, 3545, 151000, 77275, -28125, 1666500, 28125, -3550, 3550, -69100, -3565, 69100, 3565, -52725, -3574, 52725, -3575, 3574, 3575, 3576, 3585, 69125, -69125, -3590, 3590, -3595, 3595, 19980, -3599, -3600, 3599, 3600, 3601, -3605, 3605, 3610, -20000, 20000, 1527350, -1527350, -3620, 3620, -3625, 3625, -3630, 3630, -11825, 36400, 11825, 3635, 93750, 3640, -3650, 3650, 1666650, 3655, 3660, -28250, 28250, -3675, 3675, 3680, -11875, 11875, 3685, 69225, -69225, -3695, 3695, -3700, 3700, -61045, 61045, 3703, -61050, 61050, 69245, -69245, 61055, -69250, 69250, 69255, -69255, -3720, 3720, -3725, 28300, 3725, -28305, -3730, 28305, 3730, 69275, -69275, -3740, 3740, -151200, -3745, 3745, 151200, -3749, -3750, 3749, 3750, 3751, -3755, 28330, 3755, -61100, 61100, -61104, 61104, 3760, 61105, 61106, 61110, -3770, -151225, -77500, 3770, 151225, 77500, -3775, 3775, -3780, 3780, -3781, 3781, -69320, 749250, 69320, -749250, 69325, -69325, -151245, 151245, 151250, 306900, -151250, -151255, 151255, 3800, 3805, -12000, 12000, 69345, -69345, -69350, 69350, -151275, 61160, 151275, 69355, -69355, 28400, -3825, 3825, 69365, -69365, -69370, 36600, 69370, -69374, 69375, -69375, 69374, 44800, 69376, -3845, 69380, 3845, 151300, 69385, -3850, 3850, 159500, -3855, 3855, 69395, -69395, 36630, 69400, -20250, 20250, 69405, -3870, 3870, -3875, 3875, 1527600, -3880, 3880, -3885, 3885, -12080, 69425, 12080, 3890, -3895, 3895, 69430, -1527600, -3900, 3900, -12095, 12095, 3905, -12100, 167750, 12100, -12105, 12105, 3920, 1527620, -1527620, -12120, 12120, 1527630, 69475, -69475, -3950, 3950, 1527650, -12150, 69495, 12150, -69495, 3960, 69500, -20350, 20350, 69505, -3975, 3975, 69525, -3995, 3995, -4000, 4000, -4005, 4005, -12200, 12200, 12210, -4025, 4025, 12221, 61380, 765900, 45000, -151500, -4045, 4045, 151500, -4050, 4050, -4055, 4055, -12250, 12250, -4070, 4070, -151525, 151525, -4075, 4075, 69625, -4095, 4095, -4100, 4100, -4105, 86025, 4105, -36875, 36875, -4110, 4110, -4115, -20500, 4115, 69650, 20500, -4120, 4120, -4124, -4125, 4124, 4125, 4126, -4130, 12321, 4130, 4135, -45100, 45100, 4140, -4145, 4145, -4150, 4150, 4155, -12350, 12350, 168000, -20550, 20550, 1527900, 4175, -12370, 12370, -4180, 4180, -12375, 12375, -12380, 12380, -4195, 4195, -831600, -4200, 4200, 4205, -12400, 12400, 249975, -249975, -20600, 20600, 831600, 4225, -20620, 20620, -20625, 20625, 20630, -4250, 4250, -61600, 61600, -12450, 12450, -61604, 61604, 61606, 20650, 61610, -78000, 78000, 4275, -12475, 12475, -28875, -610500, 28875, -4300, 4300, 610500, -12495, 12495, -12500, 12500, -12505, -1388750, 12505, 1388750, 20700, -4320, 4320, -12525, 12525, 69875, -69875, -45300, 45300, -4345, 4345, -4350, 4350, 37125, -12550, 12550, -307470, 307470, 20750, -4370, 4370, -78100, 78100, -4375, 4375, 4380, -1388850, -4390, 4390, -78120, 1388850, 78120, -4395, 4395, 69930, -4399, -4400, 4399, 4400, 4401, 78130, 4405, -12600, 12600, -45370, 4410, 45370, -45375, 45375, 45380, 1388880, 78150, -29000, 29000, -4425, 4425, -37200, -1388870, -12625, 37200, 12625, 1388870, 242000, 69975, -69975, -4440, 4440, -4444, 4444, -831850, 831850, 4455, -12650, 69995, 12650, -69995, -70000, -831870, 70000, 1388900, 831870, 70005, -4475, 4475, 4480, 831880, 70025, 45450, -4495, 4495, 831900, -4500, 4500, -111000, 4505, 111000, 20900, 78250, 4525, -61875, 61875, 4550, -12750, 12750, -29145, 29145, -12765, -29150, 1389000, 12765, 29150, 4575, -29155, 29155, 70125, -70125, 111095, -111095, -111100, 111100, -37375, 37375, 111105, -111106, -111105, 111106, -111110, 152070, 111110, -152070, 21000, -152075, 111112, 152075, 111116, 4625, 4629, 37400, 78375, 4650, -4670, 4670, 78400, -4675, 4675, 4680, 45650, 1831500, -111200, 111200, -37475, 37475, -37495, 37495, -4730, 4730, -37500, 37500, 37505, -4750, 4750, 37525, 832150, 21175, -4795, 4795, 4800, 4805, -13000, 13000, 62160, 103125, 611050, -29415, 29415, -29425, 29425, 37625, -307970, 307970, -4875, 4875, -152345, 152345, -308000, 152350, -152350, -152355, 152355, -4900, 308000, -135975, 4900, 135975, 611105, -308015, 308015, 168750, -168750, -308024, 78650, -308025, 308024, 308025, 308026, -4930, 4930, -13125, 13125, 308035, -4950, 4950, 308050, -1676100, 1676100, -4975, 4975, 308080, -4990, 4990, -4995, 4995, -5000, 5000, -5005, 5005, -13200, 13200, 78750, -5025, 5025, -13225, 37800, 13225, -5040, 5040, -152500, 152500, -5050, 5050, -13245, 13245, -136125, 136125, -13250, 13250, 5060, -299970, -13255, 299970, 13255, 332750, -13275, 13275, 5087, 70625, -5100, 5100, 832500, 152570, -152570, -152575, 152575, -13315, 13315, -29700, -5125, 29700, 5125, -13320, 13320, -13325, 13325, -152595, 152595, -152600, 152600, -152605, 152605, -62500, 62500, -152615, 152615, -152620, -1111100, 1111100, 144430, -152624, 152620, 152626, -152625, 152624, 152625, 152630, 152635, -13375, 13375, -152645, 152645, 152650, 152655, 5200, 1111111, 70750, -21600, 21600, 152675, -5220, 5220, -5225, 5225, 152680, -5230, 5230, -13440, 13440, -5250, 5250, -5255, 5255, -13450, 13450, -5275, 5275, -13470, 13470, -5280, 5280, -13475, 13475, -5285, 5285, -13480, 13480, 152750, -5295, 5295, -5300, 5300, -13495, 13495, -5305, 5305, -13500, 13500, 1529000, -13505, 13505, -333000, 333000, -13525, 13525, -21725, 21725, -29920, 29920, -5350, 5350, 38125, -13550, 13550, -5375, 5375, -13575, 13575, -29965, 29965, -29970, 29970, -5395, 5395, -29975, -5400, 29975, 5400, -13595, -29980, 13595, 29980, -5405, 5405, -13600, 13600, -13605, 13605, -30000, -5425, 30000, 5425, -13620, 13620, -5430, 5430, -13625, 13625, 169275, -5435, 5435, -152895, -13630, 152895, 13630, -5440, 5440, 308550, -5444, -5445, 5444, 5445, 152900, -5450, 5450, 152905, -5455, 5455, -13650, 1537350, 13650, -1537350, -5470, 5470, 308580, -5475, 5475, -5480, 5480, -5490, 5490, 21875, -5495, 5495, -5499, -5500, 5499, 5500, -5501, 5501, -13695, 13695, -5505, 5505, -13700, 13700, -5510, 5510, -13705, 13705, -5520, 5520, -5525, 5525, -13720, 13720, -5529, -5530, 5529, 5530, -5531, 5531, -13725, 13725, -5535, 5535, -13730, 13730, -5539, -5540, 5539, 5540, -5543, -5544, 5543, -5545, 5544, 5545, -5546, 5546, -13740, -5548, -5549, 13740, 5548, -5550, 5549, 5550, -5551, 5551, -5552, -13745, 5552, -5553, -5554, 13745, 5553, -5555, 5554, 5555, -5556, 5556, -13749, -13750, -5558, 5557, 13749, 13750, 5558, -5559, -13751, 5559, -5560, 13751, 5560, -5561, 5561, -13755, 5562, 169400, 13755, -5564, 5564, -5565, 5565, 5566, -13760, 5567, 13760, -5570, 5570, 5571, -30150, -5575, 30150, 5575, 3085800, -13770, 13770, -5579, -5580, 5579, 5580, 5581, -13775, 13775, -5585, 5585, -13780, 13780, -5590, -21975, 5590, 21975, 349650, -5595, 5595, -5599, -5600, 5599, 5600, 5601, -13795, 13795, 390625, -5605, 5605, -13800, 13800, -5609, -5610, 5609, 5610, -21995, 333295, 21995, -333295, 5611, -13805, 13805, -22000, 22000, -30195, -5620, 30195, 5620, 22005, -13815, 13815, -5625, 5625, -13820, 333305, -30205, 13820, 693750, 30205, -5630, 5630, -693750, -13825, 13825, 5635, -13830, 13830, 8394375, 22025, -5645, 5645, -13840, 13840, -30225, -5650, 30225, 5650, -13845, 13845, -5655, 5655, 333330, -13849, -13850, 13849, 13850, -13851, 13851, 5660, 6944375, -13855, 13855, -30240, 30240, 5665, 5666, -13860, 13860, -30245, 30245, -13864, -13865, -30249, 13864, -30250, 13865, 30249, 30250, -5675, -30251, 5675, 30251, -13869, -13870, 13869, 13870, -13871, 30255, 13871, 5680, -13873, -13874, 13873, -13875, 13874, 13875, -30260, 30260, 13876, 5685, 13877, -13879, 13879, -13880, 226875, 13880, 13881, 13885, 13886, 13887, -13888, 13888, -13890, 13890, -30275, 30275, -5700, 5700, -13895, 13895, 1554000, 5705, -13899, -13900, 13899, 13900, 13901, -13905, 13905, 153175, 13910, -30295, 30295, 153180, -13920, 13920, -30305, 30305, -816750, 816750, -13925, 13925, 13930, 13935, -5750, 5750, -13945, 13945, -13950, 13950, 13955, -5770, 5770, -5775, 30350, 5775, -13970, 13970, -5780, 5780, -13975, 13975, -13980, 13980, -5795, 5795, -13990, 13990, -5800, 5800, -13995, 13995, 55555555, -5805, 5805, -13999, -14000, 13999, 14000, 14001, -14005, 14005, -22200, 22200, 14010, -30400, -5825, 30400, 5825, -14020, 14020, -5830, 5830, -22215, 22215, -14025, 14025, -5835, -22220, 5835, 22220, -14030, 22222, 14030, -30415, 30415, -22225, 22225, -55000, 55000, -5850, 5850, -22240, 5855, 22240, 14050, 14055, 833250, -5885, 1734375, 5885, -30465, 30465, 22275, -30470, 30470, -30475, 30475, -5900, 5900, -14100, 14100, 46875, -30495, 30495, 833325, -30500, 30500, 333600, -14120, -30505, 14120, 30505, -14125, -30510, 14125, 30510, -30514, 14130, 30514, -5940, 5940, 350000, -30519, -30520, 30519, 30520, -30521, 30521, -30523, -30524, 30523, 30524, -30525, 30525, -5950, 30526, 5950, 30527, -30529, -14145, 30529, -30530, 14145, 30530, 30531, 14150, 30536, -71500, 14155, 30540, 71500, -30545, 30545, -5975, 30550, 5975, 30552, 30555, 14175, -5994, 5994, -5995, 5995, -30575, -6000, 30575, 6000, 30580, -6005, 6005, 30585, 194425, 22400, -6025, 6025, -6040, 6040, -6045, 6045, -6049, -30625, 6049, -6050, 30625, 6050, -6051, 6051, -6055, 6055, -14250, 14250, 30635, 6060, 4159375, 30650, 6075, 15415125, -6080, 3110800, 6080, -38850, 38850, 14275, -6094, 6094, -6095, 6095, -6099, -6100, 6099, 6100, -6101, 6101, -6103, 6103, -6104, -6105, 6104, 6105, 6106, 6107, -14300, -6109, 14300, 6109, 6110, 6111, 694250, 6115, -694250, 22500, 6116, 38885, -6120, 6120, -6125, 6125, -55280, 55280, -6130, 6130, -55300, 55300, -6150, 6150, -6155, 6155, -6159, 6159, 6160, 6161, 6165, -30745, 30745, 6180, -14375, 14375, -6195, 6195, -30775, -6200, 30775, 6200, -6205, 6205, -14400, 14400, 694350, -30790, 30790, 6215, -694350, 47175, 6216, -6220, 6220, -30799, -30800, 30799, -6225, 30800, 6225, 30801, 30802, -6230, 6230, 30833025, -14425, 39000, 14425, 30810, 14430, -6240, 6240, 14435, -6245, 6245, 694380, -55400, 694370, -6249, 55400, -6250, 6249, 30825, 6250, -6251, -694370, 6251, -6255, 6255, -6260, 6260, -6270, 6270, -153725, 153725, -6275, 6275, -55430, 55430, -6280, 30855, 6280, -14475, 694400, 14475, -6295, 6295, -55450, 55450, -6300, 6300, -14495, 14495, -6305, 6305, -14500, 14500, 14505, -6320, 6320, -55475, 55475, -6325, 6325, -14520, 14520, -6330, 6330, 14525, -55495, 55495, -55500, 55500, -6350, 6350, -55505, 55505, -6360, 6360, 14560, 907500, -6370, 6370, -55525, 55525, -6375, 6375, -14570, -55530, 14570, 55530, -6380, 6380, -55535, -14575, 694500, 55535, 14575, 6385, 3815625, -14580, -55540, 14580, 55540, -55544, 55544, -55549, -55550, 55549, 55550, -55551, -6400, 55551, 6400, -55553, -55554, 55553, 55554, -55555, 55555, 55556, 55557, -55559, 55559, -55560, 55560, 55561, 55566, 55570, -55575, -31000, 55575, 31000, -137500, 55580, 137500, 55585, 14625, 6435, 1694000, -55595, 55595, 915750, -55600, 55600, -6450, 6450, -55605, 55605, 55615, -6475, 6475, -6480, -63825, 6480, 63825, 145750, -145750, 1890625, -31070, 31070, -6495, 6495, -31075, 55650, -6500, 31075, 6500, 31080, -6505, 6505, -14700, 14700, 31085, -153975, 153975, -6525, 6525, 55680, -153995, 153995, -154000, -6545, 6545, 154000, -31125, 31125, 6550, 154005, 31130, -14750, 14750, 154025, -6575, 6575, -6590, 6590, -6595, 6595, -6599, -6600, 6599, 6600, -6601, 6601, -14795, 14795, -6605, 6605, 72145, -6610, -72145, 6610, 72150, 72155, -6620, 6620, -31200, -6625, 31200, 6625, -555500, 555500, -6630, 6630, -14825, 14825, -14840, -31225, 14840, 55800, -6650, 31225, 6650, 416250, -14845, 14845, -6655, 6655, -14849, -14850, -170500, 14849, -555530, 14850, -6659, -14851, 555530, 6659, 14851, 6660, 6661, 170500, -14855, 14855, 6665, 6666, -14860, 14860, -31245, 31245, -555545, -31250, 555545, 31250, 760350, -31255, -760350, 55830, 31255, -14875, 14875, 555565, -6695, 6695, -555554, -31275, -555555, 555554, 555555, -6700, 31275, 6700, 555556, 555580, 6710, 3471875, -14905, 14905, 178750, -6720, 6720, -6725, 31300, 6725, -6730, 6730, 555610, -6740, 6740, -6745, 555600, 6745, 80475, -80475, -6749, -6750, 6749, 6750, -6751, 6751, -6755, 6755, -14950, 14950, -6760, 6760, -6765, 6765, -6770, 6770, -31350, -6775, 31350, 6775, -6780, 6780, -14975, 14975, 31360, 14985, -6795, 6795, -31375, -6800, 31375, 6800, -14995, 14995, -6805, 6805, -15000, 15000, -15005, 15005, -6815, 6815, 154275, -6820, 6820, -15015, 15015, -6825, 6825, -6830, 6830, -15025, 15025, -6840, 6840, -6845, 6845, -56000, 56000, -6849, -6850, 6849, 6850, -6851, 6851, -15045, 15045, -6855, 6855, -15050, 15050, -6860, 6860, -6864, -6865, 6864, 6865, 695000, -6869, -6870, 6869, 6870, -6871, 6871, -15065, -6873, -6874, 15065, 6873, -6875, 6874, 6875, 6876, -15070, 6877, 15070, -6879, 6879, -6880, 6880, 6881, -15075, 15075, 6885, 6886, -15080, 15080, -6890, 6890, -6895, 6895, -15090, 15090, -6899, -6900, 6899, 6900, 6901, -15095, 15095, -6905, 6905, -15099, -15100, 15099, 15100, -15101, 15101, 6910, 30858025, -15105, 15105, -15110, 15110, -6920, 6920, -15114, -15115, 15114, 15115, -31500, 31500, -6925, 6925, -15119, -15120, 15119, 15120, -15121, 15121, 6930, -15123, -15124, 15123, 15124, -15125, 15125, 15126, 6935, 15127, -15129, 15129, -15130, 6937, 15130, -6940, 15131, 6940, -6943, 15135, 6943, -6945, 15136, 6945, -15140, 777000, 15140, 56100, -6950, 6950, -15145, 15145, 6955, -15149, -15150, 15149, 15150, 56110, 15151, 6960, 88880, -15155, 15155, 72500, 15160, -6970, 6970, -6975, 6975, -15170, 15170, -6980, 6980, -15175, 15175, 27777775, 6985, 15180, -6990, 6990, 23375, 15185, -6995, 6995, -6999, -7000, 6999, 7000, 7001, 7005, 15200, 7010, 97125, 15205, -7020, 7020, -7025, 7025, 7030, 416625, -15225, 15225, 64380, 15235, -31625, 31625, 7050, -15245, 15245, 7055, -15250, 15250, 31635, -72600, 15255, 72600, 15260, 15262, 15275, -7095, 7095, -7100, 7100, -39875, 39875, -15300, 15300, -7120, 7120, -7125, 7125, 7130, 1555400, -7140, 7140, -7145, 7145, -7149, -7150, 7149, 7150, 7151, -15345, 15345, 7155, -15350, 15350, 277500, 7160, 48125, -277500, 7175, 138250, -138250, -15375, 15375, -7195, 7195, -15390, 15390, -7200, 7200, -15395, 15395, -7205, 7205, -15399, -15400, 15399, 15400, 15401, 15405, -7215, 7215, 15410, -31800, -7225, 31800, 7225, 15425, -7250, 7250, 30555525, 15455, -23650, 72800, 23650, -81000, 81000, 7275, 187500, 7280, -15475, 15475, -31875, 31875, -15495, 3333300, 15495, -15500, 15500, -15505, 15505, -277650, 457875, 277650, -31895, 31895, 31900, 31905, -15525, 15525, 72875, -72875, -7350, 7350, 277700, -72900, 72900, -277700, -7370, 7370, -7375, 7375, -15570, 15570, -7380, -277720, 7380, -15575, 15575, -277725, 277725, 277720, 859375, 81125, -81125, -7400, 7400, -15595, 15595, -15600, 171250, 15600, -277750, -122100, 277750, -171250, -15605, -277745, 15605, 277745, 122100, -7420, 7420, -277755, -15615, 277755, 15615, -277765, 7425, -138500, 277765, -294150, 294150, -15620, 15620, 138500, 7430, -15624, -15625, 15624, 15625, -277774, -277775, 15626, 277774, 277775, -277770, 277770, 15630, -7440, 277780, 48400, 7440, 1678600, 15635, 277776, -7445, 7445, -7450, 7450, -15645, 277785, 15645, 89375, -1678600, 15650, -277795, 15655, 277795, 277805, 277800, -7470, 7470, -7475, 7475, -15670, 15670, -7480, 7480, 15675, 15680, -7490, 7490, 277830, 277825, -7495, 7495, -7499, -7500, 7499, 7500, 7501, -7505, 7505, 7510, -7520, 7520, 81250, -7525, 7525, -138600, 138600, 7530, -15725, 15725, 7535, 15730, 7550, -15745, 15745, -138625, 138625, 7555, 15750, 7560, 277900, 7562, 15755, -302475, 302475, 105875, 15775, 302500, -7590, 7590, -302500, -7600, 32175, 7600, 24000, -7620, 7620, -7625, 7625, -138700, 7630, 138700, -7631, 7631, -7650, 7650, -138725, 138725, -278000, 278000, -138745, 138745, 138750, -138750, -138755, 138755, 15875, -1678870, -310795, 1678870, 310795, 310805, -7700, -138775, 7700, 163350, 138775, -163350, -15900, 15900, 278050, 138800, -40500, 40500, 1678880, -138820, -7750, 7750, 138820, -138825, 138825, -171600, -15950, 15950, 171600, -7770, 7770, -138845, 7775, 138845, 138850, -138850, -138855, 138855, -138865, -7795, 138865, 7795, 138870, -138870, -7800, 7800, -138875, 138874, 138875, -138874, 7805, 138876, -147075, 147075, 138880, 138885, -138895, 138895, -32400, 32400, 138900, 138905, 138925, 138930, 40625, 3055250, -3055250, -343750, 343750, 15277625, -138975, 138975, -16095, 16095, 171750, -171750, 155375, -138995, 138995, -32500, 32500, -139000, 139000, -16125, 16125, 139005, -155395, 155395, 155400, -7950, 7950, 155405, 139025, -7970, 7970, -7975, 7975, -7980, 7980, 311080, 1679150, -8000, 8000, -16195, 16195, -16200, 171850, 16200, -171850, -16205, 16205, -16220, 171870, 16220, -171870, -16225, 16225, -24420, 24420, -16230, 16230, 171880, -16245, 16245, 139125, -16250, 16250, 171900, 16255, 3055530, 139150, 3055520, -163725, 163725, 90000, 16275, 335775, 761750, -761750, -8095, 8095, -8100, 8100, -376750, -8105, 8105, 376750, -3055520, -8120, 8120, -32700, -8125, 32700, 8125, 8130, -32725, 32725, 8150, 770000, -16350, 16350, 172000, -32745, 32745, 385000, -8175, 8175, -16375, 16375] \\\\\\\\\\\\\

 

 

 

두번째 코드 방식이다. 

동적 프로그래밍 방식으로 구현한 코드이다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    static int _N;
    static List<Integer>[] dp;//메모이제이션

    public static List<Integer> dp(int n){
        if(dp[n] != null) return dp[n];

        dp[n] = new ArrayList<>();
        dp[n].add(dp[n-1].get(0) * 10 + _N);

        for(int i = 1 ; i < n ; i++) {
            int j = n - i;
            List<Integer> dp1 = dp(i);
            List<Integer> dp2 = dp(j);

            for(int n1 : dp1) {
                for(int n2 : dp2) {
                    dp[n].add(n1 + n2);
                    dp[n].add(n1 - n2);
                    dp[n].add(n1 * n2);
                    if(n2 != 0) dp[n].add(n1 / n2);
                }
            }
        }
        return dp[n];
    }

    public int solution(int N, int number) {

        _N = N;
        int answer = -1;

        dp = new ArrayList[10];
        dp[0] = new ArrayList<>();
        dp[0].add(0);

        for(int n = 1 ; n <= 8 ; n++) {
            dp(n);
            if (dp[n].contains(number)) {
                answer = n;
                break;
            }
        }

        return answer;
    }
}

구현 방식은 비슷하다. 단지, 메모이제이션과 재귀방식을 사용했는가에 차이점이 있다.

실행속도 측면에서는 DP방식이 더 극단적으로 나왔다.