-
Notifications
You must be signed in to change notification settings - Fork 1
/
Elite Day-12 Program-4.txt
80 lines (63 loc) · 2.36 KB
/
Elite Day-12 Program-4.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
In the present situation, most of the movies releasing in OTTs.
The Showtime OTT in US, introduced a new offer for the customers,
they can purchase either 1-day, 7-day, or 30-day subscription,
and the cost is as follows price[0], price[1], price[2].
The Subscription allows you to watch as many movies as you want with in subscribed days.
For example:
If you purchased, a 7-day subscription on day 5, then you can watch
the movies for 7 days: day 5, 6, 7, 8, 9, 10 and 11.
Your task is to find out the minimum cost, you spend to watch the movies
in the given list of days .
NOTE: Days are numbered from 1, 2, 3, ...365, in sorted order.
Input Format:
-------------
Line 1: Space separated integer days[], list of days.
Line 2: 3 space separated integer price[], cost of subscription.
Output Format:
--------------
Print an integer, minimum cost.
Sample Input-1:
---------------
1 4 6 7 8 20
2 7 15
Sample Output-1:
----------------
11
Explanation:
------------
For example, here is a way to buy subscription, to watch the movies in given days:
On day 1, buy a 1-day subscription for price[0] = $2, which cover day 1.
On day 4, buy a 7-day subscription for price[1] = $7, which cover days 4, 5, ..., 10.
On day 20, buy a 1-day subscription for price[0] = $2, which cover day 20.
In total you spent $11.
Sample Input-2:
---------------
1 2 3 4 5 6 7 8 9 10 30 31
2 7 15
Sample Output-2:
----------------
17
Explanation:
------------
For example, here is a way to buy subscription, to watch the movies in given days:
On day 1, buy a 30-day subscription for price[2] = $15, which cover days 1, 2, 3,....,30.
On day 31, buy a 1-day subscription for price[0] = $2, which cover day 31.
In total you spent $17.
def Savings(days,costs):
size = days[-1]
max_cost = max(costs) * size
dp = [0] + [max_cost] * size
ott_price = {1: costs[0], 7: costs[1], 30: costs[2]}
for day in range(1, len(dp)):
if day not in days:
dp[day] = dp[day - 1]
continue
for ott in [1, 7, 30]:
if day >= ott:
dp[day] = min(dp[day], dp[day - ott] + ott_price[ott])
else:
dp[day] = min(dp[day], dp[0] + ott_price[ott])
return dp[-1]
days=list(map(int,input().split()))
cost=list(map(int,input().split()))
print(Savings(days,cost))