Statistics

Problem Statement for "FarmvilleDiv2"

Problem Statement

Farmer John recently found out about a popular online farming game.

There are n types of plants in the game. The types are numbered 0 through n-1. At the beginning of the game, Farmer John is given one seed of each plant type.

There is a single plot of land. At any time the plot can only contain at most one plant. Whenever the plot is empty, Farmer John can plant one of the seeds. Once a seed of type i is planted, it takes time[i] seconds until it grows into a fully developed plant. When that happens, Farmer John will harvest the plant and the plot will become empty again. Planting a seed and harvesting a plant happens instanteously.

Farmer John also has budget coins. He can spend these coins to make his plants grow faster. For each i, Farmer John may pay cost[i] coins to reduce time[i] by 1. Farmer John may pay for the same plant multiple times, each time decreasing its growing time by 1. Obviously, the growing time cannot be reduced below 0.

You are given the int[]s time and cost with n elements each, and the int budget. Determine and return the minimum amount of time in which Farmer John can grow a single plant of each type.

Definition

Class:
FarmvilleDiv2
Method:
minTime
Parameters:
int[], int[], int
Returns:
int
Method signature:
int minTime(int[] time, int[] cost, int budget)
(be sure your method is public)

Notes

  • The value of n is not given as a separate argument. Instead, you can determine it as the number of elements in time.

Constraints

  • n will be between 1 and 50, inclusive.
  • time,cost will have exactly n elements.
  • Each element of time,cost will be between 1 and 100, inclusive.
  • budget will be between 1 and 5,000, inclusive.

Examples

  1. {100}

    {1}

    26

    Returns: 74

    In this case, we have a single plant that takes 100 seconds to grow. We can reduce the time it takes to grow by 1 second at a cost of 1 coin. Since we have 26 coins, we can use all our coins to reduce the time it takes the plant to grow to only 74 seconds.

  2. {100}

    {1}

    101

    Returns: 0

  3. {2,1}

    {1,1}

    3

    Returns: 0

    Here we have two plants. Without payments, plant 0 will grow in 2 seconds and plant 1 will grow in 1 second. We have a budget of 3 coins. We can pay 1+1 to decrease the growing time of plant 0 from 2 to 0. We can then pay 1 to decrease the growing time of plant 1 from 1 to 0.

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

    {5,4,3,2,1}

    15

    Returns: 6

  5. {100,100,100,100,100,100,100,100,100,100}

    {2,4,6,8,10,1,3,5,7,9}

    5000

    Returns: 50

  6. {30,40,20,10}

    {10,20,30,40}

    5

    Returns: 100

  7. {69,97,16,11,34,29,99,1,29,53,10,48,10,85,32,68,91,63,6,7,17,30,30,75,31,29,22,61,48,18,53,45,37,93,52,67,45,13,74}

    {64,59,84,9,88,11,74,38,75,86,6,56,78,71,57,68,61,23,76,60,45,2,54,15,79,28,92,33,48,64,58,54,70,32,87,38,64,6,38}

    4472

    Returns: 1424

  8. {8,52,61,14,83,46,46,58,47,53,16,51,32,57,28,70,73,66,99,29,98,43,12,63,14,27,82,27,94,96,50,59,72,39,49,74,76,100,66,80,6}

    {89,71,64,84,74,21,29,34,55,95,72,72,55,42,50,1,81,41,13,93,81,60,80,40,63,53,6,53,62,51,93,8,88,48,20,85,62,13,99,3,14}

    138

    Returns: 2124

  9. {41,10,86,22}

    {100,50,71,80}

    3259

    Returns: 111

  10. {67,78,12}

    {95,1,76}

    3513

    Returns: 41

  11. {68,85,6,23,40,74,42,39,38,77,94,54,42,42,33,80,8}

    {39,72,72,15,70,7,6,38,66,99,73,69,28,10,35,45,69}

    3303

    Returns: 606

  12. {51,7,79,12,48}

    {97,13,41,58,88}

    4276

    Returns: 97

  13. {33,85,88,54,54,85,69,68,45,81,78,9,63,89,33,91,17,34,38,77,8,79,53,10,51,19,22}

    {79,39,4,35,21,66,26,64,63,96,30,39,51,70,100,55,48,60,45,27,12,69,16,16,88,82,98}

    1533

    Returns: 1271

  14. {35,86,36,68,60,53,73,25,25,34,69,8,61,2,43,50,8,16,100,52,70,1,29,42,26,77,43,27,52,83,41,76,32,46,91,50,29,79,18}

    {34,31,27,98,54,50,54,81,35,45,6,14,94,35,33,10,89,14,86,42,3,48,97,98,99,79,30,53,82,10,86,50,73,68,80,73,52,50,33}

    4380

    Returns: 1447

  15. {28,18,2,62,15,89,48,32,70,11,99,18,43,17,44,95,19,86,19,19,69,46,82,61,54,83,6,35,37,79,36,65,10,34,95,84,33,4,38}

    {66,9,87,5,82,27,59,83,12,62,10,37,56,52,51,12,74,1,1,35,8,45,41,72,85,58,3,93,24,32,33,20,64,93,17,9,85,26,42}

    4491

    Returns: 1209

  16. {11,14,41,42,18,6,58,16,86,14,41,85,56,23,73,40,64,62,39,40,45,3,62,50,89,23}

    {7,11,91,32,94,32,90,87,14,23,33,29,91,84,57,66,19,73,94,72,53,68,39,53,4,88}

    3606

    Returns: 814

  17. {21,48,15}

    {77,24,36}

    920

    Returns: 46

  18. {46,100,9,50,5,2,43,52,95,61,48,88,34,59,20,2,27,54,43,2,34,25,59,76,69,75,89}

    {64,26,90,34,57,15,81,5,30,80,14,23,99,97,49,56,76,1,66,10,98,69,72,26,20,69,61}

    1009

    Returns: 1111

  19. {44,10,9,95,9,20,86,34,14,75,65,79,31,6,30,22,7,53,93,14,37,69,19,38,30,83,57,53,88,31,22,43,29,22,90,25,53,69,82,81,35}

    {24,50,35,5,46,35,6,12,61,5,85,45,5,31,26,97,5,31,59,12,100,10,50,50,18,18,46,55,85,69,98,55,14,9,22,84,80,35,21,42,5}

    4472

    Returns: 1307

  20. {17,91,12,88,24,37,20,26,7,60,57,33,56,87,46,14,18,13,82,33,58,48,58,89,74,86,72,43,59,83,52}

    {39,18,79,85,16,85,98,97,41,43,42,25,87,80,31,89,45,30,30,26,60,31,15,12,7,4,9,43,49,73,73}

    322

    Returns: 1463

  21. {47,55,58,64,86,36,83,35,40,23,35,31,53,9,10,96}

    {43,81,41,62,33,6,91,49,63,47,38,98,96,90,47,63}

    3630

    Returns: 624

  22. {96,68,45,95,94,21,66,93,29,92,38,43,23,90,12,30,44,84,31,68,43,51,19,45}

    {41,44,83,100,35,56,61,77,75,29,54,54,54,73,99,65,80,8,10,67,9,55,57,26}

    1177

    Returns: 1182

  23. {3,81}

    {53,60}

    3993

    Returns: 18

  24. {65,80,74,38,99,39,17,42,68,83}

    {23,68,42,65,67,78,13,55,12,59}

    4212

    Returns: 415

  25. {49,93,86,60,36,70,4,72,42,64,35,82,75,70,4,29,77,68,25,97,37,26,18,22,21,42,35,100,79,41,84,82,56,71,64,81}

    {76,78,10,14,47,18,1,26,32,12,92,33,88,64,55,70,70,55,85,91,27,50,72,23,3,97,42,52,35,42,35,36,58,58,65,47}

    1295

    Returns: 1856

  26. {48,68,29,57,30,48,21,54,29,91,99,14,60,79,9,48,10,19,61,18,87}

    {83,97,31,7,73,23,60,14,10,57,39,28,58,21,78,67,37,65,82,21,99}

    2889

    Returns: 771

  27. {4,72,66,93,47,65,18,55,1,38,25,81,92,94,81,19,53,20,39,67,51}

    {70,51,48,9,7,43,51,8,20,68,7,1,39,44,50,79,20,96,6,63,71}

    3159

    Returns: 688

  28. {54,53,87,8,79,64,53,36,84,25,7,98,21,43,79,93,80,83,84,28,46,10,65,52,95,58,76,25,99,45}

    {85,7,42,14,59,47,85,96,65,39,73,10,10,53,59,40,24,43,71,97,47,3,17,9,96,3,47,1,2,84}

    3649

    Returns: 1243

  29. {42,88,83,36,97,39,33,29,20,96,100}

    {46,39,55,31,58,13,8,16,81,46,88}

    1275

    Returns: 561

  30. {59,74,61,71,28,82,57,92,34,73,64,29,89,63,1,91,39,74,42}

    {59,97,59,91,16,16,67,85,82,14,34,77,73,9,25,43,7,59,41}

    1912

    Returns: 945

  31. {36,39,15,41,21,5,16,64,67,73,85,95,71,39,28,100,9,4,96,35,92,96}

    {84,40,93,12,54,47,100,80,13,78,7,44,20,47,8,81,48,47,27,11,69,5}

    4714

    Returns: 695

  32. {35,18,13}

    {53,52,44}

    2105

    Returns: 24

  33. {20}

    {10}

    3075

    Returns: 0

  34. {42,27,53,80,28,44,87,13,49,39,18,61,77,29,61,8,98,66,51,52,38,50,3,56,51,99,65,48,1,63,15,51,41,74}

    {87,34,95,58,29,70,29,72,13,60,44,78,7,84,16,51,13,74,16,91,69,2,21,27,61,62,28,98,79,69,29,59,88,69}

    2687

    Returns: 1356

  35. {81,78,43,71,61,90,87,12,24,12,31,83,26,67,9,5,97,39,100,80,56}

    {32,37,44,82,30,81,100,27,49,25,46,66,85,81,19,34,35,29,16,3,89}

    4797

    Returns: 866

  36. {87}

    {89}

    774

    Returns: 79

  37. {56,82,87,5,20,85,81,27,27,97,9,69,4,46,5,90,27,10}

    {81,50,74,54,46,44,21,8,16,43,15,21,4,16,34,4,86,100}

    2828

    Returns: 580

  38. {36,6,80}

    {15,41,57}

    4831

    Returns: 10

  39. {14,13,72}

    {22,8,19}

    3829

    Returns: 0

  40. {91,82,31,53,42,23,86,97,12,28,17,75,46,24,10,94,66,28,69,3,43,96,6,8,39,13,85,57,61,33,3}

    {41,85,76,45,94,18,82,11,80,78,15,26,74,58,92,84,67,20,90,93,57,43,21,82,56,19,78,46,13,37,89}

    1378

    Returns: 1301

  41. {75,50,37,4,13,88,80,89,36,91,59,95,22,65,48,93,23,30,50,65,92,8,28,95,53,99}

    {91,48,25,77,69,95,11,77,14,29,94,62,86,14,44,100,76,30,49,58,21,88,45,78,37,70}

    843

    Returns: 1412

  42. {95,1,89}

    {82,16,11}

    2878

    Returns: 73

  43. {45,94,8,5,74,34,64,4,30,36,95,7,45,3,83,46,67,80,26,82,95,84,12,91,62,11,64,97,49,32,73}

    {53,57,81,3,16,79,80,39,8,75,37,73,68,8,68,79,62,49,78,75,52,27,5,73,36,91,38,56,25,24,24}

    2530

    Returns: 1433

  44. {9,68,8,15,38,18,9,27,2,30,76,96,58,50,99,5,79,25,8,43,83,56,68,84,43,99,2,39,13,49,3,56,1,83,41,9}

    {80,60,10,58,16,64,71,77,7,49,54,34,20,26,7,9,83,75,40,95,99,38,24,50,75,64,64,39,42,56,26,81,79,11,82,20}

    2948

    Returns: 1228

  45. {1,79,21,23,79,13}

    {97,66,16,76,28,79}

    2633

    Returns: 115

  46. {61,16,39,89,2,67,6,94,21,16,99,30,99,28,70,68,41,60,46,40,21,58,37,53,37,26,32,95,80,22,30,12,89,81,61}

    {78,48,57,10,44,28,51,81,87,90,17,31,76,19,43,38,60,97,69,38,88,72,11,70,11,64,1,38,26,84,55,57,22,36,70}

    4290

    Returns: 1389

  47. {17,44,6,53,97,13,94,35,27,33,7,94,100,74,24,45,71,87,4,34,36,76,43,99,87,37,94,52,71,96,54,73,77,16,57,74,32,10,62,70,64,76,25,16,48,93,28,20,70,76}

    {44,88,72,20,91,96,87,20,50,76,1,43,7,77,13,97,2,47,52,37,47,95,84,51,38,17,70,17,34,60,27,92,56,86,56,86,41,25,6,14,29,40,58,61,70,54,35,84,6,48}

    4739

    Returns: 2184

  48. {59,86,62,6,95,27,69,38,55,33,46,25,61,8,32,4,100,41,96,34,35,90,3,82,71,57,64,45,41,34,67,11,78,68,21,41,32,40,37,53,12,41,99,97,97,72,85,46,21,14}

    {36,44,89,9,63,98,49,1,59,88,10,99,57,76,75,6,59,43,5,35,56,24,43,56,42,40,70,60,14,11,70,99,61,14,69,72,29,14,64,33,57,95,17,97,91,77,3,51,77,40}

    4472

    Returns: 2032

  49. {76,44,62,89,50,31,37,90,57,53,76,88,96,92,45,42,44,10,89,82,74,4,13,55,77,98,24,36,75,27,20,51,52,75,62,70,54,4,91,70,29,37,99,70,23,37,23,78,68,93}

    {64,5,56,35,74,58,15,39,65,1,55,99,67,21,14,38,9,12,53,74,5,26,35,37,10,95,62,14,2,75,12,59,89,83,73,4,43,45,51,66,24,93,82,62,56,76,63,91,3,38}

    3691

    Returns: 2244

  50. {97,4,58,89,1,62,95,15,41,43,90,51,23,74,34,86,60,61,72,89,26,97,80,92,14,66,34,3,94,8,15,42,88,39,5,68,63,86,76,85,64,14,60,93,17,21,35,54,43,61}

    {76,87,38,15,75,32,98,55,23,64,92,79,37,88,9,58,6,61,25,52,19,79,97,40,36,67,84,1,58,16,75,26,76,95,12,77,33,39,67,35,21,21,61,26,59,58,72,49,84,91}

    138

    Returns: 2663

  51. {31,94,67,36,69,42,95,71,26,73,91,41,99,34,62,72,91,61,4,80,59,66,24,95,68,57,66,2,100,9,95,74,76,98,92,22,12,53,11,98,17,7,51,8,40,32,87,60,54,25}

    {32,43,62,85,69,53,17,29,67,28,25,66,40,4,36,70,84,22,16,46,7,36,93,74,23,8,19,67,79,85,59,2,48,39,87,43,12,8,50,51,41,12,14,30,87,67,17,44,49,58}

    1604

    Returns: 2518

  52. {8,94,43,83,58,49,25,61,89,53,85,79,9,10,94,38,59,77,20,54,68,99,16,33,24,65,25,80,41,11,45,31,69,47,25,96,21,48,94,69,4,58,33,34,45,96,58,12,42,2}

    {96,26,82,69,65,33,76,93,47,55,49,64,37,85,57,38,39,55,62,85,97,84,3,12,26,77,63,99,52,25,83,30,25,78,82,40,35,100,58,14,47,86,26,85,80,1,73,16,10,65}

    3259

    Returns: 2166

  53. {10,59,71,11,27,46,59,74,56,41,100,30,79,9,43,92,41,78,94,84,50,55,50,63,65,39,22,12,38,99,89,68,61,57,87,26,60,55,54,48,83,39,59,100,78,96,41,9,37,53}

    {9,27,77,50,70,9,39,7,39,45,4,57,57,95,9,92,31,27,89,82,32,39,57,50,62,82,96,50,79,89,98,86,43,24,87,31,81,46,8,36,89,88,87,14,68,30,12,61,24,4}

    2303

    Returns: 2434

  54. {95,33,98,73,69,32,86,77,62,45,38,89,81,21,83,12,48,60,26,83,50,18,94,79,24,81,100,5,74,28,56,40,68,12,61,68,23,33,51,43,91,18,93,73,64,18,87,74,82,73}

    {39,26,16,89,47,28,56,14,44,24,57,32,49,32,46,81,75,55,10,11,31,24,77,35,4,45,77,80,62,80,8,57,7,20,7,60,43,52,34,87,12,3,18,24,45,37,77,51,100,34}

    3513

    Returns: 2487

  55. {95,70,5,3,14,84,43,1,45,94,63,45,26,49,40,13,82,70,34,46,58,7,74,42,69,20,17,47,11,92,98,46,37,26,19,83,42,95,40,19,64,3,19,15,16,60,79,39,86,60}

    {11,71,26,36,12,19,64,91,11,88,13,67,44,74,30,95,86,90,18,80,55,57,98,6,79,73,61,22,21,37,5,76,14,76,25,54,12,10,8,67,2,40,1,98,73,71,71,13,3,3}

    3167

    Returns: 1750

  56. {10,4,73,93,4,73,94,82,5,68,76,88,45,1,56,32,36,34,66,33,98,73,88,84,13,51,39,10,54,69,92,5,18,75,29,80,80,98,10,39,27,25,41,76,40,1,87,6,63,49}

    {11,18,76,87,97,80,93,48,9,61,83,78,73,67,18,65,52,23,39,65,99,62,40,44,7,78,77,7,69,47,98,5,88,2,24,23,30,58,7,3,79,88,19,62,55,47,36,51,40,93}

    3303

    Returns: 2192

  57. {100 }

    {10 }

    100

    Returns: 90

  58. {1, 2, 39, 4, 6 }

    {1, 2, 3, 49, 10 }

    2

    Returns: 51

  59. {100 }

    {1 }

    26

    Returns: 74

  60. {1, 10, 15, 20, 25, 35 }

    {55, 45, 30, 15, 10, 5 }

    80

    Returns: 90

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

    {5, 4, 3, 2, 1 }

    15

    Returns: 6

  62. {22, 33, 44, 55 }

    {45, 75, 35, 25 }

    5000

    Returns: 19

  63. {100, 100 }

    {10, 10 }

    10

    Returns: 199

  64. {10 }

    {2 }

    3

    Returns: 9

  65. {100, 100 }

    {100, 100 }

    1

    Returns: 200

  66. {1, 1, 1, 1, 1 }

    {100, 100, 100, 100, 100 }

    100

    Returns: 4

  67. {5, 1 }

    {1, 2 }

    10

    Returns: 0

  68. {2 }

    {5 }

    4

    Returns: 2

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

    {5, 4, 2, 2, 1 }

    15

    Returns: 5

  70. {1 }

    {1 }

    1

    Returns: 0

  71. {1, 2, 50, 30, 6 }

    {5, 8, 10, 30, 1 }

    30

    Returns: 80

  72. {5 }

    {5 }

    5

    Returns: 4

  73. {5, 5, 5 }

    {3, 5, 10 }

    8

    Returns: 13

  74. {4, 4, 4, 4, 4 }

    {2, 2, 2, 2, 2 }

    4

    Returns: 18

  75. {100, 1 }

    {1, 2 }

    102

    Returns: 0

  76. {1, 100, 100 }

    {1, 3, 5 }

    20

    Returns: 194

  77. {1, 2, 3, 5, 5 }

    {5, 4, 3, 2, 1 }

    15

    Returns: 6

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: