[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