Statistics

Problem Statement for "NicePartition"

Problem Statement

Optimus Prime wants to build 2*N buildings. You are given their heights in the int[] H.

The buildings have to be partitioned into two rows: row A and row B. We will use A[i] to denote the height of the i-th building (0-based index) in row A, and B[i] for row B. The partition into A and B must satisfy the following constraints:

  • Each row must contain N buildings.
  • The rows must be aligned: for each i, the i-th building in row A will stand opposite to the i-th building in row B.
  • The heights of buildings in row A must form a non-decreasing sequence: for each i, A[i] <= A[i+1].
  • The heights of buildings in row B must form a non-increasing sequence: for each i, B[i] >= B[i+1].

The instability of a pair of buildings that stand opposite each other is the absolute difference between their heights: | A[i] - B[i] |.

The instability of the whole partition is the total instability over all N such pairs of buildings.

Optimus Prime wants the most optimistic partition: the one whose instability is minimal. Calculate and return the smallest possible instability of the partition of Optimus Prime's buildings.

Definition

Class:
NicePartition
Method:
minCost
Parameters:
int[]
Returns:
int
Method signature:
int minCost(int[] H)
(be sure your method is public)

Constraints

  • Length of H will be an even integer between 2 and 400, inclusive.
  • Each element of H will be between 0 and 500, inclusive.

Examples

  1. {0,2}

    Returns: 2

    There are two possible partitions: either A = {2} and B = {0}, or A = {0} and B = {2}. In each case the instability is |2-0| = 2.

  2. {3,5,1,5,7,9}

    Returns: 12

    Partition A = {3,7,9} B = {5,5,1} gives the minimum instability. Its instability is |3-5| + |7-5| + |9-1| = 2 + 2 + 8 = 12. There are other partitions which give the minimum instability as well. One of them is: A = {1,5,5} B = {9,7,3}

  3. {31,52,11,52,73,19,54,124,21,1}

    Returns: 272

    One optimal partition: A = {19,21,31,54,73} B = {124,52,52,11,1} Instability = |19-124| + |21-52| + |31-52| + |54-11| + |73-1| = 272

  4. {1,1,1,1,1,1}

    Returns: 0

  5. {427,251,203,280,227,393,497,191,247,99,242,147,353,330,500,16,232,370,100,294,391,123,440,55,309,402,324,179,256,103,245,35,316,173,192,241,376,102,336,61,74,286,156,320,185,293,388,252,226,2,407,13,85,217,275,219,488,306,301,22,82,18,23,164}

    Returns: 6930

  6. {177,492,237,316,70,397,454,31,159,16,152,357,275,269,264,229,114,10,368,224,357,2,381,27,123,107,416,289,6,356,376,291,38,99,405,219,266,446,233,20,250,216,432,222,56,254,80,123,285,485,316,463,440,350,240,64,237,184,193,402,416,178,115,363,451,385,187,334,13,378,108,328,258,431,152,72,377,21,283,155,245,301,122,40,455,466,378,81,24,428,151,230,337,339,276,332,59,59,111,166,84,86,64,271,401,156,271,492,238,103,347,27,220,321,187,481,317,15,35,246,496,388,487,436,128,242,211,24,282,170,106,344,36,174,0,361,23,398,315,192,373,464,311,208,18,241,146,224,155,186,105,388,475,288,457,65,11,330,258,136,439,300,186,247,358,89,17,340,389,492,52,183,340,236,206,118,330,387,252,349,68,199,228,411,294,371,417,353,30,321,264,74,198,289,206,106}

    Returns: 23274

  7. {321,103,130,400,415,279,396,486,474,134,296,155,111,195,249,221,219,55,407,322,261,392,212,349,465,212,20,54,31,366,157,149,450,293,173,444,480,182,325,301,236,474,252,326,378,250,17,477,462,275,224,98,477,209,154,83,348,342,420,2,59,133,196,184,287,321,305,87,438,249,361,480,303,94,494,55,36,449,112,21,444,112,155,270,16,202,255,425,284,179,350,315,271,51,348,246,55,119,18,46}

    Returns: 12093

  8. {463,210,438,95,300,192,114,72,330,226,125,193,384,326,338,6}

    Returns: 1798

  9. {427,251,203,280,227,393,497,191,247,99,242,147,353,330,500,16,232,370,100,294,391,123,440,55,309,402,324,179,256,103,245,35,316,173,192,241,376,102,336,61,74,286,156,320,185,293,388,252,226,2,407,13,85,217,275,219,488,306,301,22,82,18,23,164}

    Returns: 6930

  10. {177,492,237,316,70,397,454,31,159,16,152,357,275,269,264,229,114,10,368,224,357,2,381,27,123,107,416,289,6,356,376,291,38,99,405,219,266,446,233,20,250,216,432,222,56,254,80,123,285,485,316,463,440,350,240,64,237,184,193,402,416,178,115,363,451,385,187,334,13,378,108,328,258,431,152,72,377,21,283,155,245,301,122,40,455,466,378,81,24,428,151,230,337,339,276,332,59,59,111,166,84,86,64,271,401,156,271,492,238,103,347,27,220,321,187,481,317,15,35,246,496,388,487,436,128,242,211,24,282,170,106,344,36,174,0,361,23,398,315,192,373,464,311,208,18,241,146,224,155,186,105,388,475,288,457,65,11,330,258,136,439,300,186,247,358,89,17,340,389,492,52,183,340,236,206,118,330,387,252,349,68,199,228,411,294,371,417,353,30,321,264,74,198,289,206,106}

    Returns: 23274

  11. {321,103,130,400,415,279,396,486,474,134,296,155,111,195,249,221,219,55,407,322,261,392,212,349,465,212,20,54,31,366,157,149,450,293,173,444,480,182,325,301,236,474,252,326,378,250,17,477,462,275,224,98,477,209,154,83,348,342,420,2,59,133,196,184,287,321,305,87,438,249,361,480,303,94,494,55,36,449,112,21,444,112,155,270,16,202,255,425,284,179,350,315,271,51,348,246,55,119,18,46}

    Returns: 12093

  12. {463,210,438,95,300,192,114,72,330,226,125,193,384,326,338,6}

    Returns: 1798

  13. {500,500,210,500,148,115,500,311,322,236,500,460,500,287,500,451,500,138,500,55,500,303,500,124,471,401,396,266,261,428,500,500,500,7,170,500,185,315,467,438,171,500,500,369,251,500,500,5,500,263,500,395,500,500,500,500,359,500,500,47,500,290,500,100,500,277,500,500,500,92,134,4,228,482,286,6,500,305,500,441,500,500,175,492,500,340,500,307,500,500,500,500,374,436,137,500,500,500,342,48,500,352,500,500,500,465,500,500,500,440,500,179,500,232,133,500,73,500,206,500,79,166,500,500,500,469,500,307,500,32,415,278,500,500,321,500,426,250,500,500,54,389,500,500,500,500,500,500,500,500,277,500,500,500,362,3,391,491,500,47,500,500,155,460,500,500,500,413,500,171,500,500,500,500,60,500,500,500,500,67,500,288,500,500,500,500,64,500,366,31,210,500,59,500,143,500}

    Returns: 23055

  14. {15,58,423,348,146,322,323,360,266,248,86,210,191,181,30,349,140,307,349,159,148,205,378,31,20,437,208,157,98,290,193,268,275,233,272,124,319,422,229,294,483,187,441,374,493,69,311,406,483,455,205,436,209,496,373,272,41,298,122,71,15,253,42,492}

    Returns: 7491

  15. {450,461,192,416,455,340,387,1,90,496,478,188,190,165,300,337}

    Returns: 2020

  16. {275,440,376,131,70,488,233,259,21,227,196,411,387,128,47,334,390,27,53,209,303,116,173,202,233,91,481,279,493,121,168,183,164,389,318,174,296,132,167,147,299,123,330,451,37,458,488,381,3,425,338,306,468,118,451,33,484,441,231,104,27,200,14,132,186,218,247,490,217,479,415,216,315,411,348,121,248,225,454,388,216,224,170,88,324,271,63,396,183,71,408,292,386,73,70,472,456,132,493,118,240,73,479,153,431,69,219,186,52,103,81,270,470,408,291,460,294,259,375,490,63,247,74,347,178,367,457,29,150,354,294,158,355,87,19,310,410,2,279,100,194,183,246,412,122,106,163,326,314,348,328,368,158,495,284,215,250,109,325,260,333,151,98,474,417,323,111,242,135,210,375,261,428,362,259,244,453,21,318,15,25,182,460,316,163,167,319,386,65,285,317,218,409,305,56,324,180,6,167,251,62,101,103,50,20,232,64,264,198,10,88,119,418,189,253,143,214,108,455,238,143,172,26,10,235,92,29,217,184,138,388,290,355,28,164,498,270,418,111,284,49,190,143,382,406,30,157,486,423,399,324,245,63,252,79,48,367,225,110,417,113,116,237,211,199,69,254,148,137,111,371,346,66,314,193,14,111,385,470,376,472,198,280,152,183,70,213,374,212,254,333,42,286,286,493,321,56,314,288,441,150,402,387,265,355,69,225,233,467,294,67,279,41,34,222,495,243,401,266,274,262,295,480,83,158,30,18,334,138,311,413,302,141,150,327,58,135,77,58,270,204,384,35,148,428,455,88,228,115,239,252,327,322,427,142,14,200,234,364,136,366,412,459,69,234,269,113,486,437,256,206,112,33,314,390,463,321,426,345,402,360,145,118,94,429,48,11,208,101,169,461,277,230,2,304,39,479,488,337,36}

    Returns: 47635

  17. {274,278,267,75,497,276,244,168,41,28}

    Returns: 1036

  18. {387,490,500,500,500,322,500,500,481,500,500,500,500,1,134,473,500,500,200,500,288,500,500,155,500,163,500,145,500,500,500,99,500,29,396,500,177,360,500,500,500,500,500,495,500,142,500,36,500,283,500,500,192,260,426,206,500,97,355,500,500,500,26,78,500,116,500,302,209,500,500,326,66,407,88,500,500,482,187,500,282,127,196,500,500,128,238,500,500,500,50,472,500,500,500,91,148,500,500,162,240,18,500,500,500,500,500,500,500,500,343,500,500,337,183,130,239,150,341,500,500,187,500,191,500,500,500,100,144,500,89,214,500,65,484,39,500,174,500,500,433,500,337,500,190,500,500,500,500,283,186,500,430,500,42,500,386,500,134,203,500,228,500,56,412,500,500,170,102,4,445,500,500,500,439,215,500,500,494,316,500,419,500,490,500,500,397,358,500,73,500,500,500,500,500,275,430,452,500,332,500,317,500,500,419,371,285,160,500,337,247,448,500,500,500,500,415,500,500,500,500,286,334,500,196,69,500,209,455,500,210,200,375,500,500,226,26,500,500,228,500,500,327,478,500,500,500,317,500,500,470,423,500,192,500,500,500,445,500,159,184,184,500,7,99,500,500,96,211,381,288,500,500,500,48,5,500,271,500,102,8,500,500,500,480,500,30,500,500,137,500,488,500,500,500,321,145,51,500,500,349,394,77,500,67,500,76,500,500,97,500,500,395,500,12,465,500,500,500,256,500,338,285,500,491,215,500,61,331,423,114,64,500,500,500,291,429,500,500,255,500,206,500,500,500,255,500,500,500,500,500,500,500,25,319,500,239,500,392,500,500,500}

    Returns: 44547

  19. {374,63,393,314}

    Returns: 390

  20. {128,42,312,136,176,217,286,63,121,189,180,224,469,397,416,22,174,488,402,288,443,272,311,423,217,243,58,40,251,495,277,467,121,80,327,444,457,97,72,69,286,268,476,261,248,293,344,315,81,56,259,366,478,32,69,442,470,324,79,389,249,323,325,40,156,355,244,2,416,216,204,172,252,196,481,180,362,127,91,453,376,421,416,257,183,443,62,482,311,44,425,40,212,148,4,204,305,41,463,345,456,179,496,228,7,8,233,320,497,107,82,45,183,290,69,224,239,156,356,337,169,191,356,252,348,385,223,426,310,388,488,413,277,280,2,17,120,223,242,109,37,304,262,101,454,413,371,355,326,152,480,68,473,22,487,111,164,380,461,201,460,417,352,190,24,1,474,137,180,17,150,257,50,397,162,73,57,485,326,157,278,27,209,425,11,434,256,237,379,460,494,233,345,78,473,119,453,489,459,429,93,240,450,54,467,267,228,242,239,202,71,296,343,164,297,100,481,460,345,251,476,431,48,309,211,348,389,459,98,467,459,9,375,305,95,245,223,241,182,109,115,3,270,344,139,324,108,384,9,151,162,51,434,464,221,175,237,153,121,228,367,294,3,61,312,404,26,325,478,355,408,466,168,27,329,148,200,263,108,175,79,281,479,212,314,459,13,444,19,114}

    Returns: 36870

  21. {169,500,486,164,52,157,492,340,114,115,355,315,355,352,119,81,449,141,190,468,108,500,480,487,447,209,25,209,375,409,173,11,348,493,175,197,269,271,131,146,141,334,436,96,138,471,247,388,427,201,393,15,303,156,398,124,236,397,456,248,79,88,22,8,347,414,395,499,232,184,378,231,394,352,193,340,49,298,19,279,434,198,142,282,197,483,106,257,117,171,323,50,499,224,260,96,202,377,474,311,477,423,309,435,470,398,278,309,13,267,396,15,127,55,48,203,77,243,455,276,82,243,319,428,428,382,447,435,186,177,17,178,231,133,152,234,292,406,450,160,157,277,207,166,267,254,323,212,348,101,490,407,444,87,73,407,153,384,164,181,290,410,484,284,89,198,174,320,433,497,395,292,182,2,414,416,25,114,299,432,317,244,8,395,314,14,5,351,459,63,391,452,5,310,143,9,404,192,381,168,109,275,251,311,429,181,252,459,241,359,339,235,375,497,165,321,483,404,445,465,403,233,134,393,263,99}

    Returns: 28052

  22. {483,211,217,395,335,500,6,299,385,4,146,97,499,418,142,442,281,414,316,175,64,52,240,182,343,374,140,499,427,7,236,246,122,13,84,163,302,375,97,428,91,342,360,109,93,478,361,37,305,394,51,405,469,463,33,29,228,280,155,10,235,335,237,312,80,231,106,219,177,430,32,276,347,375,278,482,395,402,175,159,353,264,268,470,147,11,205,96,314,144,14,124,347,118,446,197,461,340,173,266,98,326,410,445,478,284,150,2,300,54,302,66,425,347,483,59,392,249,370,368,7,414,267,289,259,463,335,295,9,278,471,165,249,366,157,437,439,196,200,214,175,337,182,450,370,66,224,204,141,143,151,219,335,207,63,410,68,395,161,171,219,354,399,87,414,91,307,51,293,15}

    Returns: 20967

  23. {314,500,500,336,78,500,500,51,500,97,329,500,500,222,500,66,500,381,116,500,180,500,500,139,465,500}

    Returns: 3726

  24. {462,120,372,18,100,165,226,131,249,69,70,93,411,262,180,498,288,494,245,221,26,324,215,162,468,479,87,431,380,91,448,170,489,466,230,296,399,246,251,69,50,159,106,195,296,83,335,193,298,317,383,168,243,320,276,499,146,262,445,347,260,70,21,185}

    Returns: 7444

  25. {6,372,488,347,194,55,102,32,324,200,149,112,423,37,389,433,139,320,109,159,442,255,428,457,351,243,260,219,119,389,352,455,393,222,369,59,345,138,74,43,65,125,265,410,46,65,21,233,117,210,367,10,426,65,133,322,324,154,278,296,260,465,69,396,419,483,304,458,87,306,454,378,189,25,243,112,47,5,259,370,219,177,70,420,192,448,281,58,16,415,443,442,427,385,434,349,418,174,19,472}

    Returns: 13381

  26. {17,435,359,300,405,404,71,10,462,429,225,196,147,91,406,438,207,146,430,85,80,98,470,276,65,324,495,162,369,111,165,438,77,73,39,337,54,161,422,404,489,262,338,195,416,179,339,102,70,391,51,461,17,31,378,186,464,252,179,385,20,474,405,455,452,284,307,240,336,378,123,348,499,63,426,150,287,294,141,320,254,142,162,256,261,274,94,138,134,482,223,29,125,450,25,391,275,451,334,252,67,141,431,25,243,489,255,451,257,208,387,490,292,230,124,25,380,18,291,16,274,11,162,331,392,97,87,198,286,209,130,214,132,80,366,498,52,78,71,441,249,107,55,174,436,36,334,279,120,15,329,205,460,378,450,71,56,256,72,420,75,367,290,186,295,380,458,393,16,434,215,237,307,334,298,297,89,253,18,125,483,251,499,435,469,232,389,407,273,433,464,204,194,251,437,167,51,119,471,266,233,130,160,144,344,40,494,347,457,360,367,395,102,144,188,301,383,452,234,372,348,480,258,102,433,279,352,243,112,364,245,132,380,336,46,179,37,443,455,373,270,167,179,19,199,479,96,372,225,314,314,285,486,69,425,80,311,310,250,60,379,171,498,136,170,139,245,430,437,148,435,490,319,161,233,132,160,79,444,354,418,104,263,53,404,229,176,11,387,97,102,169,490,31,352,353,292,159,11,91,282,495,498,283,459,190,436,51,145,365,9,150,243,351,454,374,435,424,307,231,445,445,263,270,312,281,265,293,354,350,352,169,140,241,351,391,412,327,212,214,47,301,211,283,368,281,171,112,175,148,287,163,168,263,11,464,119,441,427,383,112,9}

    Returns: 44636

  27. {368,301,152,305,394,225,25,424,76,118,61,0,392,300,133,53,229,474,287,356,360,307,265,452,460,62,124,99,187,496,497,92,28,493,247,88,353,408,109,196,124,321,432,81,238,27,220,224,313,34,53,399,285,442,368,160,331,458,38,100,357,385,473,412,188,463,57,120,118,146,373,384,394,335,26,156,70,296,401,486,182,107}

    Returns: 11027

  28. {26,276,447,500,400,313,455,122,500,288,295,500,500,500,127,500,500,332,500,500,353,185,500,136,367,500,279,500,500,500,478,299,93,500,500,270,464,83,500,500,500,500,500,66,500,295,417,500,344,29,313,500,500,500,500,500,500,473,500,263,11,438,500,500,302,500,500,410,500,262,457,126,81,82,500,373,500,500,500,500,257,500,152,228,103,500,500,500,252,489,174,500,500,500,500,500,422,500,455,500,127,500,487,500,500,6,500,500,500,145,500,500,500,428,500,496,500,244,500,500,304,153,239,500,356,382,500,500,500,351,10,500,185,500,473,312,475,239,500,482,500,473,500,500,9,500,74,500,109,500,500,356,475,381,500,201,122,481,500,21,499,498,104,500,233,282,127,500,15,218,500,500,500,257,205,132,335,500,500,500,400,75,412,35,500,500,251,327,470,500,500,500,500,56,354,172,500,500,500,500,151,371,217,500,500,500,500,15,112,125,500,500,500,83,500,500,500,500,500,500,440,245,500,500,500,500,208,472,221,399,439,160,470,287,500,86,353,500,500,500,500,399,179,363,500,331,37,211,500,500,75,265,150,482,500,500,450,500,53,500,246,500,188,500,39,76,433,500,500,500,500,500,453,206,305,160,28,320,500,44,500,342,500,229,500,500,127,500,2,500,402,417,500,197,500,132,465,111,500,173,428,500,500,500,500,500,500,500,500,500,500,500,500,500,74,58,500,167,313,500,500,500,5,239,396,500,500,500,500,500,447,65,500,500,500,313,162,336,248,500,500,500,388,104,432,31,500,500,500,137,221,500,500,189,145,500,38,500,139,182,500,500,27,500,500,500,500,500,359,500,500,149,500,198,262,500,500,314,500,126,14,500,209,500,500,500,500,500,86,500,151,500,495,500,500,453,243,210,257,500}

    Returns: 49331

  29. {400,314,266,254,112,26,26,183,405,463,122,87,436,43,430,393,136,336,352,341,439,116,1,272,485,65,227,324,281,311,31,115,79,58,390,78,484,407,463,139,169,45,359,327,17,421,194,284,191,94,168,48,371,232,328,179,404,368,176,115,1,76,352,160,239,465,359,258,203,260,315,449,332,277,336,265,310,421,195,481,82,484,481,144,318,184,92,108,389,411,251,222,382,304,381,171,466,223,83,135,265,193,292,56,484,93,289,350,146,330,402,241,490,126,217,368,414,248,405,333,12,13,117,351,416,455,231,384,306,175,173,117,327,495,396,5,286,329,72,157,252,238,329,288,90,324,180,179,226,54,163,449,241,69,491,139,30,31,371,351,125,369,397,60,420,248,99,270,419,309,426,79,5,497,66,183,54,458,169,111,162,133,124,106,351,421,367,231,467,411,181,258,139,146,21,420,313,271,187,6,285,438,119,271,287,313,179,1,80,250,250,106,424,468,81,266,423,473,488,361,238,259,184,362,140,423,258,97,13,271,364,437,421,58,245,469,390,17,216,68,442,432,437,251,196,427,179,96,315,55,123,490,471,50,6,325,298,257,124,292,312,284,379,113,378,302,390,173,242,257,442,242,446,358,155,125,157,345,470,358,251,354,309,471,473,443,271,280,264,65}

    Returns: 34786

  30. {1,430,426,99,17,226,181,146,412,423,23,171,432,271,182,202,249,398,183,446,418,295,392,462,67,136,296,232,121,450,197,111,194,67,227,493,161,412,318,193,455,139,386,455,267,366,358,24,287,85,305,277,54,204,460,345,379,10,439,312,350,130,59,345,350,189,263,124,237,276,475,434,311,88,109,261,327,354,146,409,74,272,494,180,423,200,101,123,131,300,386,366,439,472,428,117,189,163,63,174,321,153,491,50,152,461,366,191,271,21,340,458,10,291,304,424,471,95,46,373,185,404,241,95,116,443,32,54,142,222,431,77,419,185,275,102,411,82,320,206,103,311,183,30,46,255,65,482,73,131,380,277,168,462,309,86,370,254,128,222,169,229,245,446,453,116,469,201,260,162,460,106,6,153,13,71,248,405,490,38,44,193,281,56,414,306,284,475,14,268,329,201,105,198,204,473,442,59,392,135,376,320,103,84,198,157,16,401,89,375,423,9,370,90,196,60,54,100,288,27,132,76,247,270,492,427,364,490,267,48,299,449,257,133,457,399,487,180,421,380,444,149,217,337,119,133,91,328,111,286,156,415,107,101,88,387,283,303,247,132,164,17,447,451,98,242,438,186,151,34,31,148,273,427,476,434,250,220,27,433,44,398,404,244,345,83,82,3,208,126,318,361,54,84,195,148,256,431,130,55,149,462,112,336,26,400,313,77,137,491,222,499,51,265,316,36,176,381,248,190,59,166,382,133,404,247,260,61,496,169,334,6,269,44,316,164,113,15,87,76,196,183,152,127,63,475,222,232,301,205,364,390,178,377,59,429,247,56,311,372,482,65,9,478,122,462,369,377,226,59,409,46,173,318,154,34,164,94,7,409,246,228,320,114,306,411,425,412,377,246,161,188,215,22,446,494,166,351,489,94}

    Returns: 50534

  31. {176,291,84,379,60,102,421,226,37,22,155,270,403,161,80,495,16,210,35,289,42,135,345,15,234,114,108,363,283,227,17,407,45,255,1,360,251,161,16,236,26,25,319,125,210,292,29,260,210,60,68,241,136,122,431,263,165,293,125,93,134,275,203,297,172,351,144,78,383,243,383,90,23,199,202,233,60,184,444,229,169,27,201,91,303,59,276,390,213,289,68,36,172,209,456,446,303,413,24,460,477,151,27,203,472,94,380,277,442,131,451,406,377,23,299,213,395,453,60,97,325,352,180,355,332,101,199,357,339,38,111,491,490,87,272,324,429,274,256,55,335,12,275,143,323,211,442,142,69,494,52,400,153,134,299,83,420,143,309,371,442,298,265,281,380,143,314,380,491,227,239,448,193,267,389,494,338,258,491,51,309,90,427,121,38,346,371,287,201,259,286,76,345,66,105,98,409,432,274,99,363,440,224,68,11,6,145,289,129,369,436,351,283,425,52,464,3,338,231,197,362,79,368,239,413,271}

    Returns: 27353

  32. {135,456,415,487,125,457,274,281,430,203,322,5,193,409,62,467,23,459,201,229,428,268,240,32,31,316,381,291,1,304,45,377,307,84,314,99,290,275,74,85,500,136,8,331,246,41,438,462,272,289,215,125,47,288,353,410,125,386,195,63,221,260,200,211,170,296,161,486,86,383,304,146,133,376,166,316,322,450,286,116,312,154,355,108,286,241,444,395,162,496,294,313,109,15,423,351,251,184,40,323,13,459,37,485,491,432,267,281,255,6,496,179,274,169,369,271,374,200,432,53,132,252,50,192,340,149,262,197,173,457,228,159,258,339,395,253,486,120,314,85,35,35,32,360,284,52,455,221,368,139,179,269,457,340,436,428,251,141,483,32,425,206,182,284,158,199,442,149,358,248,389,11,270,161,194,52,145,468,345,351,69,263,302,387,470,19,89,103,256,48,46,356,26,468,383,324,229,419,468,145,120,114,171,486,96,72,306,109,173,231,426,207,381,141,336,267,335,344,324,474,5,205,237,52,267,478,189,332,175,389,245,256,94,271,477,282,42,0,347,344,416,204,41,466,150,39,32,373,37,498,241,234,190,125,39,380,230,5,124,321,210,257,234,341,152,476,469,136,55,313,381,232,469,187,63,72,447,486,91,221,121,423,108,412,102,116,285,479,103,377,201,323,139,243,29,113,242,176,341,456,9,355,330,321,310,398,432,495,156,463,198,296,125,414,235,238,28,278,165,237,243,465,176,453,200,26,229,254,457,123,416,390,226,217,30,155,466,482,14,354,28,184,112,498,396,104,120,201,39,18,436,487,128,479,399,111,149,97,404,83,156,406,203,54,194,465,307,34,439,217,354,340,213,347,77,17,347,356,453,485,174,261,235,97,50,231,9,254,355,285,428,132,323,389,371,345,309,255,70,410}

    Returns: 48821

  33. {500,231,285,500,466,500,60,161,261,500,481,500,500,189,202,500,500,500,500,332,500,500,94,500,500,500}

    Returns: 2738

  34. {192,128,138,329,341,468,157,431,408,360,200,150,367,59,104,360}

    Returns: 1936

  35. {442,75,460,337,402,408,45,32,463,32,385,339,380,422,10,105,320,441,353,167,361,196,420,310,191,442,220,327,294,352,22,394,375,66,136,334,219,237,266,405,416,226,333,8,471,219,101,22,469,196,63,97,162,257,319,199,454,210,288,198,283,178,443,303,363,133,162,50,482,52,201,339,368,400,350,445,294,22,47,101,479,264,412,418,427,246,37,125,418,132,448,83,460,166,333,386,234,74,160,36,360,92,387,170,0,258,100,122,324,223,327,272,399,3,428,370,381,378,42,339,153,134,25,383,464,435,126,14,196,381,214,102,67,357,86,208,329,231,284,44,375,17,245,64,389,323,268,479,99,461,411,168,35,247,308,238,102,334,299,117,315,45,24,326,388,232,283,9,407,336,222,490,361,420,244,446,238,83,407,415,162,39,478,294,198,248,356,311,98,34,208,40,459,323,478,381,188,262,399,221,4,278,115,177,412,418,168,277,32,423,126,56,74,398,279,408,415,308,215,401,31,192,435,32,182,195}

    Returns: 28253

  36. {207,197,463,214,325,357,196,253,78,308,265,226,3,192,418,180,131,292,207,152,467,246,199,135,494,43,283,134,455,54,231,162,499,91,10,482,442,63,13,417,85,464,96,381,448,497,300,227,237,77,471,192,206,246,174,378,146,62,258,105,11,313,87,418,319,388,341,150,183,406,55,39,374,47,467,485,194,273,0,459,464,354}

    Returns: 10415

  37. {217,45,487,12,301,137,242,38,249,145,418,61,145,225,383,237,442,121,443,20,322,216,421,214,13,197,284,289,484,115,239,467,49,496,92,440,196,333,285,438,237,311,275,223,121,171,72,169,181,461,431,156,247,129,247,207,357,101,261,327,450,102,357,233,430,184,420,153,370,73,433,458,442,439,453,267,430,195,11,84,125,410,324,365,0,451,471,472,324,158,488,293,421,475,412,106,43,196,292,249,112,222,220,109,170,129,417,265,183,112,123,266,124,238,345,289,16,61,492,191,451,168,97,20,49,154,54,275,386,98,48,227,382,116,216,186,44,91,277,388,230,102,435,188,299,483,454,423,7,155,386,61,96,271,272,84,273,86,113,241,289,284,135,488,238,435,100,333,359,25,220,2,471,283,200,413,464,304,222,154,146,132,189,324,197,332,61,234,141,193,320,169,417,80,334,79,112,417,207,192,45,438,402,285,40,448,346,168,486,33,60,288,462,128,334,240,148,163,22,99,400,110,25,54,221,408,95,117,322,351,367,152,408,170,12,182,292,445,95,144,471,340,491,15,153,472,170,8,386,161,369,152,159,143,299,43,232,167,107,196,90,482,7,232,262,424,245,138,10,366,10,350,45,193,9,161,485,47,398,23,228,447,60,264,293,31,360,371,405,285,396,440,372,84,308,335,171,499,373,332,285,340,317,63,136,145,304,249,23,92,271,130,233,120,258,357,411,84,67,16,436,16,124,342}

    Returns: 39823

  38. {500,500,500,20,41,435,249,500,500,229,500,500,328,181,78,408,249,500,500,500,500,452,391,500,500,500,500,218,500,105,248,432,500,195,46,500,262,138,222,500,500,301,493,500,141,500,500,407,282,175}

    Returns: 6664

  39. {82,476,486,111,123,238,290,356,127,385,325,177,423,332,447,276,49,159,36,225,308,361,200,218,362,171,291,293,215,396,477,214,405,149,133,313,500,104,320,12,170,72,331,14,369,425,15,266,183,131,86,328,47,351,401,220,226,229,175,109,203,118,429,47,153,75,278,160,232,303,402,77,471,190,388,456,38,462,252,20,368,279,243,198,471,417,296,470,285,216,75,123,372,403,374,463,221,357,295,38,447,200,300,361,13,491,417,130,109,97,423,484,203,480,274,31,475,25,168,352,476,241}

    Returns: 14996

  40. {276,1,483,153,185,83,408,3,178,100,298,467,192,302,340,149,238,9,355,344,132,269,271,487,347,132,407,230,9,200,166,372,73,383,121,240,393,143,64,487,457,471,316,1,62,453,327,74,327,123,451,199,331,374,204,42,259,123,250,399,148,214,321,261,231,326,305,399,456,378,31,312,472,51,438,234,339,461,54,293,228,452,198,342,195,119,109,289,451,312,130,401,334,75,290,423,222,100,291,223,277,187,440,411,380,294,24,163,427,24,52,414,171,280,466,330,449,377,420,120,137,232,97,308,456,320,442,302,228,377,280,317,461,347,292,50,194,391,69,369,432,184,90,442,68,349,464,212,397,112,115,89,62,234,391,139,381,429,365,474,291,441,291,377,378,283,70,47,439,383,369,116,334,265,454,440,179,254,318,251,302,95,114,161,495,471,73,60,435,21,372,40,329,161,85,289,343,205,55,287,411,456,348,76,90,104,103,146,386,250,104,258,258,148,121,16,5,213,56,323,295,369,497,61,285,135,447,87,130,438,454,370,337,39,230,120,196,206,103,284,283,223,473,92,418,290,423,291,206,317,53,80,9,339,384,95}

    Returns: 31005

  41. {306,73,168,321,344,307,62,2,321,171,164,438,305,461,259,46,270,346,396,101,170,231,204,313,40,263}

    Returns: 2700

  42. {307,37,25,446,57,458,322,465,76,387,12,372,239,238,193,207,323,415,78,455,344,106,62,236,283,253,137,178,103,413,286,442,145,43,97,221}

    Returns: 4435

  43. {500,500,19,500,125,500,175,500,102,324,500,500,500,40,500,169}

    Returns: 2546

  44. {422,240,164,263,213,125,239,399,222,464,34,37,382,341,181,284,149,135,499,25,253,491,283,462,305,143,74,252,96,430,208,25,67,294,466,10,407,76,58,95,292,129,363,351,208,66,467,489,151,310,88,324,282,265,219,72,107,401,164,298,416,345,365,319,389,191,292,251,150,353,358,169,259,115,350,3,385,448,138,439,54,421,62,1,125,64,439,349,226,290,85,303,343,126,307,129,463,145,107,296,142,238,495,470,453,176,466,400,373,440,209,210,317,145,237,109,230,283,273,69,334,19,226,457,468,278,207,308,121,486,293,250,432,21,201,427,5,53,455,336,247,227,153,63}

    Returns: 17193

  45. {34,482,439,284,242,233,112,185,227,396,93,281,384,184,7,231,32,360,69,98,346,192,80,271,407,80,224,202,76,68,432,52,178,270,480,179,183,238,278,2,295,26,61,189,368,215,499,390,280,364,243,223,267,132,45,411,365,160,353,156,371,437,276,134,195,82,455,389,76,330,419,337,144,1,146,381,151,169,498,29,291,476,43,257,438,339,450,185,272,175,94,421,274,136,389,161,226,414,436,121,13,425,255,411,22,378,152,171,8,101,311,178,79,107,180,341,392,211,441,124,328,102,175,247,279,122,192,390,108,16,272,11,117,259,411,450,181,469,0,101,285,214,181,343,466,68,296,94,162,89,44,12,63,255,445,310,106,10,37,125,405,470,374,165,394,366,55,218,34,50,460,309,36,468,367,358,147,130,262,413,315,461,339,251,170,242,274,214,322,251,56,324,315,0,230,203,97,484,450,198,407,319,246,112,99,437,45,331,0,471,210,290,399,384,427,178,55,138,132,331,491,108,109,96,150,453,81,39,385,218,494,38,214,314,232,389,233,295,253,182,396,13,308,233,199,418,375,493,243,159,398,493,463,48,419,132,256,173,14,128,128,111,311,145,307,176,36,27,118,85,450,99,485,37,73,101,428,172,128,127,370,286,173,50,388,31,384,453,171,318,30,150,384,461,217,3,451,494,479,379,395,252,429,339,66,387,376,349,335,193,341,356,52,217,177,333,139,452,346,338,224,272,183,163}

    Returns: 40067

  46. {199,81,315,492,114,352,157,372,181,369,158,389,219,111,315,444,97,30,126,429,382,115,333,63,438,86,53,65,450,51,182,467,439,8,192,101,205,353,143,189,27,306,476,443,480,100,177,263,500,233,342,37,28,315,70,23,128,190,497,26,32,438,274,32,341,409,212,337,216,86,104,330,339,6,77,88,77,367,455,297,15,233,102,122,310,263,40,449,430,176,266,23,341,375,413,154,261,427,73,147,173,118,309,331,64,87,171,120,230,109,126,242,464,113,248,199,36,35,245,161,344,43,427,287,296,466,175,56,361,62,88,337,427,32,225,256,226,239,79,128,454,56,143,378,189,195,479,91,67,187,100,41,245,191,181,290,406,283,432,272,262,213,390,497,251,257,309,275,251,220,5,439,26,251,385,236,397,319,487,453,204,434,483,377,106,118,339,300,163,377,155,381,444,136,448,264}

    Returns: 24216

  47. {448,12,20,98,188,159,277,494,115,416,271,22,212,494,31,115,86,160,220,99,6,221,422,239,341,30,65,173,405,94,272,118,227,13,410,285,24,339,64,49,289,225,229,448,289,283,54,208,11,42}

    Returns: 6116

  48. {500,500,432,500,500,500,23,500,500,500,475,371,388,317,500,500,131,417,284,500,500,500,29,500,145,484,153,500,500,421,82,366,500,500,172,500,500,231,500,235,500,500,500,240,268,500,196,500,500,500,500,93,500,500,244,500,390,500,500,500,190,500,500,500,500,500,500,278,233,500,117,50,270,500,44,500,5,500,500,500,500,500,415,500,500,411,500,500,500,500,500,500,468,500,500,500,328,203,500,57,0,318,500,500,358,130,500,11,17,500,246,500,500,87,135,211,500,500,500,500,171,83,500,500,500,500,500,337,184,421,500,500,20,62,66,500,157,8,36,215,500,500,335,500,166,276,500,500,500,500,125,500,15,500,213,500,500,500,500,500,500,195,500,500,500,500,393,184,47,500,500,500,9,500,500,500,500,189,500,379,500,500,173,500,500,346,306,500,170,101,500,346,359,500,500,427,500,500,500,500,500,456,500,500,446,217,82,500,141,500,485,500,196,500,20,500,500,336,465,500,38,107,264,215,500,500,212,500,500,500,500,500,77,500,1,500,70,500,176,27,495,184,72,84,281,179,500,500,383,500,150,500,500,451,40,119,429,500,500,496,238,500,500,500,500,500,500,500,500,109,500,361,401,500,490,21,232,500,500,429,500,500,391,206,500,500,483,500,183,56,459,121,500,373,500,20,52,295,500,114,500,500,277,447,500,259,130,500,500,230,93,251,18,500,242,264,500,500,362,217,299,38,209,500}

    Returns: 41553

  49. {1, 8, 2, 8 }

    Returns: 13

  50. {0, 2 }

    Returns: 2

  51. {463, 210, 438, 95, 300, 192, 114, 72, 330, 226, 125, 193, 384, 326, 338, 6 }

    Returns: 1798

  52. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399 }

    Returns: 40000

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: