https://www.codechef.com/COOK124B/problems/HIRINGWO/

1

I think this problem is can be solved in a approach that for any X :
case 1: x is prime then number of min workers x+k-1
case 2: x is not prime:-
case I: x has 2 or more prime factor then number of min workers = sum of first 2 prime
factors +(k-2)
case II: x has less than 2 prime factors then number of min workers x+k-1
example:
k=4 x=7
then min no of workers will be [7+(4-1)]=10 …(case 1)
k=3 x= 12
then min no of workers will be [2+3(first 2 prime factors of 12 ) +(3-2)] = 6 …(case 2> case I)
k=3 x=8
then min no of workers will be [8+(3-1)]=10…(case 2> case II )

i have code this but it shows wrong answer
can any one help me to found what is wrong in my approach ?
Thankx in advance

2

In your solution, for Case 2:1 when x is not prime you are considering only the first 2 primes in the answer. Let’s take this example when x=12 and k=2, as per your sol, we will get two groups of workers with size-2 and 3, but they will complete their work on day 6 itself, not on day 12, so its a wrong approach.

We have to find k numbers whose LCM is x and the sum is min.

1 Like
3

yes , i haven’t notice that