Click here to Skip to main content
15,939,853 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
Chef is multi-talented. He has developed a cure for corona virus called CO-VAC-19. Now that everyone in the world is infected, it is time to distribute it throughout the world efficiently to wipe out corona virus from the Earth. Chef just cooks the cure, you are his distribution manager.

In the world, there are N countries (numbered 1 through N) with populations a1,a2,…,aN. Each cure can be used to cure one infected person once. Due to lock down rules, you may only deliver cures to one country per day, but you may choose that country arbitrarily and independently on each day. Days are numbered by positive integers. On day 1, Chef has x cures ready. On each subsequent day, Chef can supply twice the number of cures that were delivered (i.e. people that were cured) on the previous day. Chef cannot supply leftovers from the previous or any earlier day, as the cures expire in a day. The number of cures delivered to some country on some day cannot exceed the number of infected people it currently has, either.

However, corona virus is not giving up so easily. It can infect a cured person that comes in contact with an infected person again ― formally, it means that the number of infected people in a country doubles at the end of each day, i.e. after the cures for this day are used (obviously up to the population of that country).

Find the minimum number of days needed to make the world corona-free.

What I have tried:

We have been given with a sorted (in non-decreasing order) list of N positive integers (A1, A2 , ..... , An) and another positive integer X . We have to make all the list integers zero using the Integer X. But there are some conditions to do so:
Condition 1 : At one time we can only subtract X to one Integer in List (Ai).
Condition 2 : After Every Operation (of condition 1) All the Integers of list gets Doubled as well as X gets doubled.
Condition 3 : If X is larger than Ai then the Value of X changes to Ai and then Subtraction takes place.

What to find : We need to find the minimum operations to make all integers in list zero.

A sample to Understand Better :

List : 1 2 3 4 5 

X : 4


Here to find most optimal solution we will first make 4 into zero using X.
Operation cost = 1

Now every integer will be doubled hence new list will be
2 4 6 0 10, X = 8 
2 4 6 0 2, X = 8 (subtracting 10 - 8) Operation cost = 2

Again every thing gets doubled so new list is
4 8 12 0 4 , X = 16
4 8 0 0 4, X = 12` (as 12 < 16, X becomes 12) Operation cost = 3 

Again every thing gets doubled so new list is
8 16 0 0 8, X = 24 
8 0 0 0 8, X = 16  (as 16 < 24, X becomes 16) Operation cost = 4 

Again every thing gets doubled so new list is
16 0 0 0 16, X = 32
16 0 0 0 0, X = 16 (as 16 < 32, X becomes 16) Operation cost = 5
Again every thing gets doubled so new list is
32 0 0 0 0, X = 32 
0 0 0 0 0, X = 32  (as 32 <= 32, X becomes 32) Operation cost = 6


So, Finally in 6 operations we made the list zero.
Some More cases with Answers :

List : 10 20 30 40 50
X : 1
Answer : 9


List : 1 20 110
X : 10
Answer : 6


Constraints :  (1 <= Ai<= 1000000000) , (1 <= X <= 1000000000)

My approach

- Let
a
be an integer in list and x is given to make `a` into zero.
- Now, there will a series formed after every operation as given below
(a-x) , (2(a-x) - 2x) , (2(2(a-x) - 2x) - 4x) , ..........
  (a-x) , (2a - 4x) , (4a - 12x), (8a - 32x) , .....
  (a-x) , 2(a-2x) , 4(a-3x) , 8(a-4x) , .......
  an = (2^(n-1))(a-nx) | where an is nth term


So to make
An == 0 , A-nx = 0, A = n/x 


I have figured out how to make any single integer zero with x but i cant figure out how to make the list zero with minimum operations, As I have to make a code for that also so what i need is a basic algorithm which can be used to solve this problem.
Can anyone help me with this ??
Posted
Updated 12-Jul-20 3:26am
v3
Comments
Patrice T 7-Jul-20 4:42am    

We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

THink about the problem, try it out manually with small numbers and see what you can work out - we aren't here to "pass tests" for you even if they aren't "formal homework" as you
don't learn anything from the experience if we do!
 
Share this answer
 
You have asked the wrong question. Your sample test case is wrong. It cannot go beyond the given population so it can never go beyond 1,2,3,4,5 like you did: 2,4,6,8,10 these numbers cannot be formed.

Basically your answer to that test case should have been 5.
 
Share this answer
 
v2
import heapq as hq
for _ in range(int(input())):
d=0
t=0
c=0
n,x=map(int,input().split())
a=list(map(int,input().split()))
hq.heapify(a)
a=[hq.heappop(a) for i in range(len(a))]
if x in a:
t=a.index(x)
else:
for i in a:
if x>i:
c+=1
t=c
for i in range(t,n,1):
if x<a[i]:
while x<a[i]:
x=2*x
d+=1
d+=1
else:
d+=1
x=2*a[i]
t1=t+d
if t!=0:
d=0
t=t-1
for i in range(t,n,1):
if x<a[i]:
while x<a[i]:
x=2*x
d+=1
d+=1
else:
d+=1
x=2*a[i]
if d+t<t1:
print(d+t)
else:
print(t1)
else:
print(t1)
 
Share this answer
 
Comments
Patrice T 12-Jul-20 11:32am    
Use Improve solution to update your question.
While improving:
- Select all the code
- Hover on code button and click on Java in the popup

A couple sentences will be appreciated too.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900