Great editorial and problem! Also thanks a lot for giving a practice problem too! xD
CodeChef: Practical coding for everyone what is wrong with my solution. can anyone give me the countercase?. thanks in advance.
Why should we go with 2 +3+5=10? We could also use 2,2,3 as it is not given that two teams can’t have the same number of players which would give the sum as 2+2+3=7 which comes less than 10.
question said that number of worker should be minimum I thought why not to distribute 1 member for each task and ans should be equal to k can anyone help me I still cant overcome this approach of mine?
and It was nowhere written that all the task should be completed with minimum rejection.
thank you,
Try this
1
3 90
answer must be 16 (2 ,9, 5).
Thanks bro got it.
Couldn’t figure out what test case i am getting wrong . I have tried all tc’s listed above .
https://www.codechef.com/viewsolution/39780259
Hey bro , i just tested your code. you are messing up on
1
1 90
and maybe others of this type.
Thank you very much
Did this approach work?
It seems correct.
cause 2,2,3 lcm is 6. so x=6. which is false.
can anyone tell which test case is not working in these code.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd( ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return LCM of two numbers
ll lcm(ll a, ll b)
{
return (a / gcd(a, b)) * b;
}
int main() {
// your code goes here
ll t;
cin>>t;
while(t–){
ll k,x,c=0,i=0,j=0,min=1000000000;
cin>>k>>x;
vector v,v1;
int flag=0;
int n=x;
//////////////////////////////////////////////////////////////////////
///////////////////////////////////////// v1 contains prime factor while v contains all factors
while (n%2 == 0)
{
if(flag==0){
flag=1;
v1.push_back(2);
}
else
v1[i]=v1[i]*2;
n = n/2;
}
flag=0;
j=i+1;
for (int i = 3; i <= sqrt(n); i = i+2)
{
flag=0;
// While i divides n, print i and divide n
while (n%i == 0)
{
if(flag==0){
flag=1;
v1.push_back(i);
}
else
v1[j]=v1[j]*i;
n = n/i;
}
j++;
}
// This condition is to handle the case when n
// is a prime number greater than 2
if (n > 2)
v1.push_back(n);
int sum=0;
for(i=0;i<v1.size();i++)
{
// cout<<v1[i]<<" ";
sum+=v1[i];
}
/////////////////////////////////////////////////////////////////////////
for ( i=1; i<=sqrt(x); i++)
{
if (x%i == 0)
{
if (i*i == x)
v.push_back(i);
else
{
v.push_back(i);
v.push_back(x/i);
}
}
}
// cout<<v1.size()<<" "<<sum;
///////////////////////////////////////////////////////////////
if(k<v1.size()){
for(i=0;i<v.size();i++)
{
for(j=i;j<v.size();j++)
{
c=0;
if(lcm(v[i],v[j])==x){
c=v[i]+v[j]+k-2;
if(c<min)
{
min=c;
}
}
}
}
}
else{
min=sum+k-v1.size();
}
cout<<min<<endl;
}
return 0;
}
How can the answer be 12?
The lcm will be 36.
First we will multiply 2^2 to 1 because 1 is minimum in the array and then we will multiply 3^2 to 1. So the lcm will be equal to X.
Correct me if i am wrong
request :
Can anyone provide the test case for which my solution fails ??
code CodeChef: Practical coding for everyone
upd : sorry my fault link is updated.
logic :
I took all the prime to there raised power for example 224 I represented it as (2^5) * (7^1), for 30 I represented it as (2^1) * (3 ^ 1) * (5 ^ 1) since they all are the power of prime so there can never be more than 7 values. so it took all these values and also 1 and did a brute force.
additional work done:
I also checked my solution by making a generator and checking on the setter solution and it looks fine to me. I would request If someone can give a look provide some feedback (sample case on which it fails).
Your link is not showing your code
sorry my fault I have updated the link
Your code have 1 or 2 syntax error. Apart from that it is giving wrong at:
1
1 90
Your is getting wrong at :
1
2 90
Answer is 19 but your code is giving 91.
input for K is greater than 1