MKBUDGET - Making A Budget

A company uses temporary employees (“temps”) to handle its varying workloads. By doing so, it avoids having to pay for benefits normally provided to its permanent employees. However, the company must pay an employment agency a fixed fee for each temp they hire, as well as paying the temp a fixed amount of severance pay when they are terminated – in addition, of course, to the monthly salary each temp receives. The company has a good understanding of when it needs temporary workers, and how many such workers it will require each month. Depending on the fee paid to the employment agency, the temporary worker’s salary, and the severance pay, it may make sense to retain an unneeded worker for one or more months if it’s known that they will be needed again in the future.

Let’s consider an example. Suppose we know that in March the company will need 10 temps, in April they’ll need 9, and in May they’ll need 11. Suppose a temp earns $500 per month, that the employment agency receives $400 for each temp hired, and $600 is paid as severance to each temp that is terminated. If the company employs just the minimum number of temps required, then their payments will be as follows (we ignore the cost of terminating all employees at the end of the last month):


The total cost to the company is $20,400. But suppose they did not terminate the unneeded temp at the end of March, but just let that person remain employed. They would then save $400 in employment agency fees (since they’d need to hire just one additional temp for May), $600 in severance pay, and only have to pay the temp worker $500, for an overall savings of $500.

In this problem you are given, as input, the number of months for which the company is to plan its temp worker budget, the cost of hiring and firing a temp worker, the temp worker’s monthly salary, and the required minimum number of workers needed each month. You are to determine the minimum cost to the company to have at least the required minimum number of workers on hand each month. Assume there are no temporary workers on hand before the first month, and that the cost of terminating the workers at the end of the last month is not to be included in the cost. You may assume that the planning interval will be no longer than 24 months, and the hiring cost, severance pay, and monthly salary for each temp worker is greater than zero.


There will be multiple cases to consider. The input for each case begins with an integer N, the number of months for which planning is required (never larger than 24). This is followed by three integers giving the cost of hiring a worker, the worker’s monthly salary, and the severance pay for a terminated worker. Finally there will appear N integers giving the required minimum number of workers needed in each month. The last case will be followed by a zero.


For each input case, display the case number (1, 2, …) and the minimum cost to the company. Use the format shown in the examples below.


3 400 500 600 10 9 11
8 400 600 600 11 9 10 14 9 9 13 15

Case 1, cost = $19900
Case 2, cost = $66600

hide comments
chand_4: 2021-08-01 14:50:40

what will be the time complexity for an efficient algorithm?

abhishen99: 2020-11-08 05:51:05

easy peasy

bhavya_kala10: 2020-08-17 20:12:57

AC in 2nd GO!!! (silly typo)

ankitpriyarup: 2018-12-22 14:14:13

I don't know how recursion with memoization worked for others for me bottom-up DP worked. Anyone willing to share memoized solution please share :)

Last edit: 2018-12-22 14:17:07
aman_sachin200: 2018-06-15 20:53:10

The key to solving this problem lies in "Firing the employees Efficiently!!" :P
Nice One!!! :D

Last edit: 2018-06-15 20:54:07
hello_world123: 2018-06-15 19:39:54

Don't know why all ranting about the limits , there is no need of knowing in advance. No need of using long int .

Last edit: 2018-06-15 19:58:04
manas0008: 2017-02-04 07:35:35

1)donot use spoj toolkit for this question(it shows incorrect output)
2)prefer bottom-up approach (i struggled with topdown memorisation but of no use).
3)assume maximum no. of employees needed in a month = 30.
Had to give a lot of time only for debugging.My construction of code time was not even 0.01% of my debugging duration.

Last edit: 2017-02-04 07:36:06
birdie: 2016-01-05 18:16:14

nice one :)

naruto09: 2015-12-26 11:24:48

what will be the output for 3 400 500 600 10 9 9.. ??

theweblover007: 2015-11-13 11:19:43

Couldn't believe when i got AC :p

Added by:Camilo Andrés Varela León
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:North Central North America Regional Programming Contest - 2003