Connection Status:
Competition Arena > BusinessPlan

BusinessPlan

SRM 229 · 2005-01-31 · by AdrianKuegel

SRM 229 · 2005-01-31 · by AdrianKuegel · Dynamic Programming
Class Name: BusinessPlan
Return Type: int
Method Name: howLong
Arg Types: (vector<int>, vector<int>, vector<int>, int, int)
Problem Statement

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.

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
0)
{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.

1)
{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.

2)
{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.

3)
{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.

4)
{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.

5)
{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.

6)
{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)

7)
{1}
{2}
{10}
1
100000
Returns: 999990

maximum number of required hours

Submissions are judged against all 67 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BusinessPlan with a public method int howLong(vector<int> expense, vector<int> revenue, vector<int> ptime, int C, int D) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous