[LeetCode] #1011. Capacity To Ship Packages Within D Days

-

題目

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

直覺解

構想：

先設定 capacity = max(weights) ，計算需要幾天。天數超過的話 capacity += 1。直到天數在許可範圍內為止。

python 3 實作（失敗）：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

        capacity = max(weights) 

        needed_days = 1 

        package_wieghts = 0 

        while True: 

            for weight in weights: 

                if needed_days > days: 

                    break 

                 

                if package_wieghts + weight > capacity: 

                    package_wieghts = 0 

                    needed_days += 1 

                package_wieghts += weight 

             

            if needed_days <= days: 

                break 

            else: 

                capacity += 1 

                needed_days = 1 

                package_wieghts = 0 

        return capacity

Submission Detail

Time Limit Exceeded

Last executed input:
[399,447,465,213,487,97,94,419,469,76,433,316,490,434,493,289,395,157,109,341,449,122,173,489,129,373,387,368,325,348,462,112,118,476,30,464,460,155,2,244,373,460,408,376,190,149,69,76,280,452,443,365,128,176,213,307,236,129,142,357,324,471,50,425,373,19,355,497,46,67,86,395,262,203,240,258,367,3,73,234,282,494,268,444,492,131,77,87,27,366,10,176,35,491,178,464,453,116,205,461,151,342,498,200,459,120,448,98,424,19,381,246,344,263,450,369,404,452,341,242,406,310,498,170,162,463,162,429,261,363,287,467,134,55,110,108,392,475,64,156,57,433,418,336,146,125,412,468,468,24,454,327,173,468,82,357,145,172,363,464,453,285,165,459,216,446,175,438,85,348,248,109,110,386,179,61,224,146,130,437,33,490,378,470,420,229,194,51,284,276,208,290,246,393,48,193,358,395,40,262,371,243,56,352,164,17,71,492,155,197,105,488,157,247,320,363,164,43,195,403,492,5,25,410,91,71,58,110,205,462,61,293,248,213,409,317,37,450,121,377,350,282,340,422,206,481,413,263,144,108,343,226,424,150,426,68,336,247,165,125,36,148,323,81,362,229,106,449,144,449,70,200,385,218,31,226,271,234,122,405,196,223,168,206,296,480,88,372,429,270,84,330,371,20,276,28,181,107,163,3,6,387,80,189,276,12,74,33,197,341,84,421,488,497,138,177,493,117,466,363,359,167,24,298,159,146,66,454,335,176,77,23,29,166,330,281,428,156,5,409,338,62,398,15,125,144,155,470,497,208,448,364,124,354,483,207,215,210,156,401,374,74,94,69,111,40,72,19,88,206,345,440,152,426,65,244,482,294,249,86,266,309,318,439,346,368,27,47,211,357,415,459,497,167,324,133,35,189,235,67,252,215,105,309,442,404,351,298,315,490,367,211,460,348,149,184,365,411,295,261,87,146,165,199,101,387,382,176,442,47,65,426,12,209,394,92,249,372,134,284,261,25,422,107,341,146,412,448,499,301,496,98,136,185,152,161,268,416,317,209,485,416,288,451,61,147,134,14,36,282,21,123,134,481,104,261,451,322,151,110,310,313,240,345,316,119,316,301,336,452,456,228,409,363,452,182,210,98,263,226,90,271,436,388,88,340,35,398,113,44,2,30,425,280,257,154,49,283,191,100,348,470,55,146,421,380,399,283,279,451,136,444,298,202,144,72,139,361,454,128,383,360,422,41,472,237,98,89,123,296,103,5,280,206,38,366,262,56,203,83,280,71,461,296,229,99,456,38,81,133,314,373,450,311,382,433,268,311,144,114,8,33,443,188,129,1,93,476,358,213,131,144,422,249,235,39,169,390,160,371,272,2,233,352,224,48,462,256,51,325,66,126,186,347,11,374,482,201,125,468,119,101,439,136,384,194,232,432,13,48,12,189,327,394,313,218,283,119,438,49,243,96,439,332,168,52,243,125,195,392,277,42,164,368,320,455,254,328,190,127,285,180,141,286,70,396,437,41,18,192,143,277,484,430,14,448,282,131,472,411,160,118,341,451,78,188,112,479,12,249,353,156,81,26,177,353,337,273,109,495,122,236,44,358,132,130,356,70,81,188,489,264,258,161,250,402,131,379,189,194,187,280,27,292,206,422,386,335,85,455,486,311,10,338,25,386,429,356,319,463,400,447,230,482,415,463,34,143,245,396,83,327,154,345,334,89,195,129,132,306,9,104,355,338,306,394,294,420,90,444,98,134,39,209,75,35,114,455,363,75,43,411,56,246,217,233,461,193,100,237,5,112,465,315,324,482,66,248,256,105,203,223,49,151,378,309,5,346,60,337,125,229,258,225,486,364,128,439,16,116,157,256,439,344,430,252,245,25,402,113,146,460,233,204,456,415,470,127,151,215,482,2,242,345,340,89,324,64,52,243,252,12,411,82,153,286,58,108,83,27,19,412,232,292,14,291,124,128,1,88,305,251,153,472,8,491,11,243,286,214,452,293,292,11,249,9,3,163,491,282,317,346,220,489,466,472,292,8,164,268,289,338,52,272,12,469,50,235,310,291,373,274,104,185,60,128,363,67,50,410,436,86,447,232,429,432,377,249,467,216,108,335,454,319,326,248,312,308,484,154,253,329,71,345,168,188,300,427,229,275,93,159,122,176,293,459,279,458,464,101,77,138,372,11,70,399,185,390,67,118,258,499,237,410,338,93,133,77,444,225,256,138,500,394,336,17,336,150,488,30,499,127,196,10,149,486,399,304,124,327,111,274,77,442,341,53,234,300,90,145,133,393,179,38,111,384,142,236,258,182,162,248,10,375,383,45,226,315,468,452,380,146,131,116,36,264,217,402,493,106,479,318,310,79,338,185,111,336,144,161,398,9,377,248,278,205,182,49,495,186,465,406,300,99,31,24,339,100,253,174,209,333,408,286,452,83,478,262,195,138,282,336,37,97,7,219,450,266,386,340,4,427,99,446,120,334,172,122,495,54,354,356,85,51,354,440,93,462,177,25,435,346,145,78,412,153,206,424,250,489,165,389,426,411,193,464,288,27,89,15,38,386,95,328,353,483,196,428,279,287,409,299,463,157,260,466,480,78,277,227,222,294,141,397,448,217,411,257,128,431,18,318,94,380,204,386,254,269,286,79,337,26,321,211,363,166,227,340,136,210,456,20,335,97,98,126,38,225,417,460,485,245,435,263,475,377,437,323,358,286,64,32,75,211,202,469,408,181,38,108,17,35,396,156,292,347,102,158,204,347,156,157,414,121,417,167,471,420,119,421,251,17,47,299,358,251,294,425,169,114,434,75,245,280,383,274,361,11,15,125,307,348,338,417,447,144,375,17,12,433,41,62,181,42,154,240,20,48,167,500,51,218,398,48,6,18,103,50,378,137,344,9,278,91,265,122,196,64,437,413,361,53,315,54,182,49,233,128,391,48,341,381,420,36,246,63,479,239,116,357,496,93,405,404,17,500,9,438,202,311,315,195,398,423,257,219,100,262,497,213,179,135,182,360,14,276,223,436,277,25,316,5,434,256,11,481,436,188,140,13,4,225,498,11,123,3,36,71,70,258,360,429,234,135,320,209,500,366,343,316,74,495,137,116,436,157,221,208,28,137,76,241,214,76,480,14,481,329,279,133,348,332,272,380,350,494,422,409,118,119,432,138,24,278,402,49,458,200,167,57,444,205,356,120,329,42,175,291,347,1,462,89,174,81,300,260,38,111,68,258,129,37,182,166,186,464,255,1,69,14,469,65,56,116,272,413,459,30,399,78,457,420,121,420,441,99,401,323,466,350,146,63,400,379,19,480,320,331,276,270,296,325,99,291,493,460,353,288,322,40,266,160,304,225,337,332,312,136,453,444,119,252,469,97,491,378,453,405,267,150,42,450,383,483,286,35,57,19,302,465,489,300,274,443,54,248,305,447,39,95,206,151,156,120,192,105,458,255,155,92,486,282,328,492,70,315,97,249,410,488,151,457,133,323,50,1,225,14,173,361,343,160,399,345,233,186,307,96,362,403,189,217,269,189,274,481,270,206,392,202,471,415,480,59,208,100,179,394,77,470,105,464,459,328,209,117,310,330,110,105,261,25,319,360,248,125,49,355,414,314,8,337,489,100,82,383,408,75,467,108,188,300,202,18,171,449,134,363,439,41,114,65,109,310,194,58,80,189,200,16,462,317,100,398,118,204,315,482,241,169,72,137,16,420,331,258,127,349,440,423,77,302,474,446,50,8,317,346,48,326,443,375,390,38,68,222,184,166,445,74,441,124,193,312,452,346,356,464,275,140,450,422,59,473,402,474,230,1,60,464,324,378,230,345,371,62,28,303,158,462,204,137,122,14,142,485,296,227,245,401,16,116,297,74,394,130,106,296,107,204,400,288,40,123,453,448,404,175,268,171,65,240,242,431,183,219,500,213,268,482,347,176,13,83,163,109,496,42,119,52,272,46,83,123,297,264,229,42,453,487,53,105,271,205,257,106,416,457,122,206,141,367,424,69,394,496,22,463,395,295,116,183,306,433,291,400,138,198,9,242,314,221,234,318,462,80,404,20,61,34,456,394,326,287,23,324,64,403,105,394,426,227,229,388,279,287,491,499,275,131,497,249,16,34,187,444,25,193,39,448,71,73,382,441,499,257,457,337,426,265,281,340,61,486,79,163,241,211,116,256,60,141,286,209,214,313,73,193,93,169,119,294,181,322,33,117,449,301,243,69,324,233,460,236,453,202,248,176,235,50,265,228,462,391,274,484,364,133,443,369,445,134,59,150,111,178,216,284,122,315,322,303,362,15,304,242,116,129,226,440,213,162,82,73,375,146,91,449,258,357,273,170,304,182,131,281,9,383,99,61,136,203,257,171,176,131,188,43,28,358,292,330,88,225,167,286,202,8,293,433,461,106,327,458,185,61,427,230,472,319,98,496,123,274,17,426,255,218,401,282,65,373,91,170,191,82,380,64,216,123,166,175,76,322,325,224,277,141,400,245,335,105,322,197,473,423,384,95,134,290,149,407,337,367,137,120,494,185,450,321,90,122,124,362,27,164,164,100,6,468,432,131,314,262,317,189,308,222,296,366,157,369,306,418,490,415,88,353,9,91,420,55,337,386,286,409,110,44,495,258,359,261,81,258,490,493,213,347,447,12,56,367,269,331,307,492,79,221,448,128,473,447,198,341,80,285,124,85,498,198,246,207,340,360,15,88,453,326,50,127,250,124,469,370,57,26,261,199,28,421,411,413,392,465,424,52,76,133,294,472,430,419,78,398,313,361,188,412,245,425,70,74,373,198,13,332,217,272,466,410,438,288,431,108,440,117,119,478,51,385,409,360,106,298,118,399,79,385,338,351,377,330,103,435,69,286,50,376,217,384,472,426,16,225,131,113,97,100,482,309,415,302,352,324,482,395,234,470,41,75,168,384,322,114,420,186,353,492,295,87,301,170,298,244,34,132,463,405,289,345,297,435,391,218,487,357,231,90,430,124,3,123,474,375,71,120,118,475,97,85,33,495,46,87,489,53,172,345,487,351,290,340,49,312,196,167,315,9,124,256,251,112,353,229,261,200,436,24,459,54,430,300,38,426,383,282,455,336,206,113,28,348,359,125,392,158,340,408,439,331,489,116,315,302,428,462,40,427,233,359,21,244,367,337,276,219,100,491,498,106,205,130,449,346,220,337,480,99,149,50,175,179,70,358,148,51,155,457,323,333,402,71,447,376,171,389,442,218,234,282,289,477,112,270,174,311,118,327,481,226,194,279,155,333,224,386,474,393,390,342,106,377,196,146,81,202,145,259,273,496,4,419,249,351,20,217,243,446,20,399,325,248,287,129,11,374,10,77,359,50,57,178,122,399,130,400,152,199,426,15,263,403,490,231,180,115,455,405,129,284,210,469,162,55,457,215,308,445,108,250,237,29,473,459,353,364,168,355,447,134,144,353,10,197,372,393,380,497,235,468,399,15,120,126,135,273,475,182,361,58,298,269,111,139,441,295,161,174,230,373,246,295,330,389,457,94,474,330,56,430,179,29,329,293,267,188,488,393,317,124,74,197,109,243,337,258,489,318,134,159,125,93,1,442,476,204,344,96,461,492,449,109,47,324,455,145,361,474,325,16,195,151,260,47,415,370,208,64,241,34,342,370,40,15,465,375,358,313,376,353,24,45,217,62,56,210,26,263,41,105,371,244,106,410,17,267,395,156,394,400,94,33,71,204,463,71,192,399,233,124,92,188,31,372,22,405,392,46,189,216,264,375,9,451,117,174,375,281,274,320,461,247,71,154,128,336,395,354,97,77,76,446,308,225,271,469,351,86,417,96,424,139,103,154,343,108,16,209,262,149,38,355,361,96,312,5,397,418,178,487,41,65,59,482,64,381,334,69,233,230,439,184,440,368,483,8,102,84,83,65,244,168,333,127,236,206,285,146,411,350,50,470,497,472,447,208,485,423,418,154,62,28,348,291,91,259,379,117,32,133,407,417,287,97,142,34,296,348,403,406,61,424,250,264,246,152,91,372,82,499,475,487,196,153,130,468,11,105,488,43,323,445,271,118,342,312,14,83,112,355,237,144,419,341,407,140,167,451,299,78,39,485,323,81,387,435,188,283,483,13,300,488,98,483,227,374,349,181,187,371,188,453,487,424,465,312,499,301,461,393,191,419,212,53,100,281,209,8,174,440,116,143,45,379,78,184,155,171,153,289,275,148,189,481,458,287,220,141,88,382,410,216,451,90,454,332,461,84,312,283,137,304,72,135,254,137,390,246,68,256,488,11,245,164,249,403,168,19,278,461,450,284,324,218,40,179,48,481,226,281,74,228,12,305,389,426,483,484,202,67,112,350,60,239,50,179,250,343,355,58,269,254,235,297,198,98,461,43,474,236,464,8,226,396,391,269,266,414,489,430,202,202,133,387,100,205,148,271,248,250,194,483,433,430,241,220,92,484,298,153,116,294,481,362,69,118,194,64,412,185,255,282,170,68,147,233,389,306,337,378,493,499,110,35,436,152,47,145,147,337,116,385,275,94,451,174,293,14,281,416,118,195,353,357,67,491,20,115,10,21,128,402,47,10,117,84,324,25,49,161,378,279,205,227,198,424,314,172,204,344,353,107,431,26,15,33,316,89,6,282,223,282,82,422,49,163,157,36,92,260,291,462,301,280,191,191,373,176,464,64,409,385,449,376,74,60,410,36,317,9,276,56,304,325,493,387,7,203,153,383,420,440,94,186,104,368,277,266,216,386,499,391,493,55,354,360,280,180,100,433,266,424,111,479,121,427,147,155,138,17,50,71,57,120,33,200,204,93,32,391,384,467,150,355,30,196,106,397,263,331,67,324,140,404,285,18,367,11,158,213,113,5,310,6,386,241,496,413,20,145,203,378,228,378,297,174,138,76,203,185,94,443,395,258,154,79,484,202,145,189,258,273,452,128,123,403,115,85,339,128,40,439,94,292,336,415,325,296,252,453,456,387,337,270,470,350,304,288,47,253,95,469,229,383,499,444,376,418,448,143,455,273,144,299,453,60,480,307,320,379,89,261,85,451,360,215,194,84,455,71,54,445,486,52,1,148,78,207,478,35,250,407,131,400,57,377,80,70,177,281,452,93,75,163,299,102,8,270,258,192,149,125,14,237,212,221,321,443,254,236,171,99,35,317,227,437,313,410,140,458,469,237,125,153,21,399,52,351,500,80,98,347,60,1,78,74,355,52,294,76,66,56,241,37,233,162,68,469,482,277,36,196,495,79,117,331,315,338,354,138,232,68,479,328,436,119,494,382,207,162,290,375,382,338,60,149,188,97,260,87,24,74,204,489,256,324,78,252,289,435,101,383,416,178,348,395,283,467,190,379,254,209,243,329,291,285,446,32,382,14,129,83,149,298,289,232,461,142,399,431,296,430,11,11,357,330,93,432,75,406,335,92,322,227,444,457,76,156,365,140,409,474,431,322,331,172,133,105,167,107,300,492,451,279,326,476,126,153,250,140,103,487,488,118,366,479,226,23,405,220,19,75,472,151,152,478,125,76,454,209,445,231,426,219,118,251,293,396,251,326,196,394,411,398,241,207,226,234,159,211,490,271,411,488,27,291,250,473,288,170,327,327,160,208,167,488,173,392,404,351,337,405,398,470,111,415,186,257,479,274,169,214,55,392,114,296,147,238,124,311,10,162,393,235,414,320,165,36,49,448,452,387,202,470,92,500,472,311,300,359,407,101,51,479,1,207,18,401,199,426,490,154,445,33,363,121,393,182,396,22,57,75,76,126,208,426,462,245,261,449,202,330,104,30,194,490,231,292,10,41,35,149,280,164,284,390,469,193,300,334,90,199,457,43,428,315,154,287,116,332,298,229,340,420,473,430,16,100,197,232,250,152,371,410,499,412,175,193,291,192,76,413,473,473,361,402,304,47,89,272,59,221,456,439,318,371,127,51,27,407,412,470,282,96,104,133,410,266,411,447,237,441,451,465,168,54,234,275,200,116,423,122,374,56,445,12,69,126,305,131,426,41,435,362,399,351,408,210,441,494,415,71,248,296,15,276,347,77,239,342,421,436,170,230,362,470,283,223,383,382,99,377,338,225,390,412,68,292,353,266,292,465,387,433,335,378,439,470,279,30,204,60,210,170,13,329,169,441,409,432,11,469,285,298,9,380,225,245,365,415,47,432,208,230,491,81,90,218,464,281,114,442,321,268,56,122,181,394,393,283,28,7,14,357,355,364,321,56,308,236,250,300,432,364,48,241,316,115,6,296,16,491,54,72,355,198,89,61,61,478,365,252,63,393,209,389,486,197,269,475,400,465,20,360,382,319,308,371,293,84,445,200,129,459,467,348,93,422,283,414,260,191,373,70,222,285,269,222,77,28,482,28,20,97,298,82,108,351,493,87,182,19,105,326,354,269,123,274,371,193,241,213,37,347,10,107,249,7,37,150,320,486,146,136,64,66,180,202,210,38,173,465,267,240,478,99,24,394,192,350,349,145,151,26,213,309,247,34,320,411,30,139,468,197,403,205,209,306,370,273,1,432,130,125,445,164,374,286,293,261,45,61,232,109,14,318,66,306,48,348,436,142,166,100,44,303,408,201,10,492,357,265,348,295,367,355,54,157,63,211,151,130,302,30,83,346,136,243,11,296,365,387,176,215,207,362,195,35,486,176,415,161,300,408,219,373,117,288,456,405,484,99,329,437,351,301,146,109,295,315,476,37,435,441,20,234,144,495,200,466,451,288,336,431,391,157,446,217,427,339,407,20,45,441,455,162,361,279,373,419,443,454,201,28,84,353,112,183,30,269,112,227,277,339,233,420,6,441,385,31,428,428,105,308,458,485,26,446,475,187,285,415,350,438,279,425,186,488,357,63,27,55,313,237,187,336,483,104,230,102,413,47,91,244,16,71,352,447,109,40,109,493,93,134,202,197,393,157,481,348,174,373,193,374,482,175,394,115,357,169,330,238,389,18,45,209,303,248,274,480,12,440,296,261,177,334,202,138,123,119,371,207,463,409,123,500,339,398,4,216,328,437,298,81,42,51,452,157,123,411,416,90,395,47,359,52,465,325,62,118,85,355,374,264,445,295,233,355,301,204,323,440,498,179,359,197,238,30,215,376,146,293,99,87,195,260,398,252,62,242,107,131,300,5,449,243,258,472,480,414,146,243,10,162,341,379,499,4,51,116,102,356,54,300,489,251,351,295,265,75,271,209,220,111,267,454,389,21,476,19,219,322,300,354,362,254,296,473,144,5,128,211,321,431,326,50,408,424,179,128,464,445,184,279,257,481,382,113,288,433,387,428,326,393,199,58,361,128,275,410,21,208,141,333,217,84,122,363,180,24,267,360,488,424,45,351,46,365,198,190,100,391,177,367,193,69,185,65,333,317,459,481,23,373,327,378,161,411,23,285,423,278,320,85,268,134,223,37,383,184,233,301,376,451,328,289,401,353,320,186,277,96,306,394,192,473,309,404,1,188,380,450,235,326,441,37,456,306,65,273,285,109,441,59,140,70,475,392,157,322,91,309,26,477,78,129,30,303,27,97,413,208,273,401,307,149,78,104,53,32,131,191,395,476,329,70,69,171,334,327,445,342,262,130,362,76,355,327,460,111,85,128,118,138,194,162,135,457,459,448,86,465,477,492,405,377,390,96,350,102,417,115,173,155,201,30,87,394,411,259,159,218,19,189,127,66,340,65,407,80,353,87,123,148,244,455,320,61,374,121,499,275,433,342,74,128,173,232,228,14,108,417,373,230,114,240,368,217,249,371,144,54,159,444,300,85,311,429,419,198,171,127,148,43,201,90,375,74,109,308,162,324,489,334,212,301,197,42,362,353,284,167,357,429,265,75,273,420,386,316,370,342,144,240,366,241,153,297,444,283,361,310,319,164,122,456,19,94,137,42,71,240,250,149,462,35,331,209,207,490,37,306,157,433,106,39,227,297,286,223,381,57,414,403,401,19,352,397,407,386,176,164,485,302,464,346,332,399,106,396,173,473,113,86,233,273,295,353,117,455,370,74,207,495,423,86,35,500,57,344,58,155,352,449,344,313,67,41,157,237,209,146,403,411,333,60,376,440,305,324,280,48,311,236,480,158,424,467,318,19,31,194,326,31,112,147,330,251,50,70,223,482,152,51,282,68,129,137,332,117,464,386,426,7,292,108,130,468,125,178,128,29,142,377,115,318,296,456,33,375,62,209,70,344,383,273,313,34,261,496,293,69,50,182,33,260,50,99,253,219,342,456,251,148,28,271,191,246,253,479,176,289,253,458,492,449,15,106,164,27,10,101,397,294,341,408,440,459,208,251,307,214,156,312,490,346,91,156,20,149,298,169,47,345,293,246,123,105,6,325,7,238,51,352,70,82,212,257,463,369,98,310,102,190,406,114,258,130,54,474,36,74,307,133,230,328,357,228,314,118,99,190,178,107,236,30,151,220,343,488,359,384,412,475,177,133,352,158,77,457,457,59,238,177,484,359,174,61,129,72,405,294,407,350,82,171,229,309,288,236,82,81,95,451,2,399,361,241,79,169,161,465,181,418,91,378,313,471,82,308,22,459,228,480,79,84,62,217,275,323,442,235,470,112,39,327,189,112,476,137,385,318,317,204,240,151,477,386,395,93,370,242,407,135,180,316,72,400,458,33,353,76,224,176,450,490,383,161,284,500,132,386,324,21,45,25,408,330,131,284,241,442,258,482,112,418,240,375,397,250,411,11,443,118,490,299,194,450,404,426,475,190,116,22,432,138,90,85,173,292,409,196,332,237,467,236,317,116,248,227,271,38,36,191,433,7,104,20,402,444,344,117,478,187,308,135,159,366,211,467,225,488,379,303,10,270,436,252,151,223,65,114,412,373,213,70,120,182,74,88,303,108,282,395,482,149,41,300,343,88,276,330,430,18,294,15,461,294,473,434,457,97,345,496,66,322,326,307,435,187,309,209,236,491,279,458,142,42,254,326,43,280,461,213,99,386,337,294,336,455,303,283,271,485,50,267,84,317,143,411,354,95,160,66,337,367,120,452,470,277,419,443,19,154,19,65,128,237,416,63,227,75,324,278,221,75,56,29,275,231,441,240,437,429,207,420,410,403,2,128,135,283,108,322,163,99,45,368,46,270,491,231,303,373,198,311,404,352,173,113,409,383,267,96,293,393,251,448,64,132,208,131,27,38,210,455,288,158,131,201,80,153,87,9,479,250,400,347,134,270,51,147,52,121,105,378,485,51,351,463,142,103,159,75,132,200,224,166,57,135,161,384,314,163,383,192,451,265,227,48,77,351,81,240,451,305,328,298,225,428,59,96,356,69,321,314,262,336,234,460,446,322,460,321,404,14,483,167,127,470,394,324,385,323,307,114,427,28,170,181,22,222,427,180,331,253,132,407,271,431,48,452,248,164,231,193,314,160,151,279,443,153,408,119,116,60,113,35,166,268,121,37,358,151,96,417,365,368,371,82,33,67,227,30,10,408,206,243,433,364,336,2,416,130,40,275,156,252,420,75,214,23,377,20,375,111,480,213,196,184,182,488,199,94,282,122,352,334,29,87,132,239,341,423,117,2,443,354,308,418,227,436,106,117,88,122,272,236,305,383,463,179,226,224,253,43,345,69,258,371,89,313,59,395,402,378,63,108,115,427,97,278,218,228,63,224,436,285,206,104,211,259,183,16,178,386,307,131,300,182,112,153,313,110,379,106,39,15,280,264,311,290,489,197,94,434,343,298,432,15,163,190,392,294,270,372,162,378,150,256,212,77,139,394,333,101,323,255,45,123,298,131,271,103,498,265,42,358,356,442,272,419,45,106,2,391,90,41,374,45,97,52,147,394,210,281,337,250,79,175,195,497,480,419,311,51,471,460,257,133,425,12,65,373,103,29,328,10,183,361,127,54,44,306,100,110,29,39,90,329,383,485,89,173,266,90,72,285,408,229,174,361,18,389,225,390,370,118,162,435,299,451,107,217,204,482,488,428,197,342,479,171,235,385,420,84,369,127,453,177,474,137,222,188,340,171,282,77,216,337,185,95,272,367,304,278,399,189,412,12,20,8,376,15,84,335,386,204,52,207,250,412,304,391,139,338,390,20,304,322,55,154,232,112,489,106,322,90,11,450,25,238,28,108,269,465,197,135,357,103,263,377,27,356,62,399,308,73,104,40,465,409,162,454,275,285,118,455,15,384,131,5,26,375,157,79,183,218,330,62,232,92,398,88,241,219,172,169,373,215,486,101,179,147,402,139,394,343,335,346,485,72,140,258,184,490,229,491,181,76,204,379,240,160,353,147,371,13,127,361,242,375,201,277,397,262,101,480,197,115,425,15,479,214,337,422,185,167,238,422,427,301,154,430,183,270,45,63,393,264,14,72,296,477,452,243,431,460,237,390,317,266,295,471,453,207,162,488,191,490,95,463,113,84,256,431,371,373,17,390,336,422,421,157,390,342,107,83,494,25,473,334,393,387,69,345,152,294,431,88,169,496,396,331,208,154,398,471,455,12,326,415,166,406,248,80,380,132,402,130,432,439,354,113,193,215,447,449,119,259,180,234,56,292,166,132,123,21,244,25,112,40,178,98,181,468,39,78,95,1,410,279,39,16,334,438,402,280,74,271,146,246,114,359,462,166,315,152,302,379,267,137,200,195,431,59,201,417,347,166,18,89,102,434,215,327,119,113,475,224,193,236,389,296,300,346,421,258,37,242,53,331,454,367,497,240,264,387,328,191,331,120,469,14,398,63,362,212,104,83,340,330,288,14,281,179,262,255,448,165,175,459,141,478,429,68,254,39,177,349,80,252,176,76,392,14,6,350,446,72,6,403,233,118,7,219,373,498,332,350,35,98,122,493,441,130,413,75,24,132,87,229,228,19,112,130,251,52,267,380,214,402,343,61,23,481,347,131,261,106,303,264,227,13,381,174,257,261,65,192,453,96,457,484,320,89,173,327,475,188,500,364,214,442,313,41,232,430,423,172,61,192,410,356,43,226,44,385,469,114,217,428,343,462,147,420,452,49,238,154,91,403,341,470,451,176,411,236,426,405,363,464,433,397,57,258,343,414,135,131,70,58,137,409,241,410,357,99,37,387,95,111,455,367,486,111,467,196,178,9,385,270,392,390,70,52,25,150,55,276,174,67,47,144,130,413,332,445,35,473,146,443,473,279,8,442,72,194,80,87,472,392,63,254,272,371,171,338,356,281,228,440,310,120,360,259,490,223,3,245,106,424,303,117,267,392,144,380,34,363,126,152,123,449,162,315,369,61,313,125,220,374,401,230,338,317,165,378,191,464,93,184,81,258,400,438,361,380,169,275,184,270,447,88,106,348,105,332,218,10,154,259,53,221,190,303,54,111,243,294,177,383,413,133,129,42,322,101,151,395,354,41,94,167,221,85,38,194,312,474,392,385,8,107,153,138,115,234,251,236,297,421,2,451,280,321,152,340,344,238,366,95,64,81,209,59,211,417,361,114,288,406,241,422,98,282,378,70,249,455,307,66,123,54,380,43,84,19,160,456,346,2,201,10,410,127,411,193,273,415,437,429,180,181,11,242,312,306,183,220,391,86,432,240,329,161,458,228,320,306,108,23,201,295,204,211,172,264,275,202,108,479,157,177,412,182,205,64,99,93,300,436,269,368,322,195,288,350,144,20,176,421,172,492,155,111,375,190,10,210,154,64,474,338,70,448,140,98,120,424,322,438,305,50,7,176,323,373,103,434,83,122,96,113,485,299,254,414,163,88,252,99,42,325,37,482,490,109,8,347,47,78,445,374,119,215,254,462,289,169,270,252,381,402,345,176,69,61,25,142,358,431,327,7,45,60,360,370,235,168,329,107,353,379,500,191,477,110,308,490,243,179,269,260,16,144,358,101,439,224,325,373,11,313,366,468,137,349,204,147,196,114,238,405,229,382,200,35,235,127,19,457,281,451,21,230,8,25,335,164,176,130,153,354,387,98,17,4,170,161,372,494,322,206,15,5,168,99,415,69,434,338,379,238,248,126,17,187,171,116,156,377,365,115,476,97,335,464,413,430,258,86,340,444,339,188,21,120,468,490,500,265,404,488,250,257,338,231,369,130,243,29,218,277,359,141,217,14,468,85,172,46,191,10,32,416,297,20,291,337,280,492,268,48,319,28,30,418,401,274,481,435,19,88,208,103,421,234,425,234,337,244,52,237,208,325,196,134,31,275,29,376,120,3,296,213,334,406,446,302,285,175,122,374,171,62,198,155,155,257,266,428,11,457,388,453,286,173,229,315,262,239,439,21,68,6,161,164,386,110,11,192,500,11,263,284,248,310,20,390,238,414,247,208,100,97,117,112,295,112,110,94,297,466,270,25,49,486,342,285,314,485,403,340,412,405,12,260,204,164,463,250,13,249,112,95,130,414,474,386,181,349,447,267,175,48,188,422,438,412,484,481,254,61,188,474,352,417,173,34,277,49,190,313,60,427,461,260,464,418,431,373,291,16,313,222,135,431,27,239,343,301,73,31,154,25,313,63,144,379,63,59,283,415,261,150,271,375,59,358,170,380,280,263,142,46,7,96,418,281,119,273,464,220,379,191,2,394,403,10,132,160,9,441,468,456,436,154,131,197,165,492,377,45,433,195,224,50,413,11,82,377,458,309,154,54,33,469,83,210,416,215,57,407,303,410,118,351,196,336,418,402,327,131,56,48,287,241,395,316,179,169,209,307,198,360,224,137,339,202,176,375,434,174,410,312,153,441,24,85,332,191,79,108,253,117,391,41,337,250,214,488,485,374,426,56,70,265,94,443,130,441,73,15,320,428,151,63,488,419,70,153,344,430,487,77,44,301,270,112,291,232,110,202,156,272,46,171,150,29,193,7,345,346,178,78,186,496,241,341,183,134,73,286,312,170,279,461,443,211,22,97,178,345,77,199,127,297,11,484,267,178,419,229,120,465,196,178,93,362,219,229,294,348,443,55,485,53,100,258,118,380,130,221,264,89,33,190,490,192,447,239,492,142,302,78,439,167,406,221,272,406,321,219,117,428,135,117,6,54,301,18,274,430,438,459,407,386,61,387,142,393,297,181,445,316,305,433,131,442,280,450,439,357,91,343,205,323,398,90,331,237,386,364,17,251,138,351,295,210,173,167,82,485,214,16,210,260,21,22,214,41,219,346,234,66,285,262,345,211,53,409,437,274,20,60,281,318,183,382,462,120,194,137,494,451,324,442,431,79,256,141,26,89,101,215,54,73,360,75,357,318,213,498,150,106,386,122,26,152,263,371,322,24,191,109,194,75,414,263,417,136,100,203,187,428,372,327,90,82,39,6,5,36,61,373,496,216,256,199,442,292,128,126,38,271,452,183,94,253,404,385,111,179,460,79,451,88,60,477,2,146,402,431,426,79,369,387,450,224,90,138,427,354,50,423,462,295,341,343,247,229,90,158,69,500,393,5,68,27,99,46,338,372,470,355,143,165,34,319,485,379,473,419,480,206,367,414,230,302,399,418,172,464,181,457,40,44,54,137,357,393,15,352,495,436,97,245,92,80,287,153,147,311,463,371,253,272,325,420,195,204,489,147,313,13,216,318,143,482,394,412,498,112,463,421,75,246,301,485,13,375,452,125,214,418,230,360,22,29,343,456,372,447,43,482,243,61,379,126,162,494,176,273,16,470,307,488,373,39,438,171,23,351,249,468,89,11,242,88,412,260,218,30,37,389,17,452,489,322,418,80,269,188,5,496,490,278,475,54,130,270,466,356,137,374,330,265,285,159,177,250,250,349,68,175,235,281,28,156,487,258,138,316,65,392,431,381,224,413,288,233,343,107,471,283,35,459,428,184,12,453,185,403,92,37,115,401,108,375,467,226,377,120,466,22,392,207,37,333,118,397,197,307,481,274,272,200,73,206,218,162,8,189,381,2,410,454,350,422,50,120,42,482,99,96,398,231,20,172,483,78,273,124,30,451,103,328,101,380,352,235,64,409,452,355,489,231,485,6,245,106,305,142,257,81,210,15,222,113,53,288,345,6,372,77,392,90,378,344,286,305,374,487,119,223,41,267,54,150,368,169,421,335,55,235,273,341,81,440,271,434,317,481,436,453,299,165,461,14,44,486,140,89,226,101,178,143,486,2,395,499,195,245,305,323,474,167,397,300,20,59,152,266,494,389,31,453,262,58,419,469,343,426,202,35,101,373,345,226,230,111,380,343,167,356,53,485,369,332,101,230,124,80,317,283,175,351,274,220,201,162,449,90,482,145,296,216,341,167,284,330,244,210,233,145,218,417,297,429,480,352,193,249,80,263,446,407,52,7,105,141,225,440,280,90,158,198,207,102,344,220,395,193,65,407,331,465,30,256,262,216,175,170,158,415,351,233,488,61,382,230,45,33,453,96,495,147,5,29,110,219,461,131,303,307,115,231,8,364,294,53,167,412,395,494,431,487,12,93,250,257,440,419,349,478,294,443,310,195,289,222,353,178,221,388,3,38,73,253,74,168,207,249,64,175,91,325,388,485,208,311,144,348,378,142,457,166,330,420,385,77,249,158,484,428,114,143,119,328,375,233,273,263,256,375,77,345,343,25,225,38,333,208,186,377,188,163,406,92,359,19,432,330,497,468,155,215,274,237,468,308,297,444,427,32,140,247,378,228,16,400,147,424,130,459,289,332,306,299,2,432,432,228,436,328,378,308,3,381,252,353,357,242,336,12,394,348,462,42,64,490,476,342,272,321,443,448,344,97,153,445,119,167,141,156,380,433,207,270,307,381,469,327,38,414,247,307,345,54,171,223,234,202,49,61,459,397,117,419,359,37,52,189,380,280,7,94,256,356,220,419,431,448,347,376,143,229,438,380,128,262,333,406,165,224,291,407,405,430,462,61,58,367,255,419,254,363,293,270,52,37,257,294,116,228,360,2,384,418,189,412,164,180,367,379,223,428,212,47,472,462,388,248,486,231,207,11,339,448,75,200,193,21,203,387,468,163,339,395,402,225,185,286,316,392,93,446,290,167,218,9,442,424,183,142,282,149,491,98,125,8,405,489,458,443,289,46,329,212,381,126,68,34,393,266,24,111,347,444,313,124,160,374,57,288,201,499,194,133,159,11,251,338,328,116,411,35,163,276,459,60,24,448,91,210,345,464,276,456,106,152,216,283,482,388,165,215,36,1,438,176,447,243,394,6,454,277,221,53,109,48,428,81,254,223,313,420,449,228,265,483,101,94,348,489,312,29,68,280,451,334,327,333,52,128,80,136,89,36,294,22,240,114,302,81,286,153,100,424,18,387,293,449,412,115,364,73,307,145,244,311,254,77,12,489,40,372,15,417,429,410,48,341,291,382,484,271,85,317,95,363,279,280,194,372,88,25,192,199,278,58,236,44,410,6,173,214,357,66,183,255,108,294,83,374,374,69,286,36,68,464,322,339,404,19,388,462,387,114,120,15,221,198,209,75,285,30,118,218,247,138,258,181,496,168,377,65,481,126,69,3,64,184,162,410,161,432,153,110,115,141,49,9,77,284,361,213,273,368,160,136,464,197,122,408,388,460,272,451,441,157,411,327,100,427,217,147,259,156,143,437,343,259,282,94,424,100,234,297,482,36,286,384,354,58,314,173,420,155,47,155,252,94,74,391,313,353,177,51,81,450,385,22,180,331,463,249,456,71,403,111,90,46,244,79,136,165,234,29,309,359,342,85,240,446,301,340,109,192,278,92,3,346,251,157,176,409,344,34,449,63,197,164,95,170,170,476,202,158,10,335,70,366,157,105,117,320,405,208,422,138,138,160,301,493,338,94,181,221,290,310,205,266,154,175,424,177,445,63,57,66,363,144,159,208,385,104,377,256,449,141,495,2,107,355,368,97,29,317,355,279,263,48,242,8,160,492,1,58,12,184,92,424,180,378,344,131,193,373,214,374,65,438,117,292,72,203,323,252,280,431,364,316,350,356,499,27,298,231,359,482,247,115,167,172,101,191,122,201,233,264,99,227,177,356,362,120,421,434,158,265,11,163,402,11,332,406,248,285,61,449,128,291,446,361,186,150,10,426,424,241,302,413,497,186,325,397,244,103,103,431,494,169,435,365,392,92,222,114,197,5,263,428,270,135,270,41,181,390,476,487,266,8,58,405,110,163,370,112,234,472,52,250,461,27,106,29,122,192,461,249,39,79,410,270,81,389,14,244,365,297,342,467,428,328,463,303,172,58,263,13,437,359,210,231,137,143,98,24,16,373,392,386,481,180,133,179,235,121,86,292,265,290,108,61,78,359,128,439,318,272,480,188,91,292,389,259,473,133,107,81,319,421,48,457,351,270,484,405,418,376,82,427,125,202,430,149,433,488,398,393,421,56,190,146,190,64,123,417,254,445,155,196,390,256,155,107,278,183,296,218,73,385,399,20,458,311,329,239,468,480,388,10,215,222,99,118,185,398,306,325,306,348,4,222,61,452,311,186,77,111,176,257,468,256,192,95,123,187,108,140,64,417,374,485,218,282,457,352,225,426,481,315,387,409,413,333,372,471,155,80,255,372,120,150,240,149,417,217,56,213,43,15,427,225,12,218,341,469,416,116,256,392,260,232,44,472,302,31,20,272,251,141,327,88,60,266,255,136,138,473,453,241,175,36,263,395,242,257,232,222,6,99,64,277,112,63,270,417,320,360,256,315,380,463,290,162,121,63,55,398,464,263,63,404,166,483,303,251,97,139,280,257,157,52,464,456,139,76,223,237,498,214,476,448,381,372,114,274,470,111,172,346,46,163,332,5,222,297,291,110,160,303,8,150,252,95,321,441,279,212,349,127,364,139,13,24,422,351,38,85,251,142,456,184,60,182,42,36,98,105,372,331,351,465,280,182,299,164,109,260,364,361,475,411,406,198,81,230,463,380,494,309,188,394,89,141,322,26,281,201,203,283,229,306,198,77,412,256,227,420,42,266,484,25,314,210,129,3,54,486,141,196,6,20,46,133,174,432,185,53,163,21,119,431,98,143,402,356,397,116,22,306,15,310,229,199,268,178,375,390,323,133,355,497,95,262,316,246,87,133,256,83,342,395,104,101,419,431,190,285,306,218,338,358,485,148,442,260,363,429,110,424,253,326,489,177,404,61,118,277,384,320,411,334,77,347,18,494,333,373,338,300,391,407,242,316,38,445,191,218,375,154,234,412,327,321,347,124,21,463,200,27,346,166,462,276,308,249,363,169,102,181,323,357,248,390,295,9,224,227,13,179,410,458,197,334,348,6,378,332,487,131,23,487,424,365,270,96,240,413,205,387,165,291,455,225,354,331,360,284,98,308,235,118,454,336,69,363,275,141,196,167,481,489,158,17,322,83,186,142,488,432,27,250,7,164,180,454,139,430,233,265,277,203,417,368,333,216,65,5,365,419,175,116,19,394,209,221,209,76,122,191,424,477,73,284,481,183,190,7,166,372,390,312,155,469,371,320,42,2,313,470,100,75,139,391,305,480,32,3,216,314,43,138,240,93,155,288,296,204,47,401,492,260,475,386,490,100,77,61,470,178,338,354,79,409,474,428,451,213,244,340,51,387,187,295,92,362,342,215,183,199,69,122,155,426,13,478,197,310,448,118,459,273,395,111,118,402,402,472,286,301,272,7,426,46,304,466,281,422,21,471,279,149,167,336,113,98,63,356,349,178,107,232,152,250,312,235,261,224,30,294,497,66,204,232,285,267,401,440,122,384,172,278,114,429,297,118,476,273,293,68,416,101,290,233,377,133,225,481,477,493,259,426,84,274,140,348,445,435,179,171,335,52,299,87,230,471,99,9,88,122,296,423,472,430,466,416,494,362,235,337,409,49,91,161,404,60,145,382,221,361,396,389,233,323,7,334,446,399,218,30,307,117,339,32,448,140,222,29,288,234,152,151,53,430,312,198,163,20,113,362,433,29,62,434,139,168,199,448,414,238,13,306,231,98,133,135,465,386,490,332,82,468,362,380,22,298,309,5,23,83,471,108,394,27,148,236,265,115,271,492,255,162,480,340,459,34,301,424,369,125,490,394,388,256,53,463,34,488,134,438,471,335,316,397,359,104,327,81,167,176,451,338,320,326,264,57,152,244,32,304,130,299,42,6,230,363,211,412,379,484,172,425,280,174,194,475,168,386,465,316,358,468,392,26,497,319,27,339,324,124,288,450,479,139,147,168,109,51,390,448,32,222,306,131,25,132,199,76,313,31,80,237,440,342,405,373,258,214,235,268,257,478,64,26,393,129,132,424,352,62,481,125,242,267,304,135,70,131,253,228,286,79,279,97,335,42,438,450,476,164,459,139,378,239,108,221,254,185,449,187,363,108,300,21,67,306,298,473,487,345,220,261,248,216,379,495,487,356,364,69,401,112,40,489,207,50,25,465,108,76,151,444,330,471,168,16,153,3,17,146,248,385,418,45,346,64,190,355,138,365,453,30,195,63,93,160,317,167,401,476,194,337,101,443,438,265,52,240,396,179,436,173,402,227,429,271,148,30,106,53,98,215,375,418,214,283,458,470,59,374,82,365,493,456,363,321,390,269,284,207,486,444,111,105,48,136,220,339,391,258,430,90,238,208,213,87,176,466,263,234,177,216,200,89,151,69,121,432,422,475,124,364,317,360,266,37,114,474,304,54,346,309,67,25,426,380,188,15,435,315,372,77,199,36,373,446,178,389,183,362,390,99,393,331,156,183,401,466,485,115,279,390,153,386,371,266,83,193,226,278,466,455,262,213,326,242,207,22,277,143,458,294,47,174,53,296,439,359,249,198,399,163,443,129,32,397,348,349,443,213,265,146,337,172,60,380,157,70,133,160,149,303,17,245,260,339,122,456,154,174,353,460,366,104,11,287,351,390,253,294,389,87,28,381,89,444,230,117,48,41,43,85,68,1,100,34,469,478,260,10,126,75,338,68,469,236,60,302,79,237,75,278,322,95,500,486,441,230,228,433,127,54,21,359,180,146,60,320,203,59,385,446,38,118,174,255,169,14,468,368,335,455,120,152,487,414,272,230,329,126,123,10,279,177,172,60,72,373,100,34,336,487,159,441,30,232,195,179,21,194,293,60,183,371,410,277,77,143,331,299,153,321,246,14,183,234,47,223,133,350,56,493,146,345,217,361,2,371,80,378,485,485,266,122,288,354,304,399,7,230,292,179,82,422,205,212,31,318,402,273,49,361,316,431,192,281,291,176,479,97,233,452,329,93,52,83,333,6,103,24,81,467,384,409,15,489,337,197,411,268,178,396,194,287,113,211,431,176,62,490,336,229,455,291,309,312,353,138,474,389,73,327,176,319,93,321,172,178,360,191,204,460,306,322,235,235,209,305,285,4,341,153,117,452,33,109,286,254,27,427,115,374,480,392,211,385,378,28,133,30,340,20,428,490,58,290,112,177,70,109,64,239,20,311,227,229,51,17,127,93,301,242,416,461,63,400,142,421,119,469,454,100,41,139,26,307,86,221,426,354,276,416,199,85,335,71,156,364,445,439,92,35,215,415,42,135,307,374,405,71,48,148,296,244,105,329,199,62,174,337,484,468,5,53,7,412,91,193,290,37,324,396,454,67,494,87,380,2,274,322,181,284,106,257,482,430,274,192,160,399,127,280,450,421,167,340,90,410,114,353,128,236,71,362,163,57,141,245,466,300,362,148,92,226,256,433,409,283,23,82,274,366,320,349,80,300,497,253,350,450,250,124,263,470,146,327,213,402,252,241,145,409,314,148,36,299,374,459,351,386,88,450,408,128,93,197,39,130,319,233,294,140,319,301,78,482,289,226,427,276,63,188,123,179,175,379,493,427,72,211,194,271,333,172,183,236,439,447,214,81,146,391,351,316,287,464,208,156,141,404,30,353,39,89,38,216,87,372,449,188,499,113,221,2,347,485,285,474,300,82,53,127,56,483,435,479,400,122,40,117,172,200,53,293,231,360,14,435,304,156,430,496,210,66,496,312,277,396,388,326,374,21,120,419,251,262,160,352,45,465,123,299,469,194,404,30,123,241,161,224,69,353,155,378,253,424,448,272,435,365,83,137,437,189,148,102,343,202,74,419,82,491,187,352,41,330,15,62,463,476,461,424,151,333,308,478,389,162,176,62,202,444,271,114,47,64,56,3,50,9,347,172,328,159,343,360,421,68,430,332,56,206,437,462,476,143,22,417,348,401,456,298,124,426,438,189,18,316,372,25,478,462,121,284,450,398,23,109,334,305,242,160,317,378,213,350,274,459,51,106,396,194,340,249,455,350,498,418,189,432,108,107,26,318,286,86,224,391,127,493,143,420,138,479,422,197,370,104,428,394,182,381,500,122,37,373,450,180,318,126,468,385,249,310,210,171,445,458,102,158,440,375,197,133,6,299,447,365,490,485,375,459,20,2,325,448,449,249,270,40,302,448,203,9,498,256,63,307,451,365,313,51,405,495,74,257,415,86,49,336,223,259,233,230,106,154,221,9,306,454,178,491,383,120,383,131,387,8,195,350,318,65,139,434,498,481,212,251,191,16,119,125,361,176,320,159,33,56,270,335,464,289,18,296,444,366,115,83,336,282,496,214,241,372,126,420,60,358,334,443,420,183,237,452,122,184,448,131,296,32,475,468,261,267,498,219,157,251,23,169,190,222,206,445,108,106,190,212,105,209,244,181,82,489,227,50,220,413,275,244,379,178,13,127,219,71,86,276,366,106,476,486,204,465,147,118,91,217,21,246,215,426,63,493,307,393,482,365,86,253,459,300,343,391,367,105,193,62,475,164,396,355,449,465,194,326,121,177,147,179,69,91,177,238,6,400,481,415,101,495,156,443,186,379,71,229,452,240,431,14,364,82,318,454,22,62,196,161,123,414,147,187,457,461,468,196,73,497,435,260,276,404,303,387,251,67,203,462,399,314,6,193,101,6,168,196,135,357,395,190,193,414,367,361,453,74,302,127,244,40,261,98,271,170,429,274,483,390,23,454,313,438,313,106,274,396,370,476,208,491,366,286,320,16,399,129,62,153,189,234,24,90,19,271,251,51,244,295,272,367,256,219,228,88,228,138,208,45,237,74,306,159,421,56,234,500,52,352,143,23,45,438,436,405,274,187,122,418,428,354,404,402,116,467,191,17,387,263,214,444,412,462,376,125,96,412,417,450,289,61,172,287,108,441,372,475,25,156,103,131,171,351,314,488,9,85,86,12,371,207,232,481,199,401,322,137,164,170,165,267,218,480,49,269,156,70,388,344,336,12,207,415,351,278,395,268,71,61,261,397,43,445,55,200,138,70,281,284,460,475,300,378,343,145,90,57,56,305,469,306,4,314,496,20,63,320,297,70,436,232,113,460,95,498,57,30,294,245,143,437,36,246,424,487,269,109,340,471,424,39,301,351,19,338,476,165,99,384,178,22,350,497,225,462,415,252,444,498,397,398,234,444,216,267,280,255,127,111,462,56,232,422,14,158,3,113,97,279,264,303,289,437,352,460,433,54,399,45,320,284,45,158,442,145,385,483,384,200,377,135,137,399,297,184,348,59,404,341,255,131,4,167,27,457,50,97,157,20,52,220,99,408,58,12,233,225,90,216,245,36,403,126,307,496,318,52,369,487,408,28,200,158,245,386,470,144,213,25,434,444,165,49,139,347,358,40,209,95,27,40,394,190,242,462,286,315,159,175,231,76,265,90,46,259,435,19,225,218,179,231,131,271,279,277,51,444,303,482,205,215,180,322,3,11,185,409,465,73,188,192,141,172,250,401,220,274,24,298,188,21,63,395,348,11,364,471,363,287,164,387,273,385,218,379,164,433,328,443,208,489,110,75,176,119,31,451,83,372,246,500,447,115,358,453,266,194,286,355,103,268,110,154,154,34,312,13,417,42,292,18,196,111,372,496,466,243,120,443,77,328,152,459,251,347,5,290,491,452,104,409,232,404,19,327,62,265,290,82,131,290,3,324,104,192,330,471,89,46,262,13,468,466,278,78,35,77,289,248,361,455,182,418,157,74,381,486,51,78,68,273,129,495,3,476,384,187,113,397,188,343,112,166,439,370,77,86,491,442,489,445,171,97,289,1,182,338,359,476,264,401,411,55,51,35,275,278,392,467,275,169,143,474,418,428,431,92,311,76,51,409,169,173,174,25,188,26,320,280,349,72,86,35,362,194,346,161,336,106,124,3,30,35,99,80,341,189,406,253,262,493,420,366,174,438,448,260,135,69,185,453,80,478,100,435,173,108,341,241,200,477,285,176,405,448,103,115,339,277,478,80,333,308,285,149,147,410,443,128,102,7,431,447,227,146,362,301,408,41,300,179,133,22,162,28,257,26,35,469,414,90,398,461,349,17,438,323,100,132,202,307,310,19,217,437,394,441,316,325,476,359,67,52,318,329,208,46,405,435,299,49,222,394,103,425,117,233,287,271,273,12,494,480,245,33,284,360,125,366,134,32,204,76,142,107,424,299,181,46,4,35,136,140,169,116,391,47,497,467,357,373,454,455,289,191,198,449,271,326,441,33,345,65,152,238,106,324,61,14,391,104,121,112,249,345,245,128,224,371,289,103,155,193,496,148,325,405,466,360,362,433,45,198,32,184,304,336,110,479,267,208,285,489,145,140,54,488,157,139,133,125,253,249,121,187,366,19,158,85,314,340,201,352,397,350,159,98,405,371,258,381,469,36,19,352,38,186,379,301,213,495,170,318,314,218,419,356,325,256,338,227,307,188,432,392,237,236,63,193,66,437,387,421,492,295,334,105,287,238,248,392,365,150,476,268,131,148,54,387,343,464,159,47,200,57,72,286,210,48,54,463,423,497,144,223,438,195,249,165,72,332,114,366,382,212,274,421,256,149,109,345,106,86,452,178,266,173,184,371,103,106,162,359,160,147,357,224,409,470,184,378,29,249,252,150,279,223,484,389,486,357,424,100,173,418,489,363,395,426,284,6,240,227,55,66,378,431,46,146,420,484,123,106,323,56,55,452,340,33,486,382,344,426,287,474,184,324,438,110,161,118,356,252,113,234,183,178,20,430,39,263,300,323,378,105,461,1,353,197,70,61,157,58,166,118,27,126,388,253,292,387,435,181,493,499,15,387,216,397,206,391,141,18,356,89,286,289,351,401,368,336,279,31,12,184,264,216,295,356,179,499,214,231,245,205,250,93,340,46,141,302,108,306,291,192,299,293,266,224,110,31,459,257,213,332,267,88,42,96,75,237,331,4,284,392,432,312,307,373,351,416,266,486,443,291,197,455,476,91,331,225,136,331,58,60,272,14,42,375,109,363,431,360,376,364,310,77,211,117,61,480,293,204,148,143,202,467,324,429,52,215,359,260,31,301,262,373,450,15,274,239,372,76,404,341,424,337,5,227,174,53,486,140,379,394,437,275,153,229,11,381,269,58,372,469,298,361,14,301,441,303,146,130,355,155,241,252,461,369,60,355,221,6,68,3,310,446,483,393,360,137,58,160,190,339,145,481,254,48,222,183,460,272,14,488,499,364,458,269,246,107,387,250,85,350,147,312,437,341,442,26,140,383,29,353,35,122,46,435,289,29,14,323,31,120,326,491,367,99,263,117,23,436,14,255,148,244,105,448,193,26,184,400,200,140,289,448,124,24,276,247,385,220,339,438,306,78,191,469,111,201,233,275,217,38,118,155,392,261,392,89,132,197,159,1,456,11,348,5,394,215,462,426,338,482,388,498,82,298,404,89,195,489,87,348,431,39,106,172,457,471,51,5,20,490,102,268,348,308,264,84,180,441,420,430,262,273,405,193,270,149,329,451,119,416,449,302,249,478,50,192,485,252,54,207,20,238,205,362,161,156,493,46,302,165,258,265,91,195,370,499,282,213,482,148,144,300,103,255,359,335,415,366,178,127,241,56,9,500,72,61,334,481,277,58,492,128,276,431,208,363,112,358,447,328,140,103,233,91,254,314,313,359,223,227,115,112,89,150,401,348,168,483,15,125,466,500,87,424,291,158,269,66,481,76,196,198,218,356,158,108,353,455,12,433,232,369,184,104,453,71,178,470,304,187,376,379,307,80,366,67,110,496,362,195,196,392,385,9,12,367,396,163,360,275,163,377,173,238,170,298,321,234,327,123,348,58,202,300,420,383,73,373,126,40,188,222,38,486,342,19,202,272,142,385,331,265,67,399,467,305,228,298,134,36,200,250,429,310,116,226,402,336,480,8,245,134,274,319,108,299,491,275,277,364,200,345,39,241,430,124,184,350,206,96,130,227,338,71,54,341,462,447,271,47,164,490,369,394,260,70,151,261,69,141,239,430,226,31,143,187,458,458,70,258,376,357,483,489,248,22,411,35,492,354,149,464,196,390,409,297,150,128,302,86,295,254,163,358,460,387]
324

失敗原因

⋯⋯算太久了。

構想：

用二分法尋找 capacity。capacity 上限是重量總和，下限是「每日平均重量 和 最大重量」之中最大的那個。二分法結束之後，再用一個 while 迴圈，確保這個 capacity 一定是最小的。確保方式：如果 capacity - 1 就會超過天數的話，那這個 capacity 就是最小的。

python 3 實作（失敗）：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

        weights_sum = sum(weights) 

        min_capacity = max(weights_sum // days, max(weights)) 

        max_capacity = weights_sum 

        capacity = max_capacity 

         

        while max_capacity >= min_capacity: 

            mid_capacity = (min_capacity + max_capacity) // 2 

            result = self.timely(weights, days, mid_capacity) 

             

            if result is False: 

                min_capacity = mid_capacity + 1 

            elif result == days: 

                if mid_capacity < capacity: 

                    capacity = mid_capacity 

                max_capacity = mid_capacity - 1 

            else: 

                max_capacity = mid_capacity - 1 

        while self.timely(weights, days, capacity - 1): 

            capacity -= 1 

         

        return capacity 

     

    @staticmethod 

    def timely(weights, days, capacity): 

        needed_days = 1 

        package_wieghts = 0 

        for weight in weights: 

             

            if package_wieghts + weight > capacity: 

                needed_days += 1 

                if needed_days > days: 

                    return False 

                package_wieghts = 0 

            package_wieghts += weight 

             

        return needed_days

Submission Detail

Wrong Answer

Input:
[1,2,3,1,1]
4

Output: 2

Expected: 3

失敗原因

我太執著於「花費的天數一定要等於 days」了，其實小於 days 也可以。

timely 函式並沒有檢查「weight 一定要小於等於 capacity」。第一個 while 迴圈因為有控制 capacity 的範圍，所以不會有問題，但第二個 while 迴圈沒有控制 capacity 的下限，所以會有問題。

構想：

取消 result == days 的條件判斷。實驗「第一個 while 迴圈跑完，得到的是否就是正確答案」，所以把第二個 while 拿掉。

python 3 實作：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

        weights_sum = sum(weights) 

        min_capacity = max(weights_sum // days, max(weights)) 

        max_capacity = weights_sum 

        capacity = max_capacity 

         

        while max_capacity >= min_capacity: 

            mid_capacity = (min_capacity + max_capacity) // 2 

            if self.is_in_time(weights, days, mid_capacity): 

                if mid_capacity < capacity: 

                    capacity = mid_capacity 

                max_capacity = mid_capacity - 1 

            else: 

                min_capacity = mid_capacity + 1 

         

        return capacity 

     

    @staticmethod 

    def is_in_time(weights, days, capacity): 

        needed_days = 1 

        package_wieghts = 0 

        for weight in weights: 

            if package_wieghts + weight > capacity: 

                needed_days += 1 

                if needed_days > days: 

                    return False 

                package_wieghts = 0 

            package_wieghts += weight 

             

        return True

效能：

Runtime: 568 ms, faster than 49.63% of Python3 online submissions for Capacity To Ship Packages Within D Days.
Memory Usage: 17 MB, less than 46.30% of Python3 online submissions for Capacity To Ship Packages Within D Days.

研究別人的解

來源：sample 508 ms submission

研究重點：想看更簡潔、更有效率的寫法。

別人的 python 3 實作：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

         

        def count_days(capacity): 

            # ensure that capacity >= max(weights) 

            days = 1 

            cap = capacity 

            for w in weights: 

                if cap < w: 

                    days += 1 

                    cap = capacity 

                cap -= w 

            return days 

         

        # at least max of weights, at most sum of weights 

        lo, hi = max(weights), sum(weights) 

        while lo < hi: 

            mid = (lo + hi) >> 1 

            d = count_days(mid) 

            if d > days: 

                lo = mid + 1 

            else: 

                hi = mid 

                 

        return lo

效能：

Runtime: 500 ms, faster than 83.08% of Python3 online submissions for Capacity To Ship Packages Within D Days.
Memory Usage: 17 MB, less than 75.15% of Python3 online submissions for Capacity To Ship Packages Within D Days.

研究感想

用 x >> 1 代替 x 除以 2 後無條件捨去到整數位。

他的 while 迴圈結束後回傳 lo。這樣就不用像我那樣，還多一個 capacity 變數，而且還多一個 if 判斷要不要更新 capacity。

他的 count_days 回傳載貨需要的天數。我的 is_in_time 回傳是否超過期限，如果超過期限就馬上回傳 False，所以我的 is_in_time 應該會比較早算完。

改成「 x >> 1」和「回傳 lo」以後，我的程式碼效能變化不大，依然在 550 ms 以上，但是我把 for 迴圈改成底下這樣之後，感覺有變快了，效能甚至可以到達 490 ms 左右：

for weight in weights: 

    package_wieghts += weight  

    if package_wieghts > capacity: 

        package_wieghts = weight 

        needed_days += 1 

        if needed_days > days: 

            return False

效能之所以改善，是因為寫成這樣就不用做兩次加法嗎？

研究別人的解

來源：sample 380 ms submission

研究重點：想看更簡潔、更有效率的寫法。

別人的 python 3 實作：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

         

        def daysRequired(capacity): 

            total = 0 

            days  = 1 

            for w in weights: 

                total += w 

                if total > capacity: 

                    days += 1 

                    total = w 

            return days 

         

        maximum = max(weights) 

        high = maximum*(len(weights)//days+1) 

        low  = maximum 

         

        while low + 1 < high: 

            mid = (low + high) // 2 

            if daysRequired(mid) <= days: 

                high = mid 

            else: 

                low  = mid 

                 

        if daysRequired(low) <= days: 

            return low 

        else: 

            return high

效能：

Runtime: 388 ms, faster than 99.67% of Python3 online submissions for Capacity To Ship Packages Within D Days.
Memory Usage: 16.9 MB, less than 75.15% of Python3 online submissions for Capacity To Ship Packages Within D Days.

研究感想

他的 high 的初始值比較小。

以本文之前提到的那個超級長的 input 來實驗，印出 mid_capacity，看我和他的解有什麼不一樣。

我的解，印出來的 mid_capacity，共有 22 個：

1458761 733868 371421 190198 99586 54280 31627 20301 14638 11806 10390 9682 9328 9151 9239 9195 9173 9162 9156 9159 9157 9157

他的解，印出來的 mid_capacity，共有 15 個：

9500 5000 7250 8375 8937 9218 9077 9147 9182 9164 9155 9159 9157 9156 9157

研究別人的解

來源：sample 360 ms submission

研究重點：上限和下限的初始值設成多少。

別人的 python 3 實作：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

        def can_ship(c): 

            s, cnt = 0, 1 

            for w in weights: 

                if s + w <= c: 

                    s += w 

                else: 

                    cnt+=1 

                    s = w 

            return cnt <= days 

             

        max_w = max(weights) 

        l, r = sum(weights)//days-1, max_w*(len(weights)//days+1) 

        while r-l>1: 

            mid = (l+r)//2 

            if max_w <= mid and can_ship(mid): 

                r = mid 

            else: 

                l = mid 

        return r

效能：

Runtime: 356 ms, faster than 100.00% of Python3 online submissions for Capacity To Ship Packages Within D Days.
Memory Usage: 17.3 MB, less than 6.73% of Python3 online submissions for Capacity To Ship Packages Within D Days.

研究感想

他的解，印出來的 mid_capacity，共有 14 個：

13737 11356 10165 9570 9272 9123 9197 9160 9141 9150 9155 9157 9156 9157

那個初始值到底是怎麼想到的⋯⋯

研究別人的解後，優化自己的解

python 3 實作：

class Solution: 

    def shipWithinDays(self, weights: List[int], days: int) -> int: 

        weights_sum = sum(weights) 

        max_weight = max(weights) 

        min_capacity = max(weights_sum // days, max_weight) 

        max_capacity = max_weight*(len(weights) // days + 1) 

         

        while max_capacity >= min_capacity: 

            mid_capacity = (min_capacity + max_capacity) >> 1 

            if self.is_in_time(weights, days, mid_capacity): 

                max_capacity = mid_capacity - 1 

            else: 

                min_capacity = mid_capacity + 1 

         

        return min_capacity 

     

    @staticmethod 

    def is_in_time(weights, days, capacity): 

        needed_days = 1 

        package_wieghts = 0 

  

        for weight in weights: 

            package_wieghts += weight 

            if package_wieghts > capacity: 

                package_wieghts = weight 

                needed_days += 1 

                if needed_days > days: 

                    return False 

 

        return True

效能：

Runtime: 368 ms, faster than 99.93% of Python3 online submissions for Capacity To Ship Packages Within D Days.
Memory Usage: 17 MB, less than 75.15% of Python3 online submissions for Capacity To Ship Packages Within D Days.

Comments

Post a Comment

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more