Statistics

Problem Statement for "AdaptiveRouting"

Problem Statement

A network consists of routers and links. Each link directly connects two routers. Links can transfer data in both directions, and have unlimited bandwidth but limited transfer speed. We know how many time units it takes for each link to transmit a packet from one end to the other.

The routers know the layout of the network and relay data packets so that the packet reaches its destination in the shortest possible time. Suppose a router wants to send a packet to some other router. The source router will calculate the shortest path to the destination router and send the packet to the first router on that path. That router will then proceed in the same way, and so on until the packet reaches its destination. If a router can send to more than one neighboring router and have the packet delivered in the same minimal time, it will send to the lowest-numbered of those routers.

When a link fails, the two routers it connected know about it immediately, but the other routers do not. The two routers generate control packets containing information about the failed link and distribute the control packets to all their immediate neighbors (over links that haven't failed themselves). When a router receives a control packet, it updates its internal layout of the network and passes copies of the control packet to its neighbors.

If a router receives more than one packet at the same time, it will analyze all the incoming packets before generating any outgoing traffic.

At time index 0, a number of links failed and a single data packet was sent from router A to router B. You are given the initial layout of the network as a String[], the list of failed links as a int[] and the integers A and B.

The routers are labelled with integers between 1 and 99. Links in layout will be formatted as "ROUTER1 ROUTER2 TIME", meaning that the link connects routers labelled ROUTER1 and ROUTER2 and it takes TIME time units for packets to be sent over it. A value of x in failed means that the link described by element x of layout has failed (index is 0-based).

Return an int, the number of time units needed for the data packet to reach router B. If the packet can never reach the destination, return -1.

Definition

Class:
AdaptiveRouting
Method:
deliveryTime
Parameters:
String[], int[], int, int
Returns:
int
Method signature:
int deliveryTime(String[] layout, int[] failed, int A, int B)
(be sure your method is public)

Notes

  • There can be more than one link connecting two routers.

Constraints

  • layout will contain between 0 and 50 elements, inclusive.
  • Each element of layout will be formatted as "ROUTER1 ROUTER2 TIME" (quotes for clarity).
  • ROUTER1 and ROUTER2 in each element of layout will be distinct integers between 1 and 99, inclusive, without leading zeroes.
  • TIME in each element of layout will be an integer between 1 and 10^7, inclusive, without leading zeroes.
  • Each element of failed will be between 0 and n-1, inclusive, where n is the number of elements in layout.
  • failed will not contain duplicate elements.
  • A and B will be between 1 and 99, inclusive.
  • A and B will be different.

Examples

  1. { "1 2 1", "2 3 1", "2 5 1", "3 4 1", "4 6 1", "5 6 1" }

    { }

    1

    6

    Returns: 3

    With no failed links, the packet gets sent by the shortest route (1 -> 2 -> 5 -> 6).

  2. { "1 2 1", "2 3 1", "2 5 1", "3 4 1", "4 6 1", "5 6 1" }

    { 5 }

    1

    6

    Returns: 4

    The link between routers 5 and 6 has failed. After 1 time unit, the data packet gets to router 2. At that same moment word of the failed link gets to router 2 from router 5, so router 2 sends the packet through routers 3 and 4.

  3. { "1 2 1", "1 2 22" }

    { 0 }

    1

    2

    Returns: 22

    The primary link has failed so the packet is sent through the auxiliary (slow) link.

  4. { "1 2 1", "1 2 22" }

    { 0 }

    2

    1

    Returns: 22

  5. { "1 2 1", "1 3 2", "3 4 1", "4 2 5" }

    { }

    4

    1

    Returns: 3

  6. { "4 3 100", "2 4 3", "3 2 1", "2 5 1", "4 1 2", "5 4 1" }

    { 2, 5 }

    1

    3

    Returns: 108

  7. { "4 3 100", "2 4 3", "3 2 1", "2 5 1", "4 1 3", "5 4 1" }

    { 2, 5 }

    1

    3

    Returns: 103

  8. { "1 2 1", "2 4 2", "4 3 1", "1 5 7", "5 3 1", "2 6 22", "6 3 1", "1 7 67", "7 3 1", "2 8 202", "8 3 1", "1 9 607", "9 3 1", "2 10 1822", "10 3 1", "1 11 5467", "11 3 1", "2 12 16402", "12 3 1", "1 13 49207", "13 3 1", "2 14 147622", "14 3 1", "1 15 442867", "15 3 1", "2 16 1328602", "16 3 1", "1 17 3985807", "17 3 1" }

    { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 }

    1

    3

    Returns: 7971614

  9. { "88 33 1", "33 78 2", "78 63 1", "88 16 7", "16 63 1", "33 26 22", "26 63 1", "88 48 67", "48 63 1", "33 47 202", "47 63 1", "88 53 607", "53 63 1", "33 39 1822", "39 63 1", "88 15 5467", "15 63 1", "33 71 16402", "71 63 1", "88 11 49207", "11 63 1", "33 51 147622", "51 63 1", "88 46 442867", "46 63 1", "33 28 1328602", "28 63 1", "88 25 3985807", "25 63 1" }

    { 12, 22, 14, 2, 20, 10, 16, 26, 24, 18, 8, 6, 4 }

    88

    63

    Returns: 7971614

  10. { "1 2 1", "2 4 1", "4 3 1", "1 5 2", "5 3 2", "2 6 3", "6 3 3", "1 7 4", "7 3 4", "2 8 5", "8 3 5", "1 9 6", "9 3 6", "2 10 7", "10 3 7", "1 11 8", "11 3 8", "2 12 9", "12 3 9", "1 13 10", "13 3 10", "2 14 11", "14 3 11", "1 15 12", "15 3 12", "2 16 13", "16 3 13", "1 17 14", "17 3 14", "2 18 15", "18 3 15", "1 19 16", "19 3 16", "2 20 17", "20 3 17", "1 21 18", "21 3 18", "2 22 19", "22 3 19", "1 23 20", "23 3 20", "2 24 21", "24 3 21", "1 25 22", "25 3 22", "2 26 23", "26 3 23", "1 27 24", "27 3 24" }

    { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46 }

    1

    3

    Returns: 72

  11. { "78 69 1", "69 19 1", "19 88 1", "78 24 2", "24 88 2", "69 39 3", "39 88 3", "78 33 4", "33 88 4", "69 46 5", "46 88 5", "78 64 6", "64 88 6", "69 26 7", "26 88 7", "78 16 8", "16 88 8", "69 80 9", "80 88 9", "78 71 10", "71 88 10", "69 28 11", "28 88 11", "78 29 12", "29 88 12", "69 27 13", "27 88 13", "78 91 14", "91 88 14", "69 30 15", "30 88 15", "78 31 16", "31 88 16", "69 36 17", "36 88 17", "78 21 18", "21 88 18", "69 18 19", "18 88 19", "78 43 20", "43 88 20", "69 62 21", "62 88 21", "78 75 22", "75 88 22", "69 38 23", "38 88 23", "78 95 24", "95 88 24" }

    { 14, 44, 12, 18, 38, 46, 2, 34, 22, 26, 8, 6, 24, 42, 40, 32, 4, 16, 10, 20, 36, 30, 28 }

    78

    88

    Returns: 72

  12. { "10 12 5", "10 11 2", "11 12 3" }

    { 2 }

    10

    12

    Returns: 9

  13. { "89 16 2712037", "76 73 4347065", "89 51 706012", "76 17 4520844", "76 10 8186111", "89 96 6599891", "69 89 9491545", "76 34 2281882", "76 94 2086116", "69 76 508454", "73 89 5652934", "26 89 9500739", "76 29 7350749", "76 6 6628382", "15 89 6216159", "76 4 5688060", "26 76 499260", "76 98 7910782", "54 76 4704784", "4 89 4311939", "15 76 3783840", "89 34 7718117", "10 89 1813888", "76 71 2177663", "76 97 3600874", "3 89 5882747", "89 54 5295215", "89 6 3371617", "52 89 8146249", "89 94 7913883", "76 51 9293987", "76 84 5991057", "39 76 193852", "67 76 8982778", "89 71 7822336", "96 76 3400108", "89 29 2649250", "89 17 5479155", "67 89 1017221", "3 76 4117253", "76 52 1853750", "97 89 6399125", "89 39 9806147", "89 61 6127048", "61 76 3872951", "76 16 7287962", "89 84 4008942", "89 98 2089217", "48 76 366666", "48 89 9633333" }

    { 30, 12, 48, 44, 4, 9, 17, 40, 33, 7, 18, 15, 32, 31, 45, 23, 8, 1, 3, 35, 13, 24, 20, 16 }

    89

    76

    Returns: 37625356

  14. { "96 4 10000000", "67 24 10000000", "74 16 10000000", "31 44 10000000", "88 3 10000000", "16 94 10000000", "78 56 10000000", "5 67 10000000", "73 63 10000000", "40 98 10000000", "44 40 10000000", "12 82 10000000", "69 45 10000000", "29 27 10000000", "19 4 10000000", "63 54 10000000", "39 1 10000000", "91 99 10000000", "59 19 10000000", "82 21 10000000", "35 69 10000000", "33 54 10000000", "51 1 10000000", "74 51 10000000", "6 18 10000000", "7 99 10000000", "12 81 10000000", "38 3 10000000", "94 27 10000000", "28 56 10000000", "91 98 10000000", "28 76 10000000", "32 6 10000000", "10 2 10000000", "24 53 10000000", "7 88 10000000", "21 45 10000000", "29 60 10000000", "81 31 10000000", "34 32 10000000", "73 18 10000000", "22 10 10000000", "22 5 10000000", "64 96 10000000", "76 75 10000000", "75 35 10000000", "78 64 10000000", "34 53 10000000", "2 39 10000000", "60 38 10000000" }

    {}

    33

    59

    Returns: 500000000

  15. { "25 13 9237820", "41 71 9190180", "6 19 9065015", "40 46 9349921", "64 8 9337212", "78 54 9554221", "28 10 9359610", "18 34 9817152", "30 25 9881006", "34 92 9535232", "1 40 9122143", "9 63 9474686", "18 75 9645994", "66 93 9398206", "92 74 9778452", "70 69 9105598", "13 23 9969508", "46 96 9646688", "15 61 9765776", "89 43 9424260", "57 43 9361122", "94 1 9362185", "85 73 9631284", "83 15 9521312", "14 9 9346430", "63 94 9203841", "89 8 9543312", "77 41 9454199", "59 11 9842974", "78 84 9013900", "33 70 9296640", "72 85 9260549", "51 83 9667928", "14 28 9094402", "71 10 9254058", "81 74 9436814", "31 66 9376696", "77 81 9995719", "64 31 9058407", "91 69 9744249", "30 60 9212629", "57 91 9365746", "60 19 9827792", "73 93 9021129", "27 51 9650940", "33 27 9618333", "96 11 9755535", "23 72 9795260", "75 6 9564381", "54 61 9155778" }

    {}

    84

    59

    Returns: 473092224

  16. { "93 29 3", "29 35 2", "60 56 4", "40 56 5", "81 40 3", "40 56 1", "81 40 3", "40 93 4", "60 40 2", "29 81 4", "29 35 2", "93 72 4", "29 40 4", "93 35 2", "72 35 3", "56 81 1", "60 40 3", "60 81 2", "93 35 4", "60 72 4", "72 93 2", "56 35 3", "81 72 4", "72 40 1", "29 35 3", "56 35 2", "72 29 5", "60 29 4", "40 35 1", "60 93 5", "40 56 3", "40 56 1", "56 35 3", "56 72 1", "60 29 4", "60 29 1", "60 93 1" }

    { 36, 4, 31, 27, 35, 14, 7, 34, 28, 15, 23, 16, 33, 5, 3, 10, 29, 25, 20, 32, 18, 17, 21, 8, 19, 11 }

    60

    35

    Returns: 13

  17. { "50 33 3", "50 33 2", "97 96 4", "51 20 7", "20 33 2", "36 51 5", "94 96 4", "41 50 6", "96 33 5", "41 20 5", "41 33 7", "47 33 5", "36 94 5", "51 50 4", "36 97 6", "94 47 7", "97 94 3", "96 20 3", "97 51 3", "41 20 5", "47 33 4", "94 97 4", "47 33 6", "94 51 5", "41 47 2", "41 36 5", "41 36 3", "50 33 3", "51 33 2", "51 50 5", "51 94 3", "20 51 1", "51 94 7", "36 51 4", "41 94 1", "41 47 5", "50 97 7", "96 47 5", "50 51 4", "97 33 2", "20 97 7", "41 96 7", "94 33 6", "41 36 7", "94 36 7", "20 94 1", "47 50 4", "51 33 7", "41 50 5", "41 51 3" }

    { 14, 36, 48, 46, 41, 24, 19, 5, 35, 15, 40, 49, 16, 22, 2, 43, 3, 8, 21, 47, 1, 26, 20, 34, 9, 10, 32, 31, 30, 23, 29, 45, 44, 4, 33, 42, 17, 18, 7, 13 }

    41

    33

    Returns: 24

  18. { "96 25 10", "37 70 3", "25 73 8", "37 25 3", "70 25 10", "37 25 2", "96 73 4", "70 27 1", "25 73 1", "37 73 2", "30 27 8", "27 70 10", "27 37 9", "27 73 5", "30 25 10", "70 27 5", "30 25 10", "27 96 10", "96 73 2", "30 70 6", "30 37 5", "30 27 2", "27 37 7", "25 27 10", "37 25 10", "25 96 2", "30 96 9", "30 27 3", "30 96 8", "96 37 5", "25 73 10", "27 73 2", "30 37 9", "25 73 1", "96 73 2", "25 96 6" }

    { 30, 29, 6, 11, 23, 32, 12, 0, 24, 7, 8, 31, 27, 13, 25, 33, 21, 14, 10, 26, 9, 34, 4, 18, 35, 3, 22 }

    30

    73

    Returns: 15

  19. { "8 30 7", "39 62 6", "62 99 8", "8 99 8", "4 62 3", "8 99 9", "39 8 2", "30 99 10", "38 8 1", "38 30 2", "39 8 1", "39 8 10", "62 99 4", "39 38 6", "39 30 6", "62 30 4", "62 38 6", "8 99 8", "30 99 3", "30 38 9", "39 62 3", "38 99 4", "4 8 5", "30 99 8", "39 4 1", "38 99 1", "4 38 5", "8 30 7", "4 62 2", "8 4 1", "38 8 4", "39 4 8", "39 4 7", "30 38 5" }

    { 5, 6, 9, 20, 1, 3, 11, 18, 7, 30, 25, 10, 14, 17, 4, 27, 8, 2, 26, 12, 13, 28, 31 }

    39

    99

    Returns: 17

  20. { "28 25 3", "2 84 3", "84 25 4", "84 10 1", "2 28 3", "25 84 7", "24 10 4", "2 25 10", "84 24 5", "24 48 4", "2 84 10", "48 10 8", "25 10 1", "2 28 4", "48 10 8", "25 10 6", "2 24 10", "28 48 5" }

    { 4, 3, 7, 15, 11, 17, 9, 5 }

    2

    10

    Returns: 8

  21. { "64 26 1", "85 86 3", "66 26 9", "64 58 5", "26 86 4", "64 66 8", "85 13 7", "26 64 6", "13 58 6", "85 13 9", "26 64 8", "66 58 4", "85 13 10", "13 86 4", "13 58 3", "13 66 6", "85 64 8", "66 58 2", "86 64 4", "85 66 8", "86 13 4", "13 66 8", "86 26 4", "64 13 3", "66 58 10" }

    { 22, 17, 12, 14, 10, 18, 15, 0, 21, 9, 7, 20, 13, 8, 3, 16 }

    85

    58

    Returns: 22

  22. { "15 96 6", "68 20 10", "96 89 5", "15 96 4", "16 15 2", "96 68 5", "16 68 2", "16 68 1", "96 56 3", "68 89 5", "16 96 2", "96 89 8", "20 89 2", "15 96 5", "68 15 5", "96 89 6", "16 15 2", "56 89 5", "16 96 7" }

    { 15, 2, 16, 9, 8, 18, 12, 6, 10, 5, 14 }

    16

    89

    Returns: 16

  23. { "53 21 6", "53 21 4", "9 85 4", "9 90 7", "53 90 1", "21 9 7", "85 7 5", "90 47 7", "85 9 3", "53 85 5", "7 47 9", "53 7 9", "7 47 1", "21 47 6", "90 47 2" }

    { 14, 9, 7, 8, 0, 3 }

    53

    47

    Returns: 12

  24. { "65 37 24", "37 2 66", "65 37 32", "65 46 97", "65 3 52", "37 3 66", "65 77 50", "3 56 99", "77 3 100", "3 2 39", "46 3 75", "56 46 79", "46 2 83", "3 77 73", "3 2 60", "77 2 90" }

    { 10, 4, 0, 3, 8, 15, 12, 1, 13, 9, 7, 2 }

    65

    2

    Returns: -1

  25. {"31 23 9878071", "10 42 4117507", "4 18 2065843", "33 12 3238504"}

    {}

    40

    45

    Returns: -1

  26. {"31 23 9878071", "10 42 4117507", "4 18 2065843", "33 12 3238504"}

    {}

    45

    40

    Returns: -1

  27. { }

    { }

    42

    11

    Returns: -1

  28. { "39 45 2", "45 2 1", "39 2 1", "21 39 1", "45 93 1", "39 93 1", "21 93 2", "21 93 2", "93 2 1", "45 2 2", "93 45 2", "39 2 1", "39 2 1", "93 39 1", "93 45 1", "93 2 2", "39 45 1", "21 45 1", "21 45 2", "93 2 1", "45 2 1", "21 93 2", "93 39 2", "21 39 2", "39 2 1", "39 2 2", "45 2 2", "21 39 2", "39 2 1", "45 39 2", "39 2 1", "45 39 1", "45 2 1", "45 2 2", "21 39 2", "21 2 2", "21 45 1", "45 2 1", "21 45 1", "21 39 2", "21 93 2", "21 45 2", "45 2 1", "93 39 2", "21 93 2", "39 45 2", "21 45 2", "21 45 2", "45 39 2", "21 93 2" }

    { 28, 10, 33, 4, 34, 24, 18, 25, 40, 49, 22, 21, 3, 41, 12, 35, 42, 30, 45, 23, 31, 15, 16, 29, 0, 26, 6, 13, 32, 37, 5, 46, 9, 47, 8, 2, 39, 1, 44, 20, 43, 48, 19, 36 }

    21

    2

    Returns: 5

  29. { "31 6 2", "31 7 2", "68 14 2", "6 14 2", "31 14 2", "6 7 2", "6 14 1", "68 14 2", "31 7 2", "31 68 2", "31 68 1", "68 14 1", "31 6 2", "7 14 2", "7 6 2", "31 68 1", "68 6 2", "31 68 1", "68 14 1", "31 6 2", "31 7 1", "68 7 1", "7 68 2", "6 14 2", "7 68 2", "68 14 1", "31 6 1", "31 68 1", "31 7 2", "31 6 1", "68 14 2", "31 6 1", "7 14 2", "31 68 1", "68 14 1", "31 6 2", "7 14 1", "6 14 1", "31 6 2", "6 14 2", "68 14 2", "6 68 1", "68 14 2", "68 14 2", "6 68 2", "31 6 2", "6 14 1", "31 68 1", "6 68 1", "6 14 1" }

    { 32, 4, 5, 42, 40, 28, 38, 47, 22, 33, 13, 35, 39, 27, 1, 49, 20, 24, 41, 8, 30, 34, 45, 18, 17, 11, 23, 25, 31, 10, 36, 44, 26, 16, 9, 48, 43, 29, 37, 2, 3, 7, 6 }

    31

    14

    Returns: 5

  30. { "42 13 2", "40 65 1", "74 13 2", "42 65 2", "13 65 2", "70 13 3", "13 70 3", "70 13 3", "13 70 3", "42 70 2", "74 42 4", "74 13 1", "42 70 3", "40 42 4", "70 65 4", "42 65 1", "74 70 4", "74 42 2", "13 40 1", "70 65 2", "74 70 2", "13 65 3", "42 13 1", "42 70 3", "40 42 4", "40 13 4", "70 65 4", "70 65 1", "40 65 2", "13 40 4", "70 40 2", "42 40 1", "42 40 1", "40 42 1", "74 42 3", "13 70 1", "70 40 2", "40 42 2", "74 40 3", "13 42 4", "70 40 4", "70 13 1", "13 40 2", "42 13 4", "40 70 4", "40 42 1", "13 40 3", "74 70 4", "74 42 3", "40 13 3" }

    { 23, 49, 12, 40, 1, 19, 22, 18, 30, 2, 15, 41 }

    74

    65

    Returns: 3

  31. { "67 89 7296239", "89 72 459301", "48 89 5755260", "48 28 2515915", "83 51 6418458", "98 28 8553543", "51 28 882253", "83 72 4728434", "72 51 8383240", "72 48 3494514", "83 72 7208883", "89 72 5768855", "93 48 5845714", "51 28 9477065", "48 98 4440474", "11 89 4139245", "93 83 497954", "67 11 1722203", "89 28 1898454", "93 28 8911384", "98 83 3902570", "98 51 7948509", "89 48 8929149", "93 98 572568", "83 98 256717", "67 89 286533", "67 51 7736947", "48 51 8647924", "48 83 639910", "98 72 9934980", "51 93 2769346", "89 98 7232699", "72 11 9815462", "72 51 7839659", "67 11 562709", "83 48 8322295", "72 93 8281824", "51 28 4790501", "89 48 7350092", "51 28 3624640", "67 93 795232", "67 98 6982681", "11 28 5640262", "98 89 3933550", "51 83 3519047", "89 93 3992076", "67 89 6950195", "11 83 3304677", "67 89 8651760" }

    { }

    67

    28

    Returns: 2184987

  32. { "54 50 2409926", "31 65 7479424", "53 38 4446937", "45 38 553495", "31 9 1882356", "38 50 4320324", "9 37 3504150", "91 31 444720", "37 46 2544457", "31 9 6755655", "35 38 4488135", "50 54 5599710", "9 37 673757", "9 20 7231481", "35 9 5280780", "9 45 278426", "35 31 3070805", "37 54 1740198", "55 12 6919299", "55 9 2630249", "35 77 8869480", "9 91 5932381", "20 91 4381963", "87 12 8621809", "29 37 2290488", "12 53 4524663", "29 53 9314942", "9 65 6942944", "50 29 6209286", "55 31 8925157", "53 50 787748", "54 87 6004764", "91 50 4374436", "77 29 2679003", "46 36 6303880", "53 65 1236273", "91 56 8084457", "35 46 7162053", "20 55 401308", "37 65 60261", "12 91 4293899", "77 55 1129382", "46 9 3291116", "56 53 5728253", "38 9 2475185", "35 55 2136026", "50 65 894466", "36 77 1721702", "38 20 594114", "50 65 8554491" }

    { 31, 18, 19, 39, 9 }

    35

    65

    Returns: 8346238

  33. { "96 82 5157858", "42 20 4142359", "81 79 7113975", "81 82 2240765", "94 31 5212450", "30 94 8721765", "31 39 7531559", "48 1 5330351", "97 95 9639568", "56 68 6888038", "50 48 3966208", "20 35 2393698", "35 70 2190322", "24 31 6049312", "74 57 8443117", "98 88 1291112", "56 17 3054902", "67 96 9891184", "26 94 8687133", "55 72 7155317", "79 42 6499018", "15 50 5099636", "95 38 4571056", "70 90 1394083", "17 87 6204873", "82 11 6663482", "87 30 4145843", "90 26 9673616", "94 78 5912559", "82 55 5206196", "38 54 1490153", "78 23 2764182", "79 24 2893828", "97 22 4703623", "57 26 5349478", "67 56 5060674", "26 15 9436225", "31 67 7857723", "81 74 501859", "72 97 2839173", "94 67 8923696", "23 39 7754935", "87 39 4893659", "54 94 9918970", "22 98 7153769", "11 97 9996047", "68 87 9826460", "76 79 3827225", "88 76 2318447", "1 56 8157346" }

    { 1, 45, 36, 43, 44, 34, 12, 32, 2, 48, 4, 14, 42, 6, 22, 26, 40, 23, 24, 25, 0, 41, 16, 38, 27, 21, 20, 10, 47, 37, 11, 3, 28, 13, 29, 7, 39, 8, 17, 49, 18, 15, 46, 31, 9, 33 }

    81

    39

    Returns: -1

  34. { "77 14 7548575", "36 1 8321746", "62 51 15425", "45 10 5978295", "10 94 5343425", "90 42 6777381", "36 69 7064760", "69 77 2153687", "43 39 9913148", "97 21 2766872", "30 29 5468463", "42 77 2946134", "38 16 1436927", "68 43 5646059", "4 27 4225570", "32 4 1444090", "36 30 7531938", "53 94 4467886", "35 61 1527630", "98 68 4068406", "21 38 9005142", "1 80 2240116", "21 75 2742563", "68 32 6796447", "36 90 1918093", "78 96 9839047", "42 62 9231129", "16 75 8743277", "14 53 7723070", "51 98 4199050", "80 75 9845164", "75 89 2127042", "96 20 8364793", "42 60 8910974", "89 35 3800071", "62 78 6627169", "36 62 800837", "27 56 7346334", "90 94 4312139", "29 42 1605909", "75 68 942242", "39 86 1577070", "77 45 8573696", "20 21 3790065", "61 90 2462009", "56 94 7576719", "72 97 4186525", "60 72 6000615", "75 94 6481481", "86 42 8124485" }

    { 34, 19, 3, 36, 0, 6, 42, 22, 38, 30, 47, 32, 2, 21, 18, 33, 10, 27, 40, 25, 7, 23, 46, 15, 45, 41, 31, 8, 9, 14, 39, 5, 12, 29, 17, 11, 28, 44, 26, 43, 1, 35, 48, 37, 16, 20 }

    36

    94

    Returns: -1

  35. { "80 30 2337576", "99 62 4247946", "91 50 1506971", "76 14 405783", "43 52 4276004", "67 11 3846080", "30 45 677018", "14 53 8532632", "9 51 2461237", "51 11 5799403", "15 98 425200", "76 15 4524236", "56 20 8470749", "32 19 4245564", "26 83 310084", "83 98 9540413", "19 43 6114040", "97 84 3751690", "69 53 948995", "84 98 7949223", "91 32 345553", "23 80 828835", "27 18 3866770", "58 9 1386273", "2 56 6809841", "96 27 2230241", "87 26 8463422", "18 38 1914419", "11 97 6019129", "53 41 7163937", "47 30 8671001", "14 39 8022758", "62 23 6726074", "39 47 1877948", "11 99 4110802", "41 2 3503383", "45 67 6522077", "52 14 3775048", "23 87 3602461", "43 76 3217204", "50 96 8789253", "38 43 1019790", "53 92 630568", "92 93 2550133", "30 69 8065758", "96 76 6703481", "20 96 8862847", "91 58 3615628", "93 23 5684726" }

    { 36, 26, 43 }

    91

    98

    Returns: 18871797

  36. { "71 69 179406", "97 45 2325941", "78 26 8920617", "2 41 2135480", "1 17 3237606", "91 74 9079691", "13 77 2693773", "8 64 857711", "49 45 8376620", "26 2 910640", "53 80 251734", "48 13 2237401", "43 29 2122984", "74 71 1956558", "95 48 5990466", "90 84 9893456", "33 61 9198805", "22 97 3199335", "61 52 7524521", "70 88 3238446", "40 22 8012532", "56 64 3272298", "69 1 7905445", "29 76 8396070", "98 44 2058076", "21 17 8945381", "52 78 6249363", "26 45 977136", "60 33 2893889", "80 20 3682485", "17 95 4982482", "17 37 5183108", "90 43 2691461", "37 40 8278497", "8 98 8280139", "8 17 4313537", "76 34 1412261", "77 56 6957818", "3 90 9689237", "84 49 4046098", "73 60 8759089", "41 70 2502239", "20 3 107215", "64 21 1659063", "88 3 3147311", "64 26 3346342", "17 90 894666", "44 91 5192447", "3 73 2080174", "34 53 9497484" }

    { 42, 10, 29, 16, 37, 22, 27, 47, 20, 25, 15, 13, 17, 5, 2, 0, 21, 33, 34, 49, 31, 9, 48, 30, 8, 32 }

    8

    45

    Returns: -1

  37. { "54 39 5810459", "92 49 2651698", "44 74 1888801", "57 26 8536412", "47 67 9270252", "26 24 7462386", "63 44 4028464", "31 64 9214470", "69 29 923626", "62 42 6060742", "5 32 4245366", "50 48 270934", "47 12 3350961", "49 48 7390691", "54 84 4171413", "32 74 1861869", "44 55 4209174", "76 44 4425317", "94 57 9683285", "13 48 4097299", "84 77 6288947", "67 32 1701941", "17 38 2886404", "77 92 7548767", "9 5 4326620", "1 80 9373207", "32 54 9237717", "29 54 7711386", "4 62 9452569", "12 4 5748213", "39 31 3111077", "74 69 1671199", "45 1 5311867", "24 36 6981313", "38 48 112551", "47 63 4077041", "47 9 8091227", "80 76 1615032", "42 17 7547555", "74 87 7485898", "55 5 8681317", "12 50 6551725", "36 12 4725310", "64 94 9241945", "87 13 72902", "5 45 8824616" }

    { 24, 42, 18, 23, 40, 2, 9, 20, 22, 15, 30, 7, 43, 11, 4, 28, 5, 19, 29, 35, 34, 16, 36, 1, 6, 10, 38, 0, 44, 17, 14, 26 }

    47

    48

    Returns: -1

  38. { "77 85 6674025", "28 31 8913959", "75 79 1550116", "89 88 9953189", "38 73 2930429", "73 49 7823838", "20 69 1142880", "71 77 6425330", "85 28 8643837", "63 35 594086", "59 87 3970395", "95 47 8897541", "85 97 1145054", "50 49 8401422", "17 24 9152981", "45 29 6380839", "49 26 6946680", "35 89 5880326", "90 71 4823556", "29 80 6628405", "47 44 5436880", "26 40 811062", "11 63 3437112", "60 45 498217", "90 20 5765632", "99 50 804571", "39 17 1514412", "49 39 7625621", "80 57 204719", "94 60 3849825", "38 93 9843802", "33 64 2969847", "42 59 9689105", "88 75 3548784", "56 6 6213944", "64 31 670328", "69 98 2379226", "96 85 8637733", "44 96 2063601", "87 31 1324792", "90 94 6928503", "40 56 5927343", "6 33 3785697", "79 38 2472857", "24 11 4626724", "97 42 5526784", "98 38 810610", "93 95 1555540", "57 99 9415316" }

    { 46, 8, 18, 17, 29, 1, 48, 21, 41, 47 }

    90

    31

    Returns: -1

  39. { "37 68 9031040", "3 4 7362753", "16 2 3652141", "71 32 5089207", "84 14 5736737", "4 18 6364283", "80 84 7034972", "74 77 7739365", "83 44 616328", "3 95 9285573", "96 95 9557901", "24 62 9713014", "56 81 1356435", "95 24 7183026", "3 18 2337032", "2 8 6171016", "58 40 7111864", "8 81 8736348", "87 58 7655930", "32 24 1214628", "68 83 2181134", "23 88 2083485", "12 71 6745362", "30 2 7800517", "54 56 3356514", "86 12 4689605", "1 23 1140112", "90 92 5278603", "14 94 5736633", "53 50 3991780", "18 57 2001548", "18 80 9978512", "57 96 273827", "66 54 9808159", "44 16 3960414", "95 87 3582958", "80 36 6446154", "62 37 2917287", "36 73 2395573", "77 30 3679657", "92 53 1163746", "40 86 3943494", "24 80 4914354", "73 81 3425069", "88 74 9148895", "2 66 8000792", "94 90 2203964", "50 1 5367309" }

    { 5, 37, 36, 41, 12, 46, 25, 31, 40 }

    3

    81

    Returns: -1

  40. { "19 80 9513717", "13 30 2855305", "14 19 9781309", "94 32 7243335", "80 3 3331212", "59 35 6221911", "5 6 4324395", "32 45 6375522", "50 72 2901348", "23 30 3947740", "46 15 9384768", "72 63 158892", "81 93 5068336", "3 92 1412325", "46 60 3963763", "35 68 4756137", "92 33 9507492", "21 77 5021744", "63 49 5877253", "77 80 6040293", "31 81 6979725", "74 92 7534202", "49 89 9444169", "33 30 728571", "45 13 6865405", "77 92 1284424", "80 74 8263600", "45 33 623417", "88 5 5092896", "46 31 5239432", "92 83 1785640", "68 77 336248", "34 88 4054918", "6 51 7764144", "33 23 6460515", "83 59 838312", "93 34 9231446", "89 45 8925046", "23 21 2643374", "73 23 4097302", "51 42 2336670", "46 68 390274", "16 94 618871", "42 73 6124023", "92 30 1249191", "56 50 4737286", "68 56 8960673", "60 14 7837056", "15 16 5229559" }

    { 28, 3, 16, 29, 12, 40, 44, 19, 27 }

    46

    30

    Returns: 14908228

  41. { "19 10 8812994", "71 63 5963655", "8 24 280674", "35 57 7121831", "98 34 6671707", "69 19 295079", "56 74 7283889", "17 12 9374802", "63 88 5745838", "88 83 7004306", "98 72 6663176", "34 96 2701943", "24 35 2929576", "33 25 4062753", "17 86 8928162", "96 8 199554", "25 89 895963", "72 69 8475584", "82 65 6811791", "58 41 8874418", "86 12 2962289", "74 22 6357361", "66 81 4561033", "98 69 968318", "98 66 6583065", "22 17 2137576", "89 75 58698", "72 87 1514193", "87 9 5764972", "18 95 5339268", "95 16 4833437", "9 18 4492906", "50 28 742821", "65 71 3774631", "28 56 8631787", "67 58 2488359", "75 82 9776984", "57 87 9206297", "87 12 2350954", "24 17 9541198", "83 24 5357744", "16 36 8133503", "10 12 8257331", "36 33 5740640", "81 72 7641136", "41 50 3237528", "69 67 3599891" }

    { 12, 43, 38, 36, 18, 31, 10, 5 }

    98

    12

    Returns: 47657682

  42. { "12 69 218098", "79 37 4512343", "80 7 7636752", "95 97 1588550", "82 23 8867568", "96 79 7097994", "39 66 5282361", "66 27 9442083", "48 70 5941070", "25 47 639689", "60 49 3503466", "41 94 7924210", "78 54 4625808", "69 85 7020252", "70 77 5564301", "31 11 416544", "23 95 6842226", "7 96 9659698", "37 34 7518549", "59 42 9343213", "77 39 7636113", "47 48 3900626", "88 92 8717249", "94 59 9288200", "99 22 1003248", "97 41 252177", "65 60 6450673", "27 67 3322951", "34 2 663770", "83 76 9430178", "22 82 2392408", "2 78 6726440", "15 83 1210729", "85 99 9605217", "86 25 6257356", "42 73 6491725", "46 88 2777328", "9 61 9811754", "54 46 8644290", "67 72 11560", "72 65 2352228", "76 51 9382194", "73 89 7219837", "11 80 6115212", "71 15 5940259", "49 29 1870037", "29 9 2530337", "89 86 3683531", "51 12 5862037", "61 31 4638704" }

    {17, 4, 35, 47, 10, 5, 2, 3 }

    71

    92

    Returns: -1

  43. { "68 86 9937222", "34 58 8194313", "18 34 5544152", "84 55 2948075", "23 41 5465998", "85 29 3005481", "17 68 6065502", "86 72 8032125", "2 13 3346311", "96 81 2685663", "94 46 7967521", "26 6 1918120", "6 84 7386183", "29 21 275141", "56 20 7100801", "41 82 7130256", "3 43 635050", "72 70 346068", "54 69 3358348", "82 74 7682461", "69 56 1433623", "77 91 5601349", "43 49 4201662", "12 96 480544", "81 54 6401003", "52 76 1885045", "25 23 8498228", "70 57 6074827", "91 22 5121314", "19 99 6938932", "13 14 5626247", "7 77 5369609", "57 85 5584293", "16 17 8590497", "45 32 8804497", "1 88 4876750", "20 52 6314420", "46 83 2127440", "99 7 7749426", "21 26 4022678", "58 3 9288133", "32 25 5254648", "49 94 2244016", "83 10 8935495", "76 1 2181948", "88 19 261632", "55 45 4804879", "10 16 7606977", "14 12 9178221", "22 18 3595869" }

    { }

    2

    74

    Returns: 258078993

  44. { "32 70 8375644", "73 68 6064569", "90 22 2679098", "27 94 2543583", "76 70 1114227", "24 75 649272", "85 2 9685417", "65 36 6500408", "41 63 1979373", "38 73 469720", "25 38 6738663", "63 10 6109092", "36 22 9567591", "65 25 4514950", "2 70 3273907", "78 90 3576171", "67 85 255428", "84 47 9634457", "10 32 2793768", "22 41 4418554", "65 84 2164967", "28 56 8910195", "9 70 5405710", "48 93 8865091", "47 51 7398701", "75 70 7824331", "77 54 9257393", "54 4 709168", "51 13 2076011", "65 79 6366035", "33 51 9193637", "61 4 1604148", "95 76 26955", "19 61 9213137", "51 25 3703986", "94 78 5127141", "30 27 8064328", "13 30 85873", "68 95 5412247", "4 67 1999743", "56 48 1789968", "79 19 7108862", "22 33 7920348", "93 62 1614147", "4 24 7173353", "62 77 4000427", "65 28 2534940", "25 9 7110905" }

    { 40, 16, 33, 26, 21, 30, 23, 42, 1, 10, 4, 25, 47 }

    65

    70

    Returns: 61506400

  45. { "79 24 5358329", "84 1 9116216", "96 84 9553659", "18 65 7087796", "70 78 6188380", "38 31 2959385", "4 26 2860775", "26 70 9018646", "50 53 3518121", "37 19 4052705", "48 62 8920197", "62 76 1288538", "76 11 1816512", "1 23 8166241", "59 97 9549980", "41 12 2959101", "65 20 1693304", "87 79 4931614", "78 10 1671757", "73 4 1168765", "79 65 7206134", "40 82 6534851", "65 23 7771927", "89 82 7590182", "19 50 891575", "43 40 7501656", "97 37 2094019", "45 96 701360", "31 87 7749855", "11 79 5547344", "36 14 3870406", "12 78 4535967", "24 59 3950365", "89 82 631051", "23 43 6857651", "70 87 4172422", "78 26 5980245", "87 45 2061912", "20 70 9585207", "53 41 3619568", "6 48 598982", "10 89 1289921", "73 36 1828861", "16 18 3920871", "73 41 2508986", "14 16 8366798", "41 89 1280572", "23 6 1124496", "26 38 1037078" }

    { 24, 38, 2, 46, 40, 16, 9, 14, 12, 19, 28, 27, 10, 20, 18, 33 }

    73

    82

    Returns: 86125685

  46. { "61 91 8000605", "80 2 1573972", "32 12 6200163", "48 40 6269872", "58 26 7215437", "64 61 3381211", "2 44 8071941", "2 94 972179", "42 38 954652", "25 67 6066813", "32 87 9552505", "25 77 7950657", "74 44 5145438", "4 94 5383307", "62 58 5320651", "24 20 732008", "60 70 4804296", "77 83 3120068", "92 44 8946141", "92 2 3975097", "51 92 4785000", "71 25 9550262", "19 58 4524244", "98 80 9698805", "58 44 1605416", "33 21 9510550", "12 51 3048455", "21 82 9527822", "91 62 7996723", "32 43 8979622", "32 33 4970945", "83 48 6566221", "26 42 2476631", "42 74 6229215", "32 25 9397904", "40 63 5296653", "43 42 1953088", "63 19 9447211", "38 98 284293", "87 24 8026415", "94 60 4478848", "48 92 9404865", "70 71 308389", "20 64 5105372", "82 4 6519413", "75 48 9691508", "94 29 5607165", "29 75 6589912", "67 44 7982017" }

    { 24, 12, 6, 18 }

    32

    44

    Returns: 57607236

  47. { "35 72 8280285", "17 42 3157159", "29 63 5147048", "66 17 4025507", "23 90 453740", "42 16 3404617", "18 63 2823828", "56 86 2520016", "61 15 8315045", "66 40 9328904", "77 63 27308", "10 80 6301863", "28 4 7150983", "47 77 8080188", "40 18 711826", "25 35 4639300", "99 56 4777332", "86 68 9125272", "85 68 7511941", "56 46 3772802", "49 27 5761671", "15 47 355633", "72 63 2895546", "75 99 1039736", "80 89 195818", "46 66 3807472", "82 29 5507097", "89 49 3458256", "90 63 5019071", "10 75 2537088", "36 2 8426484", "32 85 4472149", "77 23 700582", "10 36 2886834", "74 66 2923053", "4 50 3525961", "2 25 384771", "27 18 7893656", "18 82 3302538", "10 32 5997398", "50 1 1444690", "1 25 3348150", "25 77 9435993", "10 74 2752946", "68 61 6107507", "68 56 6528708", "16 28 9855139" }

    { 6, 2, 10, 28 }

    10

    63

    Returns: 57523026

  48. { "1 2 10000000", "2 3 10000000", "3 4 10000000", "4 5 10000000", "5 6 10000000", "6 7 10000000", "7 8 10000000", "8 9 10000000", "9 10 10000000", "10 11 10000000", "11 12 10000000", "12 13 10000000", "13 14 10000000", "14 15 10000000", "15 16 10000000", "16 17 10000000", "17 18 10000000", "18 19 10000000", "19 20 10000000", "20 21 10000000", "21 22 10000000", "22 23 10000000", "23 24 10000000", "24 25 10000000", "25 26 10000000", "26 27 10000000", "27 28 10000000", "28 29 10000000", "29 30 10000000", "30 31 10000000", "31 32 10000000", "32 33 10000000", "33 34 10000000", "34 35 10000000", "35 36 10000000", "36 37 10000000", "37 38 10000000", "38 39 10000000", "39 40 10000000", "40 41 10000000", "41 42 10000000", "42 43 10000000", "43 44 10000000", "44 45 10000000", "45 46 10000000", "46 47 10000000", "47 48 10000000", "48 49 10000000", "49 50 10000000", "50 1 10000000"}

    {1}

    1

    3

    Returns: 500000000

  49. { "1 2 9999999", "2 3 10000000", "3 4 10000000", "4 5 10000000", "5 6 10000000", "6 7 10000000", "7 8 10000000", "8 9 10000000", "9 10 10000000", "10 11 10000000", "11 12 10000000", "12 13 10000000", "13 14 10000000", "14 15 10000000", "15 16 10000000", "16 17 10000000", "17 18 10000000", "18 19 10000000", "19 20 10000000", "20 21 10000000", "21 22 10000000", "22 23 10000000", "23 24 10000000", "24 25 10000000", "25 26 10000000", "26 27 10000000", "27 28 10000000", "28 29 10000000", "29 30 10000000", "30 31 10000000", "31 32 10000000", "32 33 10000000", "33 34 10000000", "34 35 10000000", "35 36 10000000", "36 37 10000000", "37 38 10000000", "38 39 10000000", "39 40 10000000", "40 41 10000000", "41 42 10000000", "42 43 10000000", "43 44 10000000", "44 45 10000000", "45 46 10000000", "46 47 10000000", "47 48 10000000", "48 49 10000000", "49 50 10000000", "50 1 10000000"}

    {2}

    1

    4

    Returns: 509999998

  50. {"10 12 5", "10 11 2", "11 12 3" }

    {2 }

    10

    12

    Returns: 9

  51. {"53 21 6", "53 21 4", "9 85 4", "9 90 7", "53 90 1", "21 9 7", "85 7 5", "90 47 7", "85 9 3", "53 85 5", "7 47 9", "53 7 9", "7 47 1", "21 47 6", "90 47 2" }

    {14, 9, 7, 8, 0, 3 }

    53

    47

    Returns: 12

  52. {"1 2 1", "1 2 22" }

    {0 }

    1

    2

    Returns: 22

  53. {"65 37 24", "37 2 66", "65 37 32", "65 46 97", "65 3 52", "37 3 66", "65 77 50", "3 56 99", "77 3 100", "3 2 39", "46 3 75", "56 46 79", "46 2 83", "3 77 73", "3 2 60", "77 2 90" }

    {10, 4, 0, 3, 8, 15, 12, 1, 13, 9, 7, 2 }

    65

    2

    Returns: -1

  54. {"3 4 20", "2 3 10", "1 2 30", "1 4 100" }

    {0 }

    1

    4

    Returns: 160

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: