Statistics

Problem Statement for "BusinessPlan"

Problem Statement

A new company has hired you to help create a business plan. The company can produce several products, but only one product unit at a time. For each product the expense and the revenue for one unit is known, as well as the production time ptime. There must be enough money to cover the expenses before the production of a unit is started. After a unit of a product is finished, it is sold immediately for the value defined in revenue.
The company has a startup capital of C dollars, but to repay their debts they need to reach an amount of D dollars as soon as possible. It is your job to write a method that calculates the minimum amount of time units that the company needs to reach an amount of at least D dollars. If it is impossible to reach an amount of at least D dollars without borrowing any more money, your method should return -1.
Your method is given the information about the products as int[] expense, int[] revenue and int[] ptime. The ith element of expense, revenue and ptime represents the ith product.

Definition

Class:
BusinessPlan
Method:
howLong
Parameters:
int[], int[], int[], int, int
Returns:
int
Method signature:
int howLong(int[] expense, int[] revenue, int[] ptime, int C, int D)
(be sure your method is public)

Notes

  • All money values are given in dollars.

Constraints

  • expense, revenue and ptime contain between 1 and 10 elements, inclusive.
  • expense, revenue and ptime contain the same number of elements.
  • Each element of expense and revenue is between 1 and 100000, inclusive.
  • The ith element of revenue is always greater than the ith element of expense.
  • Each element of ptime is between 1 and 10, inclusive.
  • C is between 1 and 2147483647, inclusive.
  • D is between 0 and 100000, inclusive.

Examples

  1. {1,4}

    {2,10}

    {1,2}

    1

    10

    Returns: 5

    First, only product 0 can be produced, since there is not enough money to cover the expenses for product 1. After 3 time units producing product 0, the required money for product 1 is available. Producing a unit of product 1 requires 2 time units, therefore the return value is 5.

  2. {11}

    {20}

    {10}

    10

    10

    Returns: 0

    There is already enough money available to repay the debt. Note that we don't care that the company won't be able to produce anything without borrowing more money.

  3. {11}

    {20}

    {10}

    10

    11

    Returns: -1

    Now the company needs to earn some money, but as in the previous test case, producing one unit requires an amount of 11 dollars.

  4. {1,1,1}

    {3,4,8}

    {1,2,3}

    1

    11

    Returns: 5

    Produce one unit of product 1 and one unit of product 2. Another possibility is to produce two units of product 0 and one unit of product 2.

  5. {1,1,1}

    {8,11,10}

    {5,7,6}

    1

    22

    Returns: 15

    Shows that it is not always optimal to produce the product with maximum (revenue - expense)/ptime ratio. In this example it is even the product with the smallest ratio that has to be produced.

  6. {99999,1,99998,2,99997,3,99996,4,99995,5}

    {100000,100000,100000,100,100000,100000,100000,100000,100000,100000}

    {1,9,1,10,1,9,1,9,1,9}

    2

    100

    Returns: 9

    The company wants to get at least 100 dollars, so producing product 1 one time and getting 100000 dollars is fine.

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

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

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

    1

    100000

    Returns: 100044

    time critical test case (should still be no problem for a correct solution)

  8. {1}

    {2}

    {10}

    1

    100000

    Returns: 999990

    maximum number of required hours

  9. {1,1,1,22,880}

    {8,11,10,100,1080}

    {5,7,6,1,2}

    1

    99958

    Returns: 1017

  10. {17749,9129,26802,56920}

    {36773,28950,27092,84511}

    {3,6,8,8}

    52693

    54657

    Returns: 3

  11. {26715,2520,12458,23773,687}

    {49776,44080,32683,55363,96907}

    {6,3,1,4,4}

    19100

    41718

    Returns: 2

  12. {51153,8819,33029,8522,21627}

    {67899,49728,48907,87155,65782}

    {3,1,10,10,7}

    73574

    99898

    Returns: 1

  13. {51252,42574,67170,4380,38006,23498}

    {60168,59567,78099,6602,91577,26606}

    {10,9,10,4,5,9}

    1109

    1614

    Returns: -1

  14. {20293,20550,51306,61203,9748,23763}

    {58419,51755,96007,89475,29524,81562}

    {3,5,10,9,8,3}

    35697

    82820

    Returns: 3

  15. {44367,7336,2025,8744,76860,20387}

    {55298,25429,3969,16062,81013,21668}

    {7,4,2,5,6,7}

    13084

    60056

    Returns: 12

  16. {66319,53419,162,42597,38836,8041,24060}

    {72250,92963,4462,65711,39348,59427,65627}

    {7,9,8,9,10,6,9}

    22748

    93855

    Returns: 12

  17. {31248,64621,35895,84144,25752,75397,19421}

    {48551,92235,50656,95835,55108,85194,36214}

    {4,1,2,1,4,7,1}

    2206

    5590

    Returns: -1

  18. {21137,45038,39395,63495,4849,4162,45317}

    {74186,63330,41308,68442,76328,92393,61621}

    {7,3,3,1,10,3,1}

    36457

    64887

    Returns: 3

  19. {25364,11043,227,23,3807,37438,1196}

    {65971,61068,54302,222,17872,70204,10325}

    {6,1,8,7,7,7,1}

    3112

    26092

    Returns: 2

  20. {10180,6364,1470,6274,3247,51625,39584,12151}

    {37701,56222,40002,38024,4007,51933,64201,37083}

    {10,10,9,8,5,1,8,5}

    14611

    19736

    Returns: 5

  21. {32813,24765,128,798,29390,15074,437,47968}

    {38802,41556,55893,92541,66210,27344,9427,52419}

    {3,6,10,9,9,2,7,9}

    75000

    92392

    Returns: 4

  22. {21875,88915,8207,71907,18268,35,169,47390}

    {69046,94139,75445,75878,25742,2599,7933,67436}

    {4,3,10,5,7,3,6,1}

    19137

    22818

    Returns: 6

  23. {59925,11365,8115,4962,11654,445,9314,64238}

    {85138,49353,60976,66442,32936,3537,75427,66263}

    {5,5,8,5,4,8,2,6}

    46268

    90322

    Returns: 2

  24. {44575,195,23328,43474,664,17285,35372,34449}

    {93384,946,48761,73952,17706,26223,46935,99102}

    {10,2,1,5,2,9,3,3}

    55468

    72523

    Returns: 1

  25. {10143,7070,10598,2803,39910,25238,18367,19262,3529}

    {53899,7574,25979,12790,73515,36424,65269,93298,10924}

    {1,6,6,1,9,9,2,8,6}

    77451

    96376

    Returns: 1

  26. {34061,3071,14291,73401,14887,3351,49152,1854,41728}

    {41314,11141,99581,83881,42441,49614,65717,7587,77305}

    {2,5,8,8,6,7,3,4,8}

    5188

    16915

    Returns: 7

  27. {66686,51116,30142,5392,24105,82206,20419,8687,55573}

    {78967,67141,58161,14423,79133,89728,32938,12030,72834}

    {5,4,5,8,5,4,1,10,2}

    22477

    46976

    Returns: 2

  28. {64074,47918,20362,49440,42086,12609,5583,9788,2019}

    {80577,57945,29370,98450,52198,46438,23150,50276,15225}

    {2,9,9,1,10,6,8,8,10}

    24960

    71237

    Returns: 7

  29. {6956,371,18045,44687,30447,79698,622,28501,9541}

    {49575,12311,23122,76864,52972,84748,1679,38823,13796}

    {10,3,7,1,8,2,2,8,10}

    11152

    18871

    Returns: 3

  30. {11089,267,51504,34784,55612,50864,33260,54156,32120}

    {97527,10900,52532,58666,91448,61408,71467,70757,34495}

    {4,2,4,6,2,10,7,10,3}

    31607

    80142

    Returns: 4

  31. {75140,372,70327,2008,65004,5415,31487,51537,12385,699}

    {94429,1071,79997,4551,99435,81408,83441,74180,18774,80650}

    {5,9,4,2,8,9,4,7,1,7}

    7450

    84563

    Returns: 7

  32. {8347,92755,62477,20406,6306,12483,48988,9100,1372,77644}

    {18124,99666,67811,28508,78620,13465,62979,13017,6477,94619}

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

    10009

    24690

    Returns: 1

  33. {16968,2494,38234,4,19317,6580,16037,43409,49994,4550}

    {24412,20843,50595,5763,21222,7042,83639,61804,61880,26758}

    {6,4,1,7,8,3,1,9,4,1}

    67532

    77901

    Returns: 1

  34. {62683,52670,46434,10600,10307,53845,23846,4787,2070,11675}

    {67218,94278,71325,14376,31955,63740,49489,59486,17859,62719}

    {7,8,1,1,3,4,8,3,10,1}

    5721

    8246

    Returns: 3

  35. {6412,2063,14790,11300,971,4995,59960,31392,16907,13707}

    {27891,48494,16303,12026,2283,28805,70291,32338,19995,21945}

    {9,5,9,10,3,10,1,4,9,2}

    3364

    22946

    Returns: 5

  36. {9842,54527,59509,36389,62669,14626,18890,1146,5862,31850}

    {15426,84913,73591,70470,77655,68190,46881,41833,33453,70889}

    {5,2,5,9,8,9,2,1,1,1}

    43264

    69011

    Returns: 1

  37. {11518,31890,11085,23744,80595,57502,71257,3356,63490,14269}

    {82598,72888,45301,74234,82591,59879,74300,34693,75174,14722}

    {1,9,4,10,4,6,2,6,4,2}

    3044

    65758

    Returns: -1

  38. { 49456, 33732, 98471, 3483, 29222, 44583, 32231, 84623, 4881, 99342 }

    { 54332, 36653, 99999, 9000, 34823, 49999, 34223, 89223, 9912, 99999 }

    { 5, 3, 4, 2, 6, 5, 8, 4, 4, 2 }

    13000

    99283

    Returns: 32

  39. { 1, 90000 }

    { 2, 90001 }

    { 10, 5 }

    1

    100000

    Returns: 949990

  40. { 1, 4 }

    { 2, 10 }

    { 1, 2 }

    1

    100000

    Returns: 33335

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

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

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

    5

    100000

    Returns: 99998

  42. { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    9

    100000

    Returns: 999910

  43. { 99999, 99999, 99998, 99999, 99997, 99999, 99996, 99999, 99995, 1 }

    { 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 2 }

    { 1, 9, 1, 10, 1, 9, 1, 9, 1, 9 }

    2

    100000

    Returns: 899938

  44. { 1 }

    { 2 }

    { 10 }

    1

    100000

    Returns: 999990

  45. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    1

    100000

    Returns: 999990

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

    { 10, 20, 30, 35, 60, 80, 85, 90, 110, 115 }

    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    2

    100000

    Returns: 954

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

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

    { 1, 2, 3, 1, 2, 3, 1, 2, 3, 4 }

    1

    99999

    Returns: 99998

  48. { 1 }

    { 100000 }

    { 5 }

    90000

    95000

    Returns: 5

  49. { 1, 4 }

    { 2, 10 }

    { 1, 2 }

    11

    10

    Returns: 0

  50. { 1, 1, 1 }

    { 3, 4, 8 }

    { 1, 2, 3 }

    1

    100000

    Returns: 42857

  51. { 100, 100 }

    { 150, 15000 }

    { 1, 2 }

    100

    101

    Returns: 1

  52. { 1, 2 }

    { 2, 3 }

    { 9, 10 }

    1

    100000

    Returns: 899991

  53. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    1

    10000

    Returns: 19998

  54. { 1, 1, 2 }

    { 2, 5, 100 }

    { 1, 2, 1 }

    1

    100

    Returns: 2

  55. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    1

    100000

    Returns: 99999

  56. { 1 }

    { 100000 }

    { 10 }

    2147483647

    100000

    Returns: 0

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

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

    { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    1

    10000

    Returns: 99990

  58. { 1, 1 }

    { 8, 6 }

    { 6, 5 }

    1

    11

    Returns: 10

  59. { 1, 1, 1 }

    { 2306, 122, 2561 }

    { 9, 1, 10 }

    1

    100000

    Returns: 391

  60. { 1, 1, 2 }

    { 10, 2, 20 }

    { 3, 1, 1 }

    1

    20

    Returns: 2

  61. { 1, 100 }

    { 2, 1000 }

    { 1, 10 }

    1

    1901

    Returns: 120

  62. { 1, 2, 3 }

    { 4, 1000, 100 }

    { 1, 10, 8 }

    5

    1050

    Returns: 18

  63. { 15, 10 }

    { 30, 30 }

    { 2, 3 }

    15

    35

    Returns: 3

  64. { 1, 1 }

    { 100, 20 }

    { 4, 1 }

    1

    115

    Returns: 5

  65. { 100, 10, 1 }

    { 10000, 100, 50 }

    { 1, 10, 1 }

    10

    10000

    Returns: 3

  66. { 100, 1 }

    { 102, 2 }

    { 1, 1 }

    1

    1000

    Returns: 549

  67. { 1, 1 }

    { 100, 51 }

    { 10, 8 }

    100

    200

    Returns: 16

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: