Statistics

Problem Statement for "RiverCrossing"

Problem Statement

A carrier boat is initially on the left bank of a river. Cargo becomes available at either side of the river at various times. Each cargo unit must be loaded onto the boat, carried across the river to the opposite side, and unloaded. It takes T units of time to cross the river, and the boat can carry at most units units of cargo at a time. Loading and unloading cargo is instantaneous. The boat can wait at either side of the river and depart at any time. After all the cargo has been transported, it does not matter which side of the river the boat ends up at.

Each element of cargo represents one or more cargo units, ordered in non-decreasing order by the time at which they become available.

The waiting time of a cargo unit is the difference between the time at which it becomes available and the time at which it is loaded onto the boat. The time spent by a cargo unit while it's inside the boat does not count toward its waiting time. For example, if a cargo unit becomes available at time 0 and is loaded onto the boat at time 5, its waiting time is 5 regardless of how much longer the boat waits before departing. Determine a schedule for the boat that minimizes the sum of all the waiting times. Return this minimal sum.

You are given a String[] cargo where each element is formatted as "units time bank" (quotes for clarity only).

  • units is the number of cargo units that become available.
  • time is the time at which they become available.
  • bank is the side of the river at which they become available - either "left" or "right" (quotes for clarity only).
Even though multiple units of cargo may become available at the same time, they do not need to remain together or be loaded onto the boat at the same time.

Definition

Class:
RiverCrossing
Method:
minimalWait
Parameters:
String[], int, int
Returns:
int
Method signature:
int minimalWait(String[] cargo, int units, int T)
(be sure your method is public)

Constraints

  • cargo will contain between 1 and 50 elements, inclusive.
  • units will be between 1 and 50, inclusive.
  • T will be between 1 and 100, inclusive.
  • Each element of cargo will be formatted as "units time bank" (quotes for clarity only).
  • Elements of cargo will be ordered in non-decreasing order of time.
  • In each element of cargo, units will be an integer between 1 and 50, inclusive, with no leading zeroes.
  • In each element of cargo, time will be an integer between 1 and 100, inclusive, with no leading zeroes.
  • In each element of cargo, bank will be either "left" or "right" (quotes for clarity only).
  • The total units of cargo to be transported will be less than or equal to 200.

Examples

  1. {"5 1 right"}

    3

    3

    Returns: 22

    The boat moves as follows: Time 0: The boat departs from the left bank. Time 3: The boat arrives at the right bank, loads 3 units of cargo, and departs. The total waiting time for those 3 units is 3*(3-1)=6. Time 6: The boat arrives at the left bank, unloads its cargo, and departs. Time 9: The boat arrives at the right bank, loads the remaining 2 units of cargo, and departs. The total waiting time for those 2 units is 2*(9-1)=16. Time 12: The boat arrives at the left bank and unloads its cargo. The total waiting time was 6+16=22.

  2. {"5 5 right"}

    3

    3

    Returns: 12

  3. {"1 1 left", "1 1 right", "2 4 left"}

    3

    2

    Returns: 4

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

    50

    10

    Returns: 3188

  5. {"20 1 left", "20 2 left", "20 3 left", "20 4 left", "20 5 left", "20 6 left", "20 7 left", "20 8 left", "20 9 left", "20 10 left"}

    1

    100

    Returns: 3979100

    You always go from right to left with an empty boat.

  6. {"20 1 right", "20 2 left", "20 3 right", "20 4 left", "20 5 right", "20 6 left", "20 7 right", "20 8 left", "20 9 right", "20 10 left"}

    1

    100

    Returns: 1989300

    Coming back with a filled boat reduces the waiting time.

  7. {"5 1 left"}

    1

    100

    Returns: 2000

  8. {"4 15 left", "10 24 left", "3 35 left", "10 47 right", "4 51 right", "10 56 right", "9 65 left"}

    12

    34

    Returns: 1660

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

    20

    10

    Returns: 5620

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

    3

    2

    Returns: 8236

  11. {"4 1 left", "2 2 left", "5 3 right", "1 5 left", "4 12 left", "5 22 left", "5 22 right", "1 23 right", "5 23 left", "3 24 right", "5 25 right", "1 27 left", "5 30 right", "5 32 right", "2 33 right", "5 35 left", "5 36 right", "2 38 left", "1 40 left", "2 41 left", "3 43 left", "5 44 right", "5 44 left", "4 52 left", "5 52 right", "5 57 right", "5 65 right", "5 65 left", "5 66 right", "5 68 right", "5 69 left", "4 70 right", "5 71 left", "5 73 right", "4 76 right", "1 77 left", "5 77 left", "5 78 right", "1 83 right", "5 84 right", "5 85 right", "2 87 left", "5 88 left", "5 90 left", "3 91 right", "5 92 left", "5 93 right", "5 97 right", "5 98 right", "4 100 right"}

    6

    2

    Returns: 554

  12. {"5 1 left", "5 5 right", "3 7 right", "2 8 right", "5 10 left", "4 20 left", "2 23 right", "1 25 left", "5 28 left", "2 31 left", "48 40 right", "5 41 left", "30 51 right", "3 51 right", "5 51 left", "2 56 right", "3 59 left", "5 60 right", "1 64 right", "47 79 right", "5 82 left", "5 88 left", "1 91 left", "5 91 left", "1 96 left"}

    33

    18

    Returns: 8032

  13. {"5 2 right", "4 4 right", "5 5 right", "4 10 right", "5 11 left", "3 12 right", "4 15 right", "5 16 right", "5 19 right", "2 21 left", "3 22 left", "2 25 right", "5 26 left", "5 26 left", "5 36 right", "5 37 right", "5 41 right", "2 43 left", "5 44 left", "4 44 left", "3 44 right", "5 48 right", "5 49 right", "5 50 left", "5 51 right", "3 55 right", "5 60 left", "4 60 left", "2 62 right", "5 63 right", "1 64 right", "5 71 left", "5 74 left", "4 75 left", "2 76 left", "2 77 left", "5 78 left", "5 78 right", "4 78 left", "5 82 right", "4 83 right", "5 83 right", "5 85 left", "5 88 right", "4 90 left", "2 90 right", "5 91 left", "5 91 right", "2 98 left"}

    32

    76

    Returns: 40897

  14. {"1 11 right", "5 11 left", "5 16 left", "3 19 left", "4 24 left", "5 25 right", "5 25 left", "1 27 right", "49 30 right", "5 33 right", "5 34 right", "1 34 right", "5 34 right", "5 34 right", "3 36 right", "5 43 left", "5 44 right", "5 50 right", "5 54 left", "2 54 left", "48 60 left", "2 68 left", "5 69 right", "5 73 right", "5 81 right", "4 86 left", "3 88 left", "4 92 left"}

    14

    1

    Returns: 339

  15. {"1 9 left", "2 14 right", "5 15 left", "3 17 right", "1 21 left", "3 21 right", "5 21 left", "5 26 left", "42 28 left", "5 28 left", "3 30 right", "5 30 right", "1 34 left", "3 35 right", "5 41 right", "5 42 right", "2 44 right", "5 58 left", "4 63 right", "2 64 left", "1 69 right", "47 73 right", "5 74 right", "5 76 right", "5 82 left", "5 83 right", "1 88 left", "5 94 right", "1 94 right", "5 97 left", "5 97 right", "3 98 left", "5 100 left"}

    37

    36

    Returns: 11651

  16. {"1 6 right", "5 8 right", "5 8 right", "1 9 left", "2 14 right", "5 17 left", "49 21 right", "4 24 right", "4 29 left", "1 33 right", "1 34 left", "3 34 left", "2 34 left", "2 35 left", "5 36 left", "5 40 left", "4 45 left", "2 46 right", "5 47 right", "4 50 right", "5 51 right", "3 52 left", "1 52 right", "5 59 right", "3 62 left", "5 64 right", "5 72 right", "5 73 right", "5 75 right", "5 77 right", "4 79 left", "5 82 left", "4 83 left", "15 85 right", "2 90 left", "5 91 right", "5 91 right", "5 95 right", "1 100 right", "2 100 right"}

    27

    85

    Returns: 70969

  17. {"47 1 left", "3 5 left", "5 5 right", "3 8 left", "2 9 right", "46 10 right", "3 10 right", "5 14 right", "2 14 right", "5 16 right", "5 20 right", "5 30 left", "1 39 right", "5 41 right", "4 42 left", "1 42 right", "3 45 left", "1 49 left", "4 51 right", "5 57 left", "5 59 left", "2 64 right", "4 67 left", "5 71 left", "4 77 right", "1 81 right", "5 85 left", "3 85 right", "2 86 right", "4 87 left", "3 89 right", "2 95 left", "5 97 left"}

    28

    31

    Returns: 13886

  18. {"8 1 left", "5 1 right", "3 11 left", "3 18 left", "5 18 left", "5 21 left", "3 27 left", "3 32 left", "4 36 right", "5 38 left", "5 39 left", "48 41 left", "5 42 right", "3 45 right", "5 46 right", "1 48 left", "3 54 right", "5 55 right", "1 56 left", "5 56 left", "5 58 right", "1 58 left", "5 59 left", "4 59 right", "5 59 left", "1 60 left", "5 61 right", "4 62 left", "5 64 left", "1 73 right", "5 75 left", "5 81 right", "4 84 right", "5 84 left", "5 84 right", "5 92 right", "5 93 left", "5 95 right"}

    47

    95

    Returns: 31236

  19. {"1 2 left", "5 3 left", "5 5 right", "46 15 left", "3 17 right", "5 18 right", "2 19 left", "5 19 left", "5 22 left", "2 24 left", "5 26 left", "5 27 right", "1 30 left", "4 30 right", "1 39 right", "1 50 left", "5 53 right", "1 55 left", "1 59 left", "3 63 right", "3 64 left", "1 69 right", "3 69 left", "5 76 left", "3 77 left", "5 77 right", "5 77 right", "5 78 right", "5 79 left", "4 82 left", "1 90 left", "48 93 left", "5 97 right", "1 100 right"}

    15

    2

    Returns: 606

  20. {"46 2 right", "5 3 right", "36 4 left", "3 5 right", "5 6 left", "5 24 right", "2 27 left", "5 28 right", "5 34 right", "5 37 right", "4 43 left", "5 48 left", "5 50 left", "5 51 right", "4 60 left", "5 61 left", "5 69 left", "5 70 left", "5 71 right", "5 71 left", "5 78 right", "5 81 right", "2 84 left", "5 85 right", "2 91 left", "1 98 right", "5 98 left", "5 99 right", "5 100 right"}

    3

    89

    Returns: 585131

  21. {"5 4 right", "1 15 right", "3 16 right", "4 19 right", "4 21 left", "5 29 left", "3 29 right", "5 30 right", "5 33 right", "4 34 right", "5 34 left", "1 38 right", "5 40 right", "5 45 right", "1 46 right", "3 46 left", "5 47 right", "3 57 left", "5 61 left", "2 61 right", "5 64 left", "5 70 right", "5 79 left", "2 79 right", "5 79 right", "4 80 right", "5 83 left", "5 83 right", "5 84 left", "5 85 left", "45 86 left", "4 86 right", "2 87 right", "2 89 left", "5 90 left", "5 92 right", "5 93 left", "5 95 right", "4 99 left", "3 100 right"}

    21

    47

    Returns: 37179

  22. {"5 1 right", "5 2 left", "5 4 left", "1 5 right", "5 8 left", "5 11 left", "5 15 left", "5 16 right", "5 16 right", "5 17 right", "5 19 left", "5 22 right", "3 22 right", "5 23 right", "5 23 right", "1 27 right", "5 29 right", "5 30 left", "1 30 right", "5 31 right", "5 36 left", "5 36 left", "1 37 right", "1 38 right", "4 41 right", "2 44 left", "5 45 left", "5 46 right", "5 47 left", "5 48 left", "1 48 left", "5 52 right", "5 56 right", "3 60 right", "5 61 left", "4 66 left", "5 72 right", "2 74 right", "2 75 right", "2 79 right", "5 83 left", "5 84 left", "4 84 left", "1 87 right", "1 90 right", "5 90 left", "3 95 left", "5 95 right", "5 96 left", "5 97 left"}

    33

    85

    Returns: 38317

  23. {"5 3 left", "5 5 right", "3 9 left", "5 11 left", "2 16 right", "5 17 right", "2 17 left", "5 19 right", "5 21 left", "5 27 right", "47 30 right", "1 31 right", "1 31 left", "3 32 right", "5 33 left", "5 36 left", "5 41 left", "5 42 right", "5 42 right", "4 44 left", "5 50 right", "5 55 left", "1 55 left", "4 58 right", "4 60 left", "4 60 left", "2 60 left", "1 60 right", "5 60 left", "5 63 right", "4 71 left", "5 72 right", "1 72 right", "3 74 right", "4 77 right", "2 78 left", "2 79 right", "2 79 right", "1 81 right", "4 82 left", "1 86 left", "1 87 left", "5 90 left", "5 94 right", "1 95 right"}

    30

    25

    Returns: 11122

  24. {"5 1 right", "4 9 right", "5 13 right", "3 18 left", "1 21 left", "1 25 left", "5 26 left", "2 27 right", "46 28 right", "5 31 right", "3 32 right", "5 36 left", "49 37 left", "1 37 right", "5 39 left", "5 40 left", "5 55 left", "12 58 left", "5 61 left", "1 68 right", "2 69 left", "5 71 left", "1 74 left", "5 74 right", "5 85 left", "3 86 right", "5 92 left", "1 94 left", "5 96 left"}

    4

    95

    Returns: 478439

  25. {"2 3 right", "5 22 right", "5 24 left", "5 26 left", "1 26 left", "5 27 left", "2 28 right", "5 35 right", "5 35 left", "5 37 right", "5 37 right", "5 38 right", "5 39 right", "3 41 left", "5 41 left", "1 44 right", "46 47 left", "5 48 right", "1 51 right", "2 56 right", "5 58 left", "5 58 right", "2 59 left", "1 61 left", "5 61 left", "5 62 right", "2 63 right", "3 63 right", "5 66 left", "5 68 right", "5 69 left", "5 74 left", "5 77 left", "2 77 right", "5 81 right", "3 87 right", "5 91 right", "5 91 left", "3 92 left", "1 95 left", "5 99 right"}

    26

    45

    Returns: 28070

  26. {"5 6 left", "5 11 right", "5 14 right", "3 17 left", "5 24 left", "5 32 left", "5 34 right", "5 35 left", "3 39 left", "44 46 left", "5 52 left", "1 57 right", "5 63 right", "47 65 right", "4 83 right", "2 86 left", "5 90 right", "46 99 right"}

    44

    82

    Returns: 30684

  27. {"3 5 left", "5 9 left", "5 10 left", "5 23 left", "32 24 right", "5 27 right", "5 44 left", "47 45 right", "5 46 right", "5 51 left", "2 55 right", "5 58 right", "1 62 left", "48 62 left", "5 63 left", "5 80 left", "2 81 left", "4 94 left", "5 97 right", "4 97 right", "2 98 right"}

    19

    16

    Returns: 10182

  28. {"2 1 right", "4 1 left", "2 3 right", "4 3 right", "4 5 left", "5 5 right", "1 9 right", "5 14 left", "5 15 left", "5 15 left", "5 17 right", "2 18 left", "5 26 right", "5 28 right", "5 31 left", "5 34 left", "3 37 left", "5 44 left", "1 47 right", "5 50 left", "1 51 left", "5 54 left", "2 55 right", "50 59 left", "5 62 left", "2 66 left", "2 70 right", "5 72 right", "1 75 right", "4 76 right", "3 77 left", "4 77 right", "5 80 left", "5 82 left", "3 86 right", "2 86 left", "5 87 right", "5 87 left", "1 87 right", "5 88 right", "2 92 right", "5 97 left"}

    13

    17

    Returns: 19797

  29. {"4 1 left", "5 7 left", "5 9 left", "1 12 left", "3 14 right", "1 14 right", "4 14 left", "5 20 left", "4 20 left", "5 24 left", "4 27 left", "3 27 right", "49 33 left", "1 41 right", "5 48 left", "1 49 left", "2 56 right", "5 59 right", "5 63 right", "5 64 left", "5 66 left", "5 73 left", "5 77 left", "5 82 right", "5 86 left", "48 86 left", "5 86 right", "5 87 right"}

    23

    89

    Returns: 89382

  30. {"5 2 right", "5 5 right", "5 7 right", "5 7 left", "5 9 left", "5 20 right", "5 21 left", "5 27 left", "4 28 left", "1 31 left", "2 33 right", "5 40 left", "3 47 right", "5 51 left", "5 53 left", "4 53 right", "5 54 left", "5 55 right", "5 55 right", "1 56 right", "5 58 right", "5 62 right", "1 62 right", "2 63 right", "5 68 left", "2 68 left", "2 74 right", "46 77 right", "5 81 left", "5 83 right", "5 83 left", "5 89 left", "5 90 left", "2 92 right", "5 95 right", "5 97 left", "5 99 left", "5 99 left"}

    8

    68

    Returns: 157000

  31. {"2 1 left", "4 3 right", "5 9 right", "5 9 left", "5 16 left", "4 16 right", "5 21 left", "5 24 right", "4 25 right", "5 28 right", "2 32 right", "5 34 right", "5 34 left", "5 41 right", "5 45 left", "48 50 left", "3 53 right", "5 55 left", "6 62 left", "46 66 left", "1 69 left", "5 74 right", "5 88 left", "5 89 left", "5 99 left", "5 99 right"}

    45

    55

    Returns: 21944

  32. {"33 12 left", "49 12 left", "5 25 left", "4 26 right", "5 27 right", "5 31 left", "3 31 right", "47 40 right", "3 44 left", "5 49 left", "5 53 right", "3 55 left", "2 56 right", "5 63 left", "5 65 left", "3 68 right", "5 78 right", "5 92 right", "5 94 left", "2 97 right", "1 98 left"}

    44

    91

    Returns: 28946

  33. {"2 2 left", "5 7 right", "2 8 right", "1 12 left", "2 16 right", "5 17 left", "1 23 left", "50 26 left", "2 27 left", "5 33 right", "5 33 left", "1 38 right", "4 42 right", "5 48 left", "5 52 left", "1 53 left", "5 56 left", "5 57 left", "3 58 right", "4 60 left", "3 60 left", "5 66 left", "5 67 right", "50 68 left", "2 69 left", "5 78 left", "1 80 left", "5 82 left", "5 89 right", "5 93 left", "1 100 left"}

    22

    53

    Returns: 57304

  34. {"2 1 right", "5 2 left", "4 3 left", "2 9 right", "5 11 right", "5 11 right", "5 20 left", "3 22 right", "1 24 left", "5 27 right", "5 27 left", "5 29 right", "1 31 right", "5 35 left", "5 39 left", "2 44 left", "5 44 left", "5 52 left", "3 60 right", "5 61 right", "5 65 left", "5 66 left", "5 70 left", "5 72 right", "1 72 left", "1 73 left", "2 77 left", "2 81 left", "5 82 right", "5 82 right", "5 83 left", "5 85 left", "2 87 left", "4 90 left", "48 92 right", "4 92 left", "1 93 right", "5 94 left", "3 94 left", "4 96 left", "5 99 left"}

    32

    57

    Returns: 25550

  35. {"2 1 right", "5 4 right", "5 5 left", "5 6 right", "4 7 right", "48 10 left", "3 12 left", "5 13 right", "3 14 right", "3 14 left", "2 14 right", "5 14 right", "2 17 right", "5 24 right", "3 26 left", "5 31 right", "1 32 left", "5 33 right", "5 36 right", "5 38 left", "2 38 right", "2 42 right", "5 42 left", "5 47 right", "2 65 right", "4 68 right", "5 69 right", "5 73 left", "4 74 right", "2 77 left", "5 77 left", "5 81 left", "5 81 left", "5 90 right", "4 91 right", "5 93 right", "1 96 right", "5 97 right", "5 99 left", "3 100 right"}

    3

    80

    Returns: 518601

  36. {"3 2 left", "1 5 left", "1 7 left", "5 7 left", "3 9 right", "5 12 right", "5 19 right", "5 22 right", "5 26 right", "4 27 left", "5 29 right", "5 31 left", "5 34 right", "5 36 left", "4 36 left", "3 40 left", "2 41 left", "5 43 right", "4 44 right", "47 45 left", "5 51 right", "5 52 right", "5 59 right", "5 62 left", "5 62 right", "4 63 right", "4 65 right", "5 70 left", "1 78 left", "9 79 right", "2 79 left", "5 81 right", "5 82 right", "5 83 left", "1 95 left", "5 97 right", "3 98 right", "4 98 left"}

    9

    72

    Returns: 144563

  37. {"3 1 left", "5 1 right", "5 5 left", "3 8 left", "3 10 right", "2 11 right", "4 11 left", "5 12 right", "4 12 left", "3 14 left", "34 15 right", "3 16 right", "5 29 left", "5 31 left", "5 32 left", "5 36 right", "5 37 left", "5 38 left", "5 41 right", "4 42 right", "5 42 left", "2 46 right", "5 50 right", "5 50 left", "5 51 right", "3 51 left", "4 53 right", "1 58 right", "3 58 left", "5 59 right", "5 62 left", "5 65 left", "5 65 right", "1 67 left", "5 69 left", "2 84 right", "1 85 right", "2 86 left", "5 87 left", "4 88 right", "1 89 right", "3 91 left", "1 93 left", "5 94 right", "4 94 right"}

    45

    79

    Returns: 27982

  38. {"5 2 right", "2 5 right", "1 5 left", "2 5 right", "5 6 left", "5 6 left", "5 6 right", "5 7 left", "5 7 left", "1 7 left", "5 9 right", "3 10 right", "5 11 right", "2 13 right", "5 23 right", "5 23 left", "2 25 left", "1 26 right", "3 28 left", "5 28 left", "5 30 right", "5 32 left", "5 34 right", "2 34 left", "5 37 right", "4 42 left", "5 44 right", "5 45 left", "5 47 right", "5 51 right", "2 54 right", "5 55 left", "1 56 right", "5 57 right", "2 67 left", "5 68 left", "5 69 right", "5 70 right", "3 72 right", "5 74 right", "5 75 right", "4 75 left", "2 79 left", "5 79 left", "4 81 left", "4 83 right", "2 83 left", "5 83 left", "5 84 right", "5 93 left"}

    4

    13

    Returns: 54781

  39. {"5 1 left", "5 4 left", "1 4 left", "2 12 right", "5 12 left", "5 12 right", "4 23 left", "5 29 left", "5 31 right", "5 33 right", "5 35 left", "5 35 right", "2 38 left", "5 43 left", "2 44 left", "5 45 right", "5 47 right", "1 47 right", "48 48 right", "3 53 left", "5 55 right", "5 55 right", "1 58 left", "5 63 right", "5 67 left", "33 70 left", "3 74 left", "5 74 left", "5 76 left", "5 81 left", "5 84 right"}

    42

    25

    Returns: 6652

  40. {"37 5 right", "5 5 right", "5 6 right", "5 7 left", "2 11 right", "3 17 left", "5 17 right", "5 17 left", "5 18 left", "1 20 right", "5 22 right", "5 24 left", "5 26 left", "5 27 left", "3 32 left", "5 35 left", "4 39 right", "5 45 right", "5 54 left", "5 55 right", "5 60 right", "5 76 right", "3 83 left", "5 85 right", "4 86 right", "5 91 right", "2 96 left", "48 98 left", "3 99 left"}

    36

    78

    Returns: 32672

  41. {"1 8 right", "1 19 left", "5 35 right", "1 38 right", "2 38 right", "5 40 left", "5 40 left", "5 42 right", "46 44 left", "5 46 left", "3 57 right", "50 58 right", "5 67 left", "3 82 right", "5 90 right", "5 95 right", "5 95 right", "48 97 right"}

    19

    24

    Returns: 22063

  42. {"4 2 left", "5 6 right", "3 9 left", "5 13 right", "2 20 right", "1 21 right", "5 21 left", "5 21 left", "5 25 right", "5 27 left", "2 28 left", "5 34 left", "5 34 left", "5 38 right", "5 41 right", "2 48 left", "1 49 right", "5 50 left", "5 51 right", "5 52 right", "1 54 left", "5 55 left", "2 59 left", "1 61 right", "5 61 right", "2 66 right", "4 66 left", "5 67 right", "5 69 left", "1 70 left", "5 70 right", "5 76 left", "3 80 right", "5 83 right", "5 90 left", "5 90 left", "50 91 left", "1 96 right", "5 96 left", "5 97 left"}

    34

    54

    Returns: 22607

  43. {"5 1 right", "5 5 left", "5 12 left", "5 13 left", "5 16 left", "5 19 right", "4 19 right", "5 28 left", "5 29 left", "2 30 right", "47 33 left", "5 34 left", "1 36 left", "2 39 left", "5 41 left", "5 42 left", "5 42 left", "2 45 right", "3 47 left", "2 48 right", "5 49 left", "2 60 left", "5 72 left", "2 77 left", "4 77 right", "2 81 right", "4 83 right", "48 90 right", "5 97 left"}

    3

    5

    Returns: 25516

  44. {"5 7 left", "5 9 right", "5 13 right", "4 13 right", "1 22 left", "5 22 left", "5 24 left", "3 35 left", "5 36 right", "5 36 right", "5 36 left", "5 40 right", "5 44 right", "5 45 right", "2 54 left", "5 54 right", "5 55 left", "5 56 left", "5 58 left", "3 61 left", "5 62 right", "5 63 left", "3 64 left", "5 64 right", "2 66 left", "5 67 right", "3 67 right", "5 68 right", "48 76 right", "5 77 right", "2 77 left", "1 83 right", "5 85 left", "5 93 right", "3 95 left", "5 95 right", "3 96 right", "2 96 left"}

    29

    8

    Returns: 1574

  45. {"2 4 left", "5 8 left", "5 9 left", "4 12 right", "5 13 right", "1 13 right", "5 15 left", "5 15 left", "5 17 right", "1 24 right", "5 27 left", "1 28 left", "5 28 left", "2 31 right", "4 34 left", "5 36 left", "4 39 right", "5 41 right", "5 42 left", "5 43 right", "5 44 left", "5 47 right", "5 49 right", "5 49 right", "1 49 right", "5 53 right", "1 53 left", "5 55 right", "5 60 right", "3 62 left", "5 62 right", "2 62 right", "5 69 left", "5 73 left", "3 75 right", "3 84 left", "45 85 left", "1 95 right", "5 96 left", "2 96 left", "5 99 right"}

    32

    74

    Returns: 34826

  46. {"5 2 left", "5 3 left", "5 5 right", "5 14 right", "2 20 left", "5 20 left", "4 21 right", "5 33 left", "5 37 right", "5 37 right", "5 38 left", "5 40 right", "4 41 right", "5 46 right", "3 47 right", "5 48 right", "5 48 left", "1 56 right", "5 56 right", "5 59 left", "4 60 left", "5 60 right", "2 62 right", "5 62 left", "5 64 left", "2 66 right", "4 68 left", "2 71 right", "50 73 right", "1 77 right", "3 79 left", "4 82 left", "1 83 right", "3 85 right", "5 95 right", "5 97 left", "4 97 left", "3 98 right", "3 100 left"}

    26

    21

    Returns: 9298

  47. {"46 3 left", "5 3 right", "3 10 right", "5 10 left", "5 12 right", "2 15 right", "4 17 right", "2 21 right", "5 22 right", "2 22 left", "3 23 left", "4 24 right", "4 24 left", "5 24 right", "5 26 right", "5 30 left", "5 33 left", "5 40 right", "5 42 left", "3 44 left", "5 45 right", "1 46 right", "5 47 left", "3 53 right", "5 55 right", "5 64 left", "5 72 left", "5 73 right", "5 74 right", "2 76 right", "4 77 left", "2 81 right", "5 84 left", "3 85 left", "5 88 right", "5 88 left", "5 94 left", "4 94 left", "3 97 right"}

    31

    1

    Returns: 49

  48. {"4 4 right", "4 4 right", "1 9 right", "3 10 right", "5 12 right", "5 13 right", "1 18 right", "1 20 left", "5 22 left", "5 29 right", "5 33 left", "5 34 right", "5 36 right", "5 37 left", "5 38 right", "5 39 left", "5 41 right", "5 43 left", "5 45 right", "2 45 left", "5 47 right", "5 47 right", "2 47 right", "2 53 left", "5 55 right", "5 61 right", "2 61 right", "4 62 left", "1 67 left", "1 68 left", "5 71 left", "3 72 right", "2 72 left", "5 73 right", "3 73 left", "3 76 right", "4 77 right", "5 79 left", "5 79 right", "5 82 left", "2 83 left", "5 84 left", "5 84 right", "2 84 right", "5 85 left", "5 86 left", "5 89 left", "4 92 right", "5 95 right", "2 100 right"}

    17

    80

    Returns: 81967

  49. {"1 3 right", "3 7 left", "2 11 right", "4 13 left", "1 17 left", "42 21 left", "5 26 left", "2 26 left", "3 27 left", "2 28 right", "1 34 left", "5 35 right", "50 37 right", "3 41 right", "5 43 left", "1 45 left", "5 47 right", "3 49 left", "3 52 left", "5 54 right", "2 56 right", "5 61 left", "5 62 left", "4 63 left", "5 66 left", "3 69 right", "2 72 right", "2 77 right", "5 85 left", "5 87 right", "5 88 right", "2 89 right", "3 91 left", "5 97 right", "1 100 left"}

    25

    17

    Returns: 7323

  50. {"5 1 right", "1 4 right", "4 5 right", "50 6 right", "3 18 left", "48 21 right", "5 37 left", "5 40 right", "1 40 left", "5 43 left", "5 43 right", "5 55 right", "4 57 left", "3 60 left", "3 65 left", "1 65 left", "14 67 left", "5 70 left", "4 72 left", "5 76 right", "5 78 left", "3 83 left", "4 88 right", "5 89 right", "2 90 right", "5 91 right"}

    32

    18

    Returns: 9077

  51. {"5 9 right", "5 15 left", "5 17 left", "47 23 right", "2 27 right", "1 33 right", "5 37 left", "5 37 right", "5 37 right", "5 40 right", "5 46 left", "5 48 right", "1 49 right", "3 49 left", "5 51 left", "5 60 left", "3 61 left", "5 63 right", "5 63 right", "5 68 left", "5 70 left", "50 72 right", "3 80 left", "5 82 right", "4 83 right", "3 85 left", "3 86 left"}

    10

    38

    Returns: 82933

  52. {"1 2 right", "50 5 left", "5 7 right", "3 9 right", "5 16 left", "5 18 right", "1 20 right", "2 20 right", "4 25 right", "4 27 right", "1 37 right", "4 40 left", "5 40 right", "5 44 left", "2 48 right", "5 48 left", "5 49 right", "5 53 left", "5 54 left", "4 55 left", "4 63 right", "2 64 right", "5 67 left", "4 67 left", "1 70 left", "2 71 left", "4 72 left", "1 75 left", "1 78 left", "5 85 left", "4 85 left", "5 86 left", "3 87 left", "5 88 left", "5 90 right", "4 91 left", "2 91 left", "1 92 right", "1 94 right", "5 96 left", "5 98 left", "5 99 right", "5 99 left"}

    5

    99

    Returns: 450189

  53. {"49 3 right", "1 4 left", "4 5 left", "3 7 left", "49 8 right", "2 11 left", "4 12 left", "2 14 left", "5 19 left", "5 24 left", "5 25 right", "48 30 right", "2 31 right", "4 43 left", "5 46 left", "2 48 left", "5 91 left", "5 91 right"}

    31

    53

    Returns: 44203

  54. {"5 3 left", "5 4 right", "5 6 left", "5 10 right", "1 12 left", "5 12 left", "5 14 left", "3 15 left", "2 18 right", "5 19 right", "5 21 right", "1 24 right", "3 27 left", "1 31 right", "5 31 left", "3 35 right", "1 35 right", "2 36 right", "3 36 right", "2 37 left", "4 39 left", "5 42 right", "5 44 right", "4 45 left", "3 46 left", "5 51 right", "3 52 left", "5 53 right", "1 55 right", "4 56 right", "48 56 right", "5 58 left", "5 61 right", "5 68 right", "5 69 left", "5 83 right", "5 84 left", "5 88 left", "1 88 right", "2 92 right", "1 92 left", "1 93 right", "3 96 left", "2 99 right", "1 100 left"}

    32

    79

    Returns: 43827

  55. {"5 3 right", "5 5 right", "5 8 left", "5 8 left", "29 10 right", "5 11 right", "5 12 left", "1 13 left", "2 20 left", "5 31 right", "1 35 right", "4 41 left", "1 45 left", "5 50 right", "5 59 left", "5 60 left", "1 64 left", "2 70 right", "5 75 right", "50 77 right", "5 78 left", "1 86 right", "48 86 left"}

    3

    1

    Returns: 2087

  56. {"3 1 right", "1 1 right", "3 3 left", "4 9 left", "1 11 left", "4 15 left", "5 17 left", "5 18 left", "1 22 right", "5 24 left", "5 25 left", "5 27 right", "5 27 right", "5 28 left", "5 32 left", "5 32 right", "4 33 left", "5 37 left", "1 45 left", "5 47 right", "5 50 left", "5 54 right", "3 56 left", "2 66 right", "5 69 left", "2 70 left", "5 70 left", "5 71 right", "1 72 left", "5 74 left", "5 74 right", "3 82 right", "5 82 left", "5 85 left", "5 86 left", "5 89 right", "1 91 right", "5 95 left", "1 95 right", "1 99 left", "49 100 left"}

    10

    42

    Returns: 87881

  57. {"5 2 right", "4 7 left", "5 10 left", "5 13 left", "42 30 right", "4 32 right", "5 39 right", "3 44 left", "1 50 left", "5 51 left", "4 52 right", "5 59 right", "5 60 right", "5 62 left", "3 65 left", "5 70 right", "5 72 left", "5 75 left", "3 77 right", "5 78 right", "3 80 right", "50 82 left", "5 89 right", "3 89 left", "5 90 left", "5 94 left", "5 100 right"}

    4

    29

    Returns: 131957

  58. {"5 3 right", "5 3 right", "4 6 right", "5 6 left", "1 7 left", "2 8 right", "5 10 right", "5 11 right", "47 15 left", "5 17 left", "5 20 left", "5 23 left", "1 25 left", "4 26 right", "5 27 left", "2 32 right", "5 35 right", "5 50 left", "3 52 left", "1 54 left", "5 56 right", "5 60 right", "2 70 right", "4 71 right", "2 75 left", "2 76 right", "2 79 right", "1 80 left", "49 89 left", "5 97 left", "3 98 right"}

    39

    90

    Returns: 36743

  59. {"49 6 left", "5 7 right", "5 14 left", "3 16 right", "48 24 left", "3 24 left", "36 34 left", "5 40 right", "1 40 right", "4 49 right", "5 56 right", "3 57 left", "5 59 right", "2 64 left", "5 66 left", "1 72 left", "5 74 right", "5 84 right", "5 96 right", "5 99 left"}

    48

    94

    Returns: 33274

  60. {"5 2 right", "2 12 left", "2 12 left", "5 18 right", "5 21 left", "5 22 right", "1 22 right", "1 27 right", "5 32 right", "5 34 left", "5 43 right", "5 43 right", "1 44 right", "5 49 right", "4 52 left", "46 54 left", "5 56 left", "4 60 right", "5 66 right", "5 69 left", "5 75 left", "5 75 right", "5 78 left", "5 78 right", "5 80 left", "4 82 left", "5 83 right", "5 85 left", "5 86 left", "5 89 right", "5 91 left", "5 92 left", "2 95 left", "5 95 right", "5 97 left", "5 97 left", "3 97 left"}

    22

    66

    Returns: 54957

  61. {"13 20 left", "13 30 right", "1 30 left", "1 30 right", "30 33 right", "34 40 left", "35 41 right", "50 99 left" }

    13

    100

    Returns: 106595

  62. {"13 20 left", "13 30 right", "1 30 left", "1 30 right", "30 33 right", "34 40 left", "35 41 right", "50 99 left" }

    13

    100

    Returns: 106595

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: