Statistics

Problem Statement for "Hamiltons"

Problem Statement

In this problem you are given the ints N >= 6 and L >= 10. We will consider complete undirected graphs with N vertices in which each edge is labeled with a positive integer between 1 and L, inclusive. Below, "a graph" denotes a graph with these properties.


Maru and Vlado were given a standard programming homework: given a graph, find the cost of the cheapest Hamiltonian path.

Maru has implemented her solution properly. Vlado was lazy: He realized that he had recently implemented a program that constructs one of the cheapest Hamiltonian cycles in the given graph. Given this new homework, he now thought: "That's easy! I'll just construct the cycle and then I'll throw away the most expensive edge and I'm done." Your task is to show that this lazy approach does not have to work.

We will now introduce several definitions.

  • Let Maru(G) be the cost of the optimal Hamiltonian path for G.
  • Let Vlado(G) be the smallest cost of a Hamiltonian path Vlado's algorithm might return for G. That is, if G contains multiple cheapest Hamiltonian cycles, assume that Vlado's algorithm will always get lucky and pick the one among them that produces the cheapest Hamiltonian path.

Construct any graph G such that Vlado(G) - Maru(G) >= L/2.

Return a int[] that contains the upper triangular half of the distance matrix of your G in row major order. That is, if the vertices of your graph G are labeled starting from 0 and e(i,j) is the weight of edge i-j, return { e(0,1), e(0,2), ..., e(0,N-1), e(1,2), e(1,3), ..., e(N-2,N-1) }.

Definition

Class:
Hamiltons
Method:
construct
Parameters:
int, int
Returns:
int[]
Method signature:
int[] construct(int N, int L)
(be sure your method is public)

Notes

  • For the given constraints a solution always exists.
  • You are not required to optimize the value Vlado(G) minus Maru(G). Any graph that matches the requirements listed in the statement will be accepted.

Constraints

  • N will be between 6 and 14, inclusive.
  • L will be between 10 and 1000, inclusive.

Examples

  1. 6

    20

    Returns: {20, 6, 5, 16, 20, 1, 3, 6, 17, 8, 1, 9, 14, 14, 6 }

    The distance matrix of the returned graph G: 0 20 6 5 16 20 20 0 1 3 6 17 6 1 0 8 1 9 5 3 8 0 14 14 16 6 1 14 0 6 20 17 9 14 6 0 The shortest Hamiltonian path is the path 0-3-1-2-4-5 with total length Maru(G) = 5 + 3 + 1 + 1 + 6 = 16. The shortest Hamiltonian cycle is the cycle 0-3-1-4-5-2(-0) with total length 5 + 3 + 6 + 6 + 9 + 6 = 35. Hence, Vlado(G) = 35 - 9 = 26. The difference between Vlado(G) and Maru(G) is precisely 10 = L/2.

  2. 6

    1000

    Returns: {174, 325, 60, 839, 248, 437, 398, 965, 806, 658, 985, 969, 319, 100, 149 }

    The distance matrix of the returned graph G: 0 174 325 60 839 248 174 0 437 398 965 806 325 437 0 658 985 969 60 398 658 0 319 100 839 965 985 319 0 149 248 806 969 100 149 0 The shortest Hamiltonian path has length 920. This is the path 2-1-0-3-5-4 with edge lengths 437, 174, 60, 100, 149. The unique shortest Hamiltonian cycle is the cycle 0-2-1-3-4-5-0. Its edge lengths are 325, 437, 398, 319, 149, 248. Thus, Vlado will discard the longest edge (2-1, length 437) and obtain the Hamiltonian path 1-3-4-5-0-2 with total length 1439. The difference 1439 - 920 = 519 is large enough: L/2 is only 500.

  3. 11

    11

    Returns: {1, 11, 11, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  4. 7

    12

    Returns: {1, 12, 12, 12, 5, 12, 1, 12, 12, 12, 4, 1, 12, 12, 4, 1, 12, 12, 1, 12, 1 }

  5. 12

    12

    Returns: {1, 12, 12, 12, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  6. 6

    990

    Returns: {1, 990, 990, 331, 990, 1, 990, 990, 330, 1, 990, 330, 1, 990, 1 }

  7. 11

    602

    Returns: {1, 602, 602, 602, 602, 602, 602, 602, 201, 602, 1, 602, 602, 602, 602, 602, 602, 602, 201, 1, 602, 602, 602, 602, 602, 602, 201, 1, 602, 602, 602, 602, 602, 602, 1, 602, 602, 602, 602, 602, 1, 602, 602, 602, 602, 1, 602, 602, 602, 1, 602, 602, 1, 602, 1 }

  8. 14

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  9. 12

    576

    Returns: {1, 576, 576, 576, 576, 576, 576, 576, 576, 193, 576, 1, 576, 576, 576, 576, 576, 576, 576, 576, 192, 1, 576, 576, 576, 576, 576, 576, 576, 192, 1, 576, 576, 576, 576, 576, 576, 576, 1, 576, 576, 576, 576, 576, 576, 1, 576, 576, 576, 576, 576, 1, 576, 576, 576, 576, 1, 576, 576, 576, 1, 576, 576, 1, 576, 1 }

  10. 7

    801

    Returns: {1, 801, 801, 801, 268, 801, 1, 801, 801, 801, 267, 1, 801, 801, 267, 1, 801, 801, 1, 801, 1 }

  11. 6

    10

    Returns: {1, 10, 10, 4, 10, 1, 10, 10, 4, 1, 10, 3, 1, 10, 1 }

  12. 12

    684

    Returns: {1, 684, 684, 684, 684, 684, 684, 684, 684, 229, 684, 1, 684, 684, 684, 684, 684, 684, 684, 684, 228, 1, 684, 684, 684, 684, 684, 684, 684, 228, 1, 684, 684, 684, 684, 684, 684, 684, 1, 684, 684, 684, 684, 684, 684, 1, 684, 684, 684, 684, 684, 1, 684, 684, 684, 684, 1, 684, 684, 684, 1, 684, 684, 1, 684, 1 }

  13. 11

    233

    Returns: {1, 233, 233, 233, 233, 233, 233, 233, 78, 233, 1, 233, 233, 233, 233, 233, 233, 233, 78, 1, 233, 233, 233, 233, 233, 233, 78, 1, 233, 233, 233, 233, 233, 233, 1, 233, 233, 233, 233, 233, 1, 233, 233, 233, 233, 1, 233, 233, 233, 1, 233, 233, 1, 233, 1 }

  14. 8

    15

    Returns: {1, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 5, 1, 15, 15, 15, 5, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  15. 9

    14

    Returns: {1, 14, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  16. 10

    13

    Returns: {1, 13, 13, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 13, 13, 5, 1, 13, 13, 13, 13, 13, 4, 1, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  17. 10

    975

    Returns: {1, 975, 975, 975, 975, 975, 975, 326, 975, 1, 975, 975, 975, 975, 975, 975, 325, 1, 975, 975, 975, 975, 975, 325, 1, 975, 975, 975, 975, 975, 1, 975, 975, 975, 975, 1, 975, 975, 975, 1, 975, 975, 1, 975, 1 }

  18. 14

    15

    Returns: {1, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  19. 12

    11

    Returns: {1, 11, 11, 11, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  20. 13

    10

    Returns: {1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 4, 1, 10, 10, 10, 10, 10, 10, 10, 10, 3, 1, 10, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  21. 12

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  22. 8

    12

    Returns: {1, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 4, 1, 12, 12, 12, 4, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  23. 9

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  24. 10

    14

    Returns: {1, 14, 14, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  25. 6

    13

    Returns: {1, 13, 13, 5, 13, 1, 13, 13, 5, 1, 13, 4, 1, 13, 1 }

  26. 11

    15

    Returns: {1, 15, 15, 15, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  27. 13

    13

    Returns: {1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 5, 1, 13, 13, 13, 13, 13, 13, 13, 13, 4, 1, 13, 13, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  28. 6

    14

    Returns: {1, 14, 14, 5, 14, 1, 14, 14, 5, 1, 14, 5, 1, 14, 1 }

  29. 12

    245

    Returns: {1, 245, 245, 245, 245, 245, 245, 245, 245, 82, 245, 1, 245, 245, 245, 245, 245, 245, 245, 245, 82, 1, 245, 245, 245, 245, 245, 245, 245, 82, 1, 245, 245, 245, 245, 245, 245, 245, 1, 245, 245, 245, 245, 245, 245, 1, 245, 245, 245, 245, 245, 1, 245, 245, 245, 245, 1, 245, 245, 245, 1, 245, 245, 1, 245, 1 }

  30. 11

    10

    Returns: {1, 10, 10, 10, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 10, 10, 10, 4, 1, 10, 10, 10, 10, 10, 10, 3, 1, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  31. 7

    15

    Returns: {1, 15, 15, 15, 6, 15, 1, 15, 15, 15, 5, 1, 15, 15, 5, 1, 15, 15, 1, 15, 1 }

  32. 12

    13

    Returns: {1, 13, 13, 13, 13, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 13, 13, 13, 13, 5, 1, 13, 13, 13, 13, 13, 13, 13, 4, 1, 13, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  33. 10

    109

    Returns: {1, 109, 109, 109, 109, 109, 109, 37, 109, 1, 109, 109, 109, 109, 109, 109, 37, 1, 109, 109, 109, 109, 109, 36, 1, 109, 109, 109, 109, 109, 1, 109, 109, 109, 109, 1, 109, 109, 109, 1, 109, 109, 1, 109, 1 }

  34. 13

    594

    Returns: {1, 594, 594, 594, 594, 594, 594, 594, 594, 594, 199, 594, 1, 594, 594, 594, 594, 594, 594, 594, 594, 594, 198, 1, 594, 594, 594, 594, 594, 594, 594, 594, 198, 1, 594, 594, 594, 594, 594, 594, 594, 594, 1, 594, 594, 594, 594, 594, 594, 594, 1, 594, 594, 594, 594, 594, 594, 1, 594, 594, 594, 594, 594, 1, 594, 594, 594, 594, 1, 594, 594, 594, 1, 594, 594, 1, 594, 1 }

  35. 11

    625

    Returns: {1, 625, 625, 625, 625, 625, 625, 625, 209, 625, 1, 625, 625, 625, 625, 625, 625, 625, 209, 1, 625, 625, 625, 625, 625, 625, 208, 1, 625, 625, 625, 625, 625, 625, 1, 625, 625, 625, 625, 625, 1, 625, 625, 625, 625, 1, 625, 625, 625, 1, 625, 625, 1, 625, 1 }

  36. 6

    11

    Returns: {1, 11, 11, 4, 11, 1, 11, 11, 4, 1, 11, 4, 1, 11, 1 }

  37. 14

    19

    Returns: {1, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 7, 19, 1, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 7, 1, 19, 19, 19, 19, 19, 19, 19, 19, 19, 6, 1, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 19, 19, 19, 19, 19, 19, 19, 19, 1, 19, 19, 19, 19, 19, 19, 19, 1, 19, 19, 19, 19, 19, 19, 1, 19, 19, 19, 19, 19, 1, 19, 19, 19, 19, 1, 19, 19, 19, 1, 19, 19, 1, 19, 1 }

  38. 12

    530

    Returns: {1, 530, 530, 530, 530, 530, 530, 530, 530, 177, 530, 1, 530, 530, 530, 530, 530, 530, 530, 530, 177, 1, 530, 530, 530, 530, 530, 530, 530, 177, 1, 530, 530, 530, 530, 530, 530, 530, 1, 530, 530, 530, 530, 530, 530, 1, 530, 530, 530, 530, 530, 1, 530, 530, 530, 530, 1, 530, 530, 530, 1, 530, 530, 1, 530, 1 }

  39. 9

    254

    Returns: {1, 254, 254, 254, 254, 254, 85, 254, 1, 254, 254, 254, 254, 254, 85, 1, 254, 254, 254, 254, 85, 1, 254, 254, 254, 254, 1, 254, 254, 254, 1, 254, 254, 1, 254, 1 }

  40. 9

    13

    Returns: {1, 13, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 13, 5, 1, 13, 13, 13, 13, 4, 1, 13, 13, 13, 13, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  41. 11

    273

    Returns: {1, 273, 273, 273, 273, 273, 273, 273, 92, 273, 1, 273, 273, 273, 273, 273, 273, 273, 91, 1, 273, 273, 273, 273, 273, 273, 91, 1, 273, 273, 273, 273, 273, 273, 1, 273, 273, 273, 273, 273, 1, 273, 273, 273, 273, 1, 273, 273, 273, 1, 273, 273, 1, 273, 1 }

  42. 10

    10

    Returns: {1, 10, 10, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 10, 10, 4, 1, 10, 10, 10, 10, 10, 3, 1, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  43. 14

    12

    Returns: {1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  44. 6

    824

    Returns: {1, 824, 824, 275, 824, 1, 824, 824, 275, 1, 824, 275, 1, 824, 1 }

  45. 13

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  46. 14

    405

    Returns: {1, 405, 405, 405, 405, 405, 405, 405, 405, 405, 405, 136, 405, 1, 405, 405, 405, 405, 405, 405, 405, 405, 405, 405, 135, 1, 405, 405, 405, 405, 405, 405, 405, 405, 405, 135, 1, 405, 405, 405, 405, 405, 405, 405, 405, 405, 1, 405, 405, 405, 405, 405, 405, 405, 405, 1, 405, 405, 405, 405, 405, 405, 405, 1, 405, 405, 405, 405, 405, 405, 1, 405, 405, 405, 405, 405, 1, 405, 405, 405, 405, 1, 405, 405, 405, 1, 405, 405, 1, 405, 1 }

  47. 10

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  48. 14

    842

    Returns: {1, 842, 842, 842, 842, 842, 842, 842, 842, 842, 842, 281, 842, 1, 842, 842, 842, 842, 842, 842, 842, 842, 842, 842, 281, 1, 842, 842, 842, 842, 842, 842, 842, 842, 842, 281, 1, 842, 842, 842, 842, 842, 842, 842, 842, 842, 1, 842, 842, 842, 842, 842, 842, 842, 842, 1, 842, 842, 842, 842, 842, 842, 842, 1, 842, 842, 842, 842, 842, 842, 1, 842, 842, 842, 842, 842, 1, 842, 842, 842, 842, 1, 842, 842, 842, 1, 842, 842, 1, 842, 1 }

  49. 8

    13

    Returns: {1, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 5, 1, 13, 13, 13, 4, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  50. 6

    1000

    Returns: {174, 325, 60, 839, 248, 437, 398, 965, 806, 658, 985, 969, 319, 100, 149 }

  51. 14

    377

    Returns: {1, 377, 377, 377, 377, 377, 377, 377, 377, 377, 377, 126, 377, 1, 377, 377, 377, 377, 377, 377, 377, 377, 377, 377, 126, 1, 377, 377, 377, 377, 377, 377, 377, 377, 377, 126, 1, 377, 377, 377, 377, 377, 377, 377, 377, 377, 1, 377, 377, 377, 377, 377, 377, 377, 377, 1, 377, 377, 377, 377, 377, 377, 377, 1, 377, 377, 377, 377, 377, 377, 1, 377, 377, 377, 377, 377, 1, 377, 377, 377, 377, 1, 377, 377, 377, 1, 377, 377, 1, 377, 1 }

  52. 13

    772

    Returns: {1, 772, 772, 772, 772, 772, 772, 772, 772, 772, 258, 772, 1, 772, 772, 772, 772, 772, 772, 772, 772, 772, 258, 1, 772, 772, 772, 772, 772, 772, 772, 772, 257, 1, 772, 772, 772, 772, 772, 772, 772, 772, 1, 772, 772, 772, 772, 772, 772, 772, 1, 772, 772, 772, 772, 772, 772, 1, 772, 772, 772, 772, 772, 1, 772, 772, 772, 772, 1, 772, 772, 772, 1, 772, 772, 1, 772, 1 }

  53. 10

    15

    Returns: {1, 15, 15, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  54. 11

    14

    Returns: {1, 14, 14, 14, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  55. 7

    11

    Returns: {1, 11, 11, 11, 4, 11, 1, 11, 11, 11, 4, 1, 11, 11, 4, 1, 11, 11, 1, 11, 1 }

  56. 9

    44

    Returns: {1, 44, 44, 44, 44, 44, 15, 44, 1, 44, 44, 44, 44, 44, 15, 1, 44, 44, 44, 44, 15, 1, 44, 44, 44, 44, 1, 44, 44, 44, 1, 44, 44, 1, 44, 1 }

  57. 13

    12

    Returns: {1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  58. 9

    545

    Returns: {1, 545, 545, 545, 545, 545, 182, 545, 1, 545, 545, 545, 545, 545, 182, 1, 545, 545, 545, 545, 182, 1, 545, 545, 545, 545, 1, 545, 545, 545, 1, 545, 545, 1, 545, 1 }

  59. 8

    10

    Returns: {1, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 4, 1, 10, 10, 10, 3, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  60. 9

    11

    Returns: {1, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  61. 6

    15

    Returns: {1, 15, 15, 6, 15, 1, 15, 15, 5, 1, 15, 5, 1, 15, 1 }

  62. 11

    13

    Returns: {1, 13, 13, 13, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 13, 13, 13, 5, 1, 13, 13, 13, 13, 13, 13, 4, 1, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  63. 7

    14

    Returns: {1, 14, 14, 14, 5, 14, 1, 14, 14, 14, 5, 1, 14, 14, 5, 1, 14, 14, 1, 14, 1 }

  64. 14

    10

    Returns: {1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 4, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 3, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  65. 12

    14

    Returns: {1, 14, 14, 14, 14, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  66. 13

    15

    Returns: {1, 15, 15, 15, 15, 15, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  67. 11

    581

    Returns: {1, 581, 581, 581, 581, 581, 581, 581, 194, 581, 1, 581, 581, 581, 581, 581, 581, 581, 194, 1, 581, 581, 581, 581, 581, 581, 194, 1, 581, 581, 581, 581, 581, 581, 1, 581, 581, 581, 581, 581, 1, 581, 581, 581, 581, 1, 581, 581, 581, 1, 581, 581, 1, 581, 1 }

  68. 7

    13

    Returns: {1, 13, 13, 13, 5, 13, 1, 13, 13, 13, 5, 1, 13, 13, 4, 1, 13, 13, 1, 13, 1 }

  69. 9

    12

    Returns: {1, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  70. 10

    11

    Returns: {1, 11, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  71. 14

    13

    Returns: {1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 5, 13, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 5, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 4, 1, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 13, 1, 13, 13, 13, 13, 1, 13, 13, 13, 1, 13, 13, 1, 13, 1 }

  72. 14

    393

    Returns: {1, 393, 393, 393, 393, 393, 393, 393, 393, 393, 393, 132, 393, 1, 393, 393, 393, 393, 393, 393, 393, 393, 393, 393, 131, 1, 393, 393, 393, 393, 393, 393, 393, 393, 393, 131, 1, 393, 393, 393, 393, 393, 393, 393, 393, 393, 1, 393, 393, 393, 393, 393, 393, 393, 393, 1, 393, 393, 393, 393, 393, 393, 393, 1, 393, 393, 393, 393, 393, 393, 1, 393, 393, 393, 393, 393, 1, 393, 393, 393, 393, 1, 393, 393, 393, 1, 393, 393, 1, 393, 1 }

  73. 7

    1000

    Returns: {1, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 334, 1, 1000, 1000, 333, 1, 1000, 1000, 1, 1000, 1 }

  74. 8

    14

    Returns: {1, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 5, 1, 14, 14, 14, 5, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  75. 9

    15

    Returns: {1, 15, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  76. 13

    751

    Returns: {1, 751, 751, 751, 751, 751, 751, 751, 751, 751, 251, 751, 1, 751, 751, 751, 751, 751, 751, 751, 751, 751, 251, 1, 751, 751, 751, 751, 751, 751, 751, 751, 250, 1, 751, 751, 751, 751, 751, 751, 751, 751, 1, 751, 751, 751, 751, 751, 751, 751, 1, 751, 751, 751, 751, 751, 751, 1, 751, 751, 751, 751, 751, 1, 751, 751, 751, 751, 1, 751, 751, 751, 1, 751, 751, 1, 751, 1 }

  77. 6

    138

    Returns: {1, 138, 138, 47, 138, 1, 138, 138, 46, 1, 138, 46, 1, 138, 1 }

  78. 10

    12

    Returns: {1, 12, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  79. 7

    10

    Returns: {1, 10, 10, 10, 4, 10, 1, 10, 10, 10, 4, 1, 10, 10, 3, 1, 10, 10, 1, 10, 1 }

  80. 14

    14

    Returns: {1, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  81. 12

    10

    Returns: {1, 10, 10, 10, 10, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 10, 10, 10, 10, 4, 1, 10, 10, 10, 10, 10, 10, 10, 3, 1, 10, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 10, 1, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  82. 11

    591

    Returns: {1, 591, 591, 591, 591, 591, 591, 591, 198, 591, 1, 591, 591, 591, 591, 591, 591, 591, 197, 1, 591, 591, 591, 591, 591, 591, 197, 1, 591, 591, 591, 591, 591, 591, 1, 591, 591, 591, 591, 591, 1, 591, 591, 591, 591, 1, 591, 591, 591, 1, 591, 591, 1, 591, 1 }

  83. 13

    11

    Returns: {1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  84. 11

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1000, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  85. 8

    11

    Returns: {1, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 4, 1, 11, 11, 11, 4, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  86. 9

    10

    Returns: {1, 10, 10, 10, 10, 10, 4, 10, 1, 10, 10, 10, 10, 10, 4, 1, 10, 10, 10, 10, 3, 1, 10, 10, 10, 10, 1, 10, 10, 10, 1, 10, 10, 1, 10, 1 }

  87. 8

    1000

    Returns: {1, 1000, 1000, 1000, 1000, 334, 1000, 1, 1000, 1000, 1000, 1000, 334, 1, 1000, 1000, 1000, 333, 1, 1000, 1000, 1000, 1, 1000, 1000, 1, 1000, 1 }

  88. 13

    990

    Returns: {1, 990, 990, 990, 990, 990, 990, 990, 990, 990, 331, 990, 1, 990, 990, 990, 990, 990, 990, 990, 990, 990, 330, 1, 990, 990, 990, 990, 990, 990, 990, 990, 330, 1, 990, 990, 990, 990, 990, 990, 990, 990, 1, 990, 990, 990, 990, 990, 990, 990, 1, 990, 990, 990, 990, 990, 990, 1, 990, 990, 990, 990, 990, 1, 990, 990, 990, 990, 1, 990, 990, 990, 1, 990, 990, 1, 990, 1 }

  89. 6

    12

    Returns: {1, 12, 12, 5, 12, 1, 12, 12, 4, 1, 12, 4, 1, 12, 1 }

  90. 11

    12

    Returns: {1, 12, 12, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

  91. 14

    11

    Returns: {1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

  92. 12

    15

    Returns: {1, 15, 15, 15, 15, 15, 15, 15, 15, 6, 15, 1, 15, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 15, 5, 1, 15, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 15, 1, 15, 15, 15, 15, 1, 15, 15, 15, 1, 15, 15, 1, 15, 1 }

  93. 11

    74

    Returns: {1, 74, 74, 74, 74, 74, 74, 74, 25, 74, 1, 74, 74, 74, 74, 74, 74, 74, 25, 1, 74, 74, 74, 74, 74, 74, 25, 1, 74, 74, 74, 74, 74, 74, 1, 74, 74, 74, 74, 74, 1, 74, 74, 74, 74, 1, 74, 74, 74, 1, 74, 74, 1, 74, 1 }

  94. 12

    640

    Returns: {1, 640, 640, 640, 640, 640, 640, 640, 640, 214, 640, 1, 640, 640, 640, 640, 640, 640, 640, 640, 214, 1, 640, 640, 640, 640, 640, 640, 640, 213, 1, 640, 640, 640, 640, 640, 640, 640, 1, 640, 640, 640, 640, 640, 640, 1, 640, 640, 640, 640, 640, 1, 640, 640, 640, 640, 1, 640, 640, 640, 1, 640, 640, 1, 640, 1 }

  95. 13

    14

    Returns: {1, 14, 14, 14, 14, 14, 14, 14, 14, 14, 5, 14, 1, 14, 14, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 14, 14, 5, 1, 14, 14, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 14, 1, 14, 14, 14, 14, 1, 14, 14, 14, 1, 14, 14, 1, 14, 1 }

  96. 11

    110

    Returns: {1, 110, 110, 110, 110, 110, 110, 110, 37, 110, 1, 110, 110, 110, 110, 110, 110, 110, 37, 1, 110, 110, 110, 110, 110, 110, 37, 1, 110, 110, 110, 110, 110, 110, 1, 110, 110, 110, 110, 110, 1, 110, 110, 110, 110, 1, 110, 110, 110, 1, 110, 110, 1, 110, 1 }

  97. 9

    959

    Returns: {1, 959, 959, 959, 959, 959, 320, 959, 1, 959, 959, 959, 959, 959, 320, 1, 959, 959, 959, 959, 320, 1, 959, 959, 959, 959, 1, 959, 959, 959, 1, 959, 959, 1, 959, 1 }

  98. 10

    100

    Returns: {1, 100, 100, 100, 100, 100, 100, 34, 100, 1, 100, 100, 100, 100, 100, 100, 34, 1, 100, 100, 100, 100, 100, 33, 1, 100, 100, 100, 100, 100, 1, 100, 100, 100, 100, 1, 100, 100, 100, 1, 100, 100, 1, 100, 1 }

  99. 6

    101

    Returns: {1, 101, 101, 34, 101, 1, 101, 101, 34, 1, 101, 34, 1, 101, 1 }

  100. 13

    999

    Returns: {1, 999, 999, 999, 999, 999, 999, 999, 999, 999, 334, 999, 1, 999, 999, 999, 999, 999, 999, 999, 999, 999, 333, 1, 999, 999, 999, 999, 999, 999, 999, 999, 333, 1, 999, 999, 999, 999, 999, 999, 999, 999, 1, 999, 999, 999, 999, 999, 999, 999, 1, 999, 999, 999, 999, 999, 999, 1, 999, 999, 999, 999, 999, 1, 999, 999, 999, 999, 1, 999, 999, 999, 1, 999, 999, 1, 999, 1 }

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: